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.
@cite_35: This paper is on a graph clustering scheme inspired by ensemble learning. In short, the idea of ensemble learning is to learn several weak classifiers and use these weak classifiers to form a strong classifier. In this contribution, we use the generic procedure of ensemble learning and determine several weak graph clusterings (with respect to the objective function). From the partition given by the maximal overlap of these clusterings (the cluster cores), we continue the search for a strong clustering. We demonstrate the performance of this scheme by using it to maximize the modularity of a graph clustering. We show, that the quality of the initial weak clusterings is of minor importance for the quality of the final result of the scheme if we iterate the process of restarting from maximal overlaps. In addition to the empirical evaluation of the clustering scheme, we will link its search behavior to global analysis. With help of Morse theory and a discussion of the path space of the search heuristics we explain the superior search performance of this clustering scheme.
@cite_22: The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i.e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e.g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. This problem is very hard and not yet satisfactorily solved, despite the huge effort of a large interdisciplinary community of scientists working on it over the past few years. We will attempt a thorough exposition of the topic, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists, from the discussion of crucial issues like the significance of clustering and how methods should be tested and compared against each other, to the description of applications to real networks.
@cite_1: Ensemble clustering approaches have been recently applied, in a variety of ways, in order to enhance the quality and or the execution time of community detection tasks. The quality gain that can be obtained from applying ensemble approaches is known to be tightly linked to both quality and diversity of the applied clusterings. However, most of existing work simply ignore this important issue of ensemble selection. In this paper we intend to fill this gap. We propose a graph-based ensemble selection approach that allow to take into account both criteria of quality and diversity. Different quality measures are also considered: cluster-oriented quality and network-oriented quality functions. Experiments on real network datasets show the validity of our approach.
@cite_24: Statistical estimates can often be improved by fusion of data from several different sources. One example is so-called ensemble methods which have been successfully applied in areas such as machine learning for classification and clustering. In this paper, we present an ensemble method to improve community detection by aggregating the information found in an ensemble of community structures. This ensemble can found by re-sampling methods, multiple runs of a stochastic community detection method, or by several different community detection algorithms applied to the same network. The proposed method is evaluated using random networks with community structures and compared with two commonly used community detection methods. The proposed method when applied on a stochastic community detection algorithm performs well with low computational complexity, thus offering both a new approach to community detection and an additional community detection method.
@cite_19: In this paper we present an original approach for community detection in complex networks. The approach belongs to the family of seed-centric algorithms. However, instead of expanding communities around selected seeds as most of existing approaches do, we explore here applying an ensemble clustering approach to different network partitions derived from ego-centered communities computed for each selected seed. Ego-centered communities are themselves computed applying a recently proposed ensemble ranking based approach that allow to efficiently combine various local modularities used to guide a greedy optimization process. Results of first experiments on real world networks for which a ground truth decomposition into communities are known, argue for the validity of our approach.
@cite_31: Community detection and analysis is an important methodology for understanding the organization of various real-world networks and has applications in problems as diverse as consensus formation in social communities or the identification of functional modules in biochemical networks. Currently used algorithms that identify the community structures in large-scale real-world networks require a priori information such as the number and sizes of communities or are computationally expensive. In this paper we investigate a simple label propagation algorithm that uses the network structure alone as its guide and requires neither optimization of a predefined objective function nor prior information about the communities. In our algorithm every node is initialized with a unique label and at every step each node adopts the label that most of its neighbors currently have. In this iterative process densely connected groups of nodes form a consensus on a unique label to form communities. We validate the algorithm by applying it to networks whose community structures are known. We also demonstrate that the algorithm takes an almost linear time and hence it is computationally less expensive than what was possible so far.
@cite_17: Data analysis plays an indispensable role for understanding various phenomena. Cluster analysis, primitive exploration with little or no prior knowledge, consists of research developed across a wide variety of communities. The diversity, on one hand, equips us with many tools. On the other hand, the profusion of options causes confusion. We survey clustering algorithms for data sets appearing in statistics, computer science, and machine learning, and illustrate their applications in some benchmark data sets, the traveling salesman problem, and bioinformatics, a new field attracting intensive efforts. Several tightly related topics, proximity measure, and cluster validation, are also discussed.
There has been a great deal of work on clustering data using ensemble approaches (see @cite_17 for a review). However, when it comes to clustering vertices in , ensemble approaches have been relatively scarce See the survey @cite_22 for various community detection algorithms. . Dahlin and Svenson @cite_24 were the first to propose an instance-based ensemble CD algorithm for networks which fuses different community structures into a final representation. A few methods addressed the utility of merging several community structures @cite_31 . A new ensemble scheme called CGGC was proposed to maximize modularity @cite_35 . Kanawati proposed YASCA, an ensemble approach to different network partitions derived from ego-centered communities computed for each selected seed @cite_19 . He further emphasized the quality and diversity of outputs obtained from the base algorithms for ensemble selection @cite_1 .