Given a set @math of community detection algorithms and a graph @math as inputs, we propose two ensemble methods @math and @math that (respectively) identify disjoint and overlapping communities in @math . @math transforms a graph into a latent feature space by leveraging multiple base solutions and discovers disjoint community structure. @math groups similar base communities into a meta-community and detects both disjoint and overlapping community structures. Experiments are conducted at different scales on both synthetically generated networks as well as on several real-world networks for which the underlying ground-truth community structure is available. Our extensive experiments show that both algorithms outperform state-of-the-art non-ensemble algorithms by a significant margin. Moreover, we compare @math and @math with a recent ensemble method for disjoint community detection and show that our approaches achieve superior performance. To the best of our knowledge, @math is the first ensemble approach for overlapping community detection.
A consensus clustering'' @cite_33 approach was recently proposed which leverages a consensus matrix to produce a disjoint community structure which outperformed previous approaches. Our work differs from this approach in at least three significant ways: (i) they measure the number of times two vertices are assigned to the same community, thus ignoring the global similarity of vertices; whereas we capture the global similarity by representing the network within a feature space and grouping redundant base communities into meta communities; (ii) they either take multiple algorithms or run a particular algorithm multiple times for generating an ensemble matrix, whereas we consider both options; (iii) we are the first to show how aggregating multiple disjoint base communities can lead to discover both disjoint and overlapping community structures simultaneously. We show experimentally that beats consensus clustering.
@cite_33
2331397633
Although many successful ensemble clustering approaches have been developed in recent years, there are still two limitations to most of the existing approaches. First, they mostly overlook the issue of uncertain links, which may mislead the overall consensus process. Second, they generally lack the ability to incorporate global information to refine the local links. To address these two limitations, in this paper, we propose a novel ensemble clustering approach based on sparse graph representation and probability trajectory analysis. In particular, we present the elite neighbor selection strategy to identify the uncertain links by locally adaptive thresholds and build a sparse graph with a small number of probably reliable links. We argue that a small number of probably reliable links can lead to significantly better consensus results than using all graph links regardless of their reliability. The random walk process driven by a new transition probability matrix is utilized to explore the global information in the graph. We derive a novel and dense similarity measure from the sparse graph by analyzing the probability trajectories of the random walkers, based on which two consensus functions are further proposed. Experimental results on multiple real-world datasets demonstrate the effectiveness and efficiency of our approach.