Introduction to Label propagation algorithm (finding community structure in social networks) Problem description : Given a network or graph, how can you find the communities in this network. Although there is no precise definition about community, it basically means densely connected component in the network and loosely connected between different communities. Input : A social network N or a graph with nodes and links between them or an adjacent matrix. Output : A vector, in which each index represents each node in the network N and the value each index points represents which community the node belongs to. Algorithm : 1. initialization by assigning an unique label to each node in N 2. while the algorithm is not convergent, (convergence means every node does not change its label or the running times has reached the maximum number) 3. for each node 4. takes the label with the maximum number of neighbors have Advantages : Scalable: its running time is O(m), where m is the n