On the detection of transitive clusters in undirected networks
- 2 July 2018
- journal article
- research article
- Published by Taylor & Francis Ltd in Journal of Applied Statistics
- Vol. 46 (2), 364-384
- https://doi.org/10.1080/02664763.2018.1491535
Abstract
A network cluster is defined as a set of nodes with ‘strong’ within group ties and ‘weak’ between group ties. Most clustering methods focus on finding groups of ‘densely connected’ nodes, where the dyad (or tie between two nodes) serves as the building block for forming clusters. However, since the unweighted dyad cannot distinguish strong relationships from weak ones, it then seems reasonable to consider an alternative building block, i.e. one involving more than two nodes. In the simplest case, one can consider the triad (or three nodes), where the fully connected triad represents the basic unit of transitivity in an undirected network. In this effort we propose a clustering framework for finding highly transitive subgraphs in an undirected/unweighted network, where the fully connected triad (or triangle configuration) is used as the building block for forming clusters. We apply our methodology to four real networks with encouraging results. Monte Carlo simulation results suggest that, on average, the proposed method yields good clustering performance on synthetic benchmark graphs, relative to other popular methods.Keywords
Funding Information
- Air Force Office of Scientific Research (FA9550-15-1-0019)
This publication has 18 references indexed in Scilit:
- Community detection in networks: A user guidePhysics Reports, 2016
- Approximating dependent rare eventsBernoulli, 2013
- Community detection in graphsPhysics Reports, 2009
- Benchmark graphs for testing community detection algorithmsPhysical Review E, 2008
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Correlated binomial models and correlation structuresJournal of Physics A: General Physics, 2006
- Community structure in social and biological networksProceedings of the National Academy of Sciences of the United States of America, 2002
- A Review of Hierarchical ClassificationJournal of the Royal Statistical Society. Series A (General), 1987
- Optimization by Simulated AnnealingScience, 1983
- The Strength of Weak Ties: A Network Theory RevisitedSociological Theory, 1983