Stability of Maximum likelihood based clustering methods: exploring the backbone of classifications (Who is keeping you in that community?)
arXiv:0809.1398
Abstract
Components of complex systems are often classified according to the way they interact with each other. In graph theory such groups are known as clusters or communities. Many different techniques have been recently proposed to detect them, some of which involve inference methods using either Bayesian or Maximum Likelihood approaches. In this article, we study a statistical model designed for detecting clusters based on connection similarity. The basic assumption of the model is that the graph was generated by a certain grouping of the nodes and an Expectation Maximization algorithm is employed to infer that grouping. We show that the method admits further development to yield a stability analysis of the groupings that quantifies the extent to which each node influences its neighbors group membership. Our approach naturally allows for the identification of the key elements responsible for the grouping and their resilience to changes in the network. Given the generality of the assumptions underlying the statistical model, such nodes are likely to play special roles in the original system. We illustrate this point by analyzing several empirical networks for which further information about the properties of the nodes is available. The search and identification of stabilizing nodes constitutes thus a novel technique to characterize the relevance of nodes in complex networks.
19 pages, 9 figures
References in corpus (16)
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in networks using the eigenvectors of matrices
- Resolution limit in community detection
- Who is the best connected scientist? A study of scientific coauthorship networks
- Hierarchical structure and the prediction of missing links in networks
- The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
- Synchronization reveals topological scales in complex networks
- Mixture models and exploratory analysis in networks
- A Bayesian Approach to Network Modularity
- A network analysis of committees in the United States House of Representatives
- Community Detection as an Inference Problem
- Inversion method for content-based networks
- Bayesian approach to clustering real value, categorical and network data: solution via variational methods