An efficient influence based label propagation algorithm for clustering large graphs

摘要

Representing data in the form of graph offer a very powerful way to provideprimitive representations for many applications spanning from biological networks, web networks to social networks. In the current era of Big data, size of the graphs is growing exponentially. Clustering large graphs can provide useful insights about graphs. In this paper, an efficient influence based Label propagation algorithm (ILPA) is proposed for clustering large graphs from big data applications. The proposed algorithm stabilizes the tradition LPA to make it computationally less expensive. The proposed ILPA starts by labeling only those vertices that have high influence in network and set them as cluster centers. Further, the selected cluster centers spread their influence by passing it's label to the neighboring vertices. In the end, the vertices with same label are gathered together to form a cluster. The performance evaluation is carried out on two real life graph datasets. It is shown that the proposed ILPA outperforms the state-of art clustering algorithms in terms of Modularity and F-Measure.