Search

Most real-world information networks are heterogeneous, which contain multiple types of entities and relations between the entities. Large-scale and heterogeneity are the typical properties of heterogeneous information networks, and their community structures are often overlapping, complex, and diverse. The existing community detection algorithms without considering the above-mentioned properties may lead to low accuracy or high time complexity of community detection. In this paper, we study the multi-dimensional heterogeneous community detection problem for large-scale heterogeneous information networks with general topology structures. We define the concept of node-centric community and propose a multi-dimensional community detection algorithm referred as Hete_MESE. Specifically, we first specify one of the multiple entity types in heterogeneous information networks as community centric node type and extract the multiplex networks accordingly, and then, overlapping node-centric communities are detected based on the multiplex networks, which are considered as the seed communities to absorb the other entity types to generate the heterogeneous communities utilizing seed expansion. Taking heterogeneous academic network as an example, the effects of Hete_MESE are evaluated through extensive experiments, and the features of detected multi-dimensional academic communities are analyzed. The results demonstrate that Hete_MESE can accurately and effectively detect the meaningful overlapping and heterogeneous communities in heterogeneous information networks with general topologies from multiple dimensions. Moreover, Hete_MESE has linear time complexity, so it can be applied to large-scale heterogeneous information networks.

Community detection is an important task in network analysis. A community (also referred to as a cluster) is a set of cohesive vertices that have more connections inside the set than outside. In many social and information networks, these communities naturally overlap. For instance, in a social network, each vertex in a graph corresponds to an individual who usually participates in multiple communities. In this paper, we propose an efficient overlapping community detection algorithm using a seed expansion approach. The key idea of our algorithm is to find good seeds, and then greedily expand these seeds based on a community metric. Within this seed expansion method, we investigate the problem of how to determine good seed nodes in a graph. In particular, we develop new seeding strategies for a personalized PageRank clustering scheme that optimizes the conductance community score. An important step in our method is the neighborhood inflation step where seeds are modified to represent their entire vertex neighborhood. Experimental results show that our seed expansion algorithm outperforms other state-of-the-art overlapping community detection methods in terms of producing cohesive clusters and identifying ground-truth communities. We also show that our new seeding strategies are better than existing strategies, and are thus effective in finding good overlapping communities in real-world networks. [ABSTRACT FROM PUBLISHER]