A framework for community detection in heterogeneous multi-relational networks

Abstract

There has been a surge of interest in community detection in homogeneous single-relational networks which contain only one type of nodes and edges. However, many real-world systems are naturally described as heterogeneous multi-relational networks which contain multiple types of nodes and edges. In this paper, we propose a new method for detecting communities in such networks. Our method is based on optimizing the composite modularity, which is a new modularity proposed for evaluating partitions of a heterogeneous multi-relational network into communities. Our method is parameter-free, scalable, and suitable for various networks with general structure. We demonstrate that it outperforms the state-of-the-art techniques in detecting pre-planted communities in synthetic networks. Applied to a real-world Digg network, it successfully detects meaningful communities.

27 pages, 10 figures

References in corpus (11)

• Fast unfolding of communities in large networks
• Finding community structure in networks using the eigenvectors of matrices
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Statistical Mechanics of Community Detection
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Modularity and community detection in bipartite networks
• Community detection in networks with positive and negative links
• Detecting network communities by propagating labels under constraints
• Multistep greedy algorithm identifies community structure in real-world and computer-generated networks
• An Ant-Based Algorithm with Local Optimization for Community Detection in Large-Scale Networks