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 (24)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Community detection algorithms: a comparative analysis
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Statistical Mechanics of Community Detection
• Community detection in complex networks using Extremal Optimization
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• The performance of modularity maximization in practical contexts
• Modularity and community detection in bipartite networks
• Limits of modularity maximization in community detection
• Community detection in networks with positive and negative links
• Detecting network communities by propagating labels under constraints
• Advanced modularity-specialized label propagation algorithm for detecting communities in networks
• Multistep greedy algorithm identifies community structure in real-world and computer-generated networks
• Detecting Communities in Tripartite Hypergraphs
• An Ant-Based Algorithm with Local Optimization for Community Detection in Large-Scale Networks
• Relation Strength-Aware Clustering of Heterogeneous Information Networks with Incomplete Attributes