There has been a lot of interest in developing algorithms to extract clusters or communities from networks. This work proposes a method, based on blockmodelling, for leveraging communities and other topological features for use in a predictive classification task. Motivated by the issues faced by the field of community detection and inspired by recent advances in Bayesian topic modelling, the presented model automatically discovers topological features relevant to a given classification task. In this way, rather than attempting to identify some universal best set of clusters for an undefined goal, the aim is to find the best set of clusters for a particular purpose. Using this method, topological features can be validated and assessed within a given context by their predictive performance. The proposed model differs from other relational and semi-supervised learning models as it identifies topological features to explain the classification decision. In a demonstration on a number of real networks the predictive capability of the topological features are shown to rival the performance of content based relational learners. Additionally, the model is shown to outperform graph-based semi-supervised methods on directed and approximately bipartite networks.
In the past decade community detection has received a lot of attention from researchers spanning a wide range of domains and has consequently produced a wide range of approaches to the problem; for a comprehensive review of these approaches see @cite_16 . Although there is no commonly accepted formal definition for community detection, a lot of approaches focus on the optimisation of the Newman-Givan modularity function @cite_32 . The Newman-Givan modularity function, @math , of a network partition made up of @math disjoint communities is given by: where @math is the number of edges in community @math , @math is the number of edges in the network and @math is the total degree of the nodes in community @math . Commonly used as it is, the modularity function has been found to suffer from a number of issues such as a resolution limit @cite_23 and degeneracy of solutions @cite_7 . Rather than seek to find a globally optimum set of clusters, the proposed approach addresses the degeneracy issue by attempting to find clusters which are able to predict the class of a node.
@cite_7 @cite_16 @cite_32 @cite_23
2015953751 2209225614 2064274783 1967022297
We consider the problem of detecting communities or modules in networks, groups of vertices with a higher-than-average density of edges connecting them. Previous work indicates that a robust approach to this problem is the maximization of the benefit function known as "modularity" over possible divisions of a network. Here we show that this maximization process can be written in terms of the eigenspectrum of a matrix we call the modularity matrix, which plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations. This result leads us to a number of possible algorithms for detecting community structure, as well as several other results, including a spectral measure of bipartite structure in networks and a new centrality measure that identifies those vertices that occupy central positions within the communities to which they belong. The algorithms and measures proposed are illustrated with applications to a variety of real-world complex networks. Community detection is a topic of interest in the study of complex networks such as the protein–protein interaction networks and metabolic networks. In recent years, various methods were proposed to detect community structures of the networks. Here, a kind of local modularity with tunable parameter is derived from the Newman–Girvan modularity by a special self-loop strategy that depends on the community division of the networks. By the self-loop strategy, one can easily control the definition of modularity, and the resulting modularity can be optimized by using the existing modularity optimization algorithms. The local modularity is used as the target function for community detection, and a self-consistent method is proposed for the optimization of the local modularity. We analyze the behaviors of the local modularity and show the validity of the local modularity in detecting community structures on various networks. Prompted by the increasing interest in networks in many fields, we present an attempt at unifying points of view and analyses of these objects coming from the social sciences, statistics, probability and physics communities. We apply our approach to the Newman–Girvan modularity, widely used for “community” detection, among others. Our analysis is asymptotic but we show by simulation and application to real examples that the theory is a reasonable guide to practice. Communities of vertices within a giant network such as the World-Wide Web are likely to be vastly smaller than the network itself. However, Fortunato and Barth ' e lemy have proved that modularity maximization algorithms for community detection may fail to resolve communities with fewer than @math edges, where @math is the number of edges in the entire network. This resolution limit leads modularity maximization algorithms to have notoriously poor accuracy on many real networks. Fortunato and Barth ' e lemy's argument can be extended to networks with weighted edges as well, and we derive this corollary argument. We conclude that weighted modularity algorithms may fail to resolve communities with fewer than @math total edge weight, where @math is the total edge weight in the network and @math is the maximum weight of an inter-community edge. If @math is small, then small communities can be resolved. Given a weighted or unweighted network, we describe how to derive new edge weights in order to achieve a low @math , we modify the CNM'' community detection algorithm to maximize weighted modularity, and show that the resulting algorithm has greatly improved accuracy. In experiments with an emerging community standard benchmark, we find that our simple CNM variant is competitive with the most accurate community detection methods yet proposed.