Community detection and tracking on networks from a data fusion perspective

Abstract

Community structure in networks has been investigated from many viewpoints, usually with the same end result: a community detection algorithm of some kind. Recent research offers methods for combining the results of such algorithms into timelines of community evolution. This paper investigates community detection and tracking from the data fusion perspective. We avoid the kind of hard calls made by traditional community detection algorithms in favor of retaining as much uncertainty information as possible. This results in a method for directly estimating the probabilities that pairs of nodes are in the same community. We demonstrate that this method is accurate using the LFR testbed, that it is fast on a number of standard network datasets, and that it is has a variety of uses that complement those of standard, hard-call methods. Retaining uncertainty information allows us to develop a Bayesian filter for tracking communities. We derive equations for the full filter, and marginalize it to produce a potentially practical version. Finally, we discuss closures for the marginalized filter and the work that remains to develop this into a principled, efficient method for tracking time-evolving communities on time-evolving networks.

40 pages, 11 figures

References in corpus (15)

• Fast unfolding of communities in large networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Quantifying social group evolution
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Mixture models and exploratory analysis in networks
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• A Bayesian Approach to Network Modularity
• Characterizing the community structure of complex networks
• Community Detection as an Inference Problem