Top Leaders Community Detection Approach in Information Networks

Abstract

Much of the data of scientific interest, particularly when in-dependence of data is not assumed, can be represented in the form of information networks where data nodes are joined together to form edges corresponding to some kind of associ-ations or relationships. Such information networks abound, like protein interactions in biology, web page hyperlink con-nections in information retrieval on the Web, cellphone call graphs in telecommunication, co-authorships in bibliomet-rics, crime event connections in criminology, etc. All these networks, also known as social networks, share a common property, the formation of connected groups of informa-tion nodes, called community structures. These groups are densely connected nodes with sparse connections outside the group. Finding these communities is an important task for the discovery of underlying structures in social networks, and has recently attracted much attention in data mining research. In this paper, we present Top Leaders, a new community mining approach that, simply put, regards a community as a set of followers congregating around a potential leader. Our algorithm starts by identifying promising leaders in a given network then iteratively assembles followers to their closest leaders to form communities, and subsequently finds new leaders in each group around which to gather followers again until convergence. Our intuitions are based on proven obser-vations in social networks and the results are very promis-ing. Experimental results on benchmark networks verify the feasibility and effectiveness of our new community mining approach. 1.