The Label Propagation algorithm (LPA) is a fast algorithm for finding communities in a graph. It detects these communities using network structure alone as its guide, and doesn’t require a pre-defined objective function or prior information about the communities.

One interesting feature of LPA is that nodes can be assigned preliminary labels to narrow down the range of solutions generated. This means that it can be used as semi-supervised way of finding communities where we hand-pick some initial communities.

The intuition behind the algorithm is that a single label can quickly become dominant in a densely connected group of nodes, but will have trouble crossing a sparsely connected region. Labels will get trapped inside a densely connected group of nodes, and those nodes that end up with the same label when the algorithms finish can be considered part of the same community.

• The algorithm works as follows:
• Every node is initialized with a unique community label (an identifier).
• These labels propagate through the network.
• At every iteration of propagation, each node updates its label to the one that the maximum numbers of its neighbours belongs to. Ties are broken uniformly and randomly.
• LPA reaches convergence when each node has the majority label of its neighbours.
• LPA stops if either convergence or the user-defined maximum number of iterations is achieved.

As labels propagate, densely connected groups of nodes quickly reach a consensus on a unique label. At the end of the propagation only a few labels will remain - most will have disappeared. Nodes that have the same community label at convergence are said to belong to the same community.

• Label propagation has been used to assign polarity of tweets, as a part of semantic analysis which uses seed labels from a classifier trained to detect positive and negative emoticons in combination with Twitter follower graph. For more information, see Twitter polarity classification with label propagation over lexical links and the follower graph
• Label propagation has been used to estimate potentially dangerous combinations of drugs to co-prescribe to a patient, based on the chemical similarity and side effect profiles. The study can be found in Label Propagation Prediction of Drug-Drug Interactions Based on Clinical Side Effects
• Label propagation has been used to infer features of utterances in a dialogue, for a machine learning model to track user intention with the help of Wikidata knowledge graph of concepts and their relations. For more information, see "Feature Inference Based on Label Propagation on Wikidata Graph for DST"

Using seed labels

At the beginning of the algorithm, every node is initialized with a unique label and the labels propagate through the network.

It is possible to define preliminary labels of nodes using the parameter. We need to store a preliminary set of labels that we would like to run the Label Propagation algorithm with as node properties.

The algorithm first checks if there is a seed label assigned to the node, and loads it if there is one. If there isn’t one, it assigns a new unique label to the node. Using this preliminary set of labels, it then sequentially updates each node’s label to a new one, which is the most frequent label among its neighbors at every iteration of label propagation.

You can send your manuscript at https://bit.ly/2GFUS3A  

Media Contact:

Lina James

Managing Editor

Mail Id: computersci@scholarlypub.com 

American Journal of Computer Science and Information Technology

Whatsapp number: + 1-504-608-2390