A Classification for Community Discovery Methods in Complex Networks

Michele Coscia; Fosca Giannotti; Dino Pedreschi

Source-linked AI summary

A Classification for Community Discovery Methods in Complex Networks

Michele Coscia, Fosca Giannotti, Dino Pedreschi

arXiv:1206.3552v1Jun 15, 2012cs.SIcs.DSphysics.soc-ph

TL;DR

Community discovery lacks a single adequate definition because real networks vary in structure, direction, dimensionality, and dynamics. This survey introduces a meta definition and organizes methods by the community definitions they use, while recording supported features and trade-offs. Its practical outcome is a classification intended to help analysts choose methods by desired community definition and network features.

Problem
Community discovery methods adopt different implicit or explicit community definitions and therefore capture different real-world features across complex network settings.
Method
The survey defines a community as entities sharing closely correlated actions, then classifies discovery methods by their reference community definition and records their output characteristics.
Results
The resulting classification organizes methods into categories such as internal density, structure, and link clustering, while comparing their strengths and weaknesses across network features.
Takeaways & Limitations
Analysts can use the classification and feature table to select methods according to their desired community definition and problem features rather than only the underlying algorithm.
Takeaways & Limitations
Link Clustering ignores relation direction, while modularity has a resolution problem that can miss communities below a network-dependent scale.

Abstract

from arXiv · show

In the last few years many real-world networks have been found to show a so-called community structure organization. Much effort has been devoted in the literature to develop methods and algorithms that can efficiently highlight this hidden structure of the network, traditionally by partitioning the graph. Since network representation can be very complex and can contain different variants in the traditional graph model, each algorithm in the literature focuses on some of these properties and establishes, explicitly or implicitly, its own definition of community. According to this definition it then extracts the communities that are able to reflect only some of the features of real communities. The aim of this survey is to provide a manual for the community discovery problem. Given a meta definition of what a community in a social network is, our aim is to organize the main categories of community discovery based on their own definition of community. Given a desired definition of community and the features of a problem (size of network, direction of edges, multidimensionality, and so on) this review paper is designed to provide a set of approaches that researchers could focus on.

1. Introduction

Community discovery identifies groups hidden in complex networks, but varying network representations and community meanings make a single definition insufficient. The survey therefore organizes methods by their adopted community definition and relevant network features.

Community discovery seeks groups of entities that are closer internally than externally and may share properties or roles.
Unlike ordinary clustering, community discovery must account for relational structure, mapping proximity between entities to network topology.
Classical density-based communities contain many internal edges and fewer edges between groups, but this definition becomes imprecise for temporal, propagating, or multidimensional networks.
Communities may be hierarchical, overlapping, directed, dynamic, or multi-relational, so algorithms capture only selected features of real communities.
The survey shifts classification from how algorithms operate to what kinds of communities they aim to detect, recording output characteristics and method suitability.
It introduces a meta definition in which communities are entities sharing closely correlated sets of actions, with direct connections treated as an important action type.

3. The Definition-based classification

The survey classifies community discovery algorithms according to the definition of community they adopt rather than their operational procedure. It presents categories, feature implications, graphical examples, and a practical mapping from analytical needs to available methods.

Classification principle: Algorithms are grouped when they share the same conditions defining which entities can be clustered together as a community.
Proposed categories: The main categories include Feature Distance, Internal Density, Bridge Detection, Diffusion, Closeness, Structure, Link Clustering, and No Definition.
Feature analysis: The classification records which network and algorithmic features each category naturally supports or makes difficult, without claiming an axiomatic categorization.
Scope: The survey focuses on recent approaches and general community definitions rather than historical algorithms such as Kernighan-Lin or classical spectral bisection.
Classification overlap: Categories can overlap because methods may use broad meta definitions or shared search-space and partition-quality strategies.
Illustrative analysis: Graphical examples depict typical communities for several categories and expose differences in their definitions and feature properties.
Scope: Although deriving one algorithm from another is left for future work, the classification connects analysts’ community definitions with available tools.

4. Feature Distance

Feature-distance communities group entities that share specified features and are close under a distance measure, extending graph community discovery toward matrix or spatial clustering. The category also includes temporal, multidimensional, and compression-based approaches, but feature-based clustering can weaken the visible role of graph structure.

Definition and procedure: A feature community contains entities sharing a precise set of features, including edges, whose feature-based distance is smaller within than outside the community.The meta procedure represents entities and attributes as vectors, then applies matrix or spatial clustering.
Definition and procedure: Feature-distance discovery resembles unsupervised data-mining clustering, using similarity or distance to assign entities with shared features to groups.The paper cites K-means, co-clustering, and spectral clustering as related approaches.
Limitation: Depending on the number of node and edge attributes, feature-based positioning can reduce the importance of graph structure and produce counterintuitive visual clusters with many inter-community edges.The distance need not be based on direct edge connections and may be highly dimensional.
Related approaches: MDL methods identify groupings by compressing regularities, while Timefall tracks evolving communities, their structural changes, and change points without requiring parameters.Autopart reorders adjacency matrices to group similar nodes; Timefall also identifies appearances, disappearances, splits, and merges.
Temporal extension: Temporal clustering adds snapshot quality and history cost so successive clusterings balance fit to current data with distance from the previous clustering.The framework also targets consistency, noise removal, smoothing, and correspondence across time steps.
Related approaches: The surveyed feature-oriented approaches also cover heterogeneous k-partite graphs, multi-way clustering, latent social dimensions, and multidimensional community discovery.Examples include RSN-BD, MRGC, and SocDim, which use relation summaries, clustering functions, or modularity-based latent dimensions.

5. Internal Density

Internal-density methods define communities through unusually dense within-group connectivity, often measured against a degree-preserving random-graph expectation. The section reviews modularity-based optimization and related density approaches, while noting limitations for resolution, local optima, and multidimensional networks.

Definition: Dense communities contain significantly more internal edges than expected in a random graph without community structure.
Procedure: Algorithms in this category expand or collapse node partitions to optimize a density function until no further improvement is possible.
Modularity: Modularity measures deviation from a random graph with the same degree distribution, with larger values indicating denser within-group interaction.
Limitations: Modularity evaluation suffers from resolution problems and can be misleading when the chosen community definition differs from modularity’s assumptions.
Limitations: Density optimization is suitable for directed and weighted graphs, but multidimensional networks make a consistent multirelational density difficult to compute.
Modularity maximization: Because exact modularity maximization is NP-complete, greedy heuristics repeatedly merge communities producing the largest increase in Q and cut the resulting dendrogram at its modularity peak.

6. Bridge Detection

Bridge-detection methods define communities by removing sparse connectors between dense parts, without requiring the resulting clusters themselves to be internally dense. They identify bridges through connectivity measures, shortest-path centrality, or local expansion and fitness procedures.

Definition: An isolated community is obtained by removing sparse bridges that connect dense parts of the network.
Procedure: Bridge-detection algorithms rank nodes or edges by their contribution to network connectivity, then remove bridges or avoid expanding through them.
Bridge identification: Removing the bridge in Figure 7 decomposes the graph into disconnected components, while making no assumption about the internal density of those components.
Edge betweenness: Edge betweenness counts shortest paths traversing an edge; under the loosely connected-community assumption, intercommunity edges receive higher values and can be removed.
Overlapping communities: CONGA extends edge betweenness by splitting vertices using split betweenness, allowing disjoint community procedures to produce overlapping partitions.
Local expansion: L-shell expansion stops when the increase in total emerging degree falls below threshold α or the connected component is exhausted, with O(n^3) time complexity per the described analysis.
Local fitness: For the local fitness method, large α yields very small communities, small α yields large modules, and varying α from 0.5 to 2 reveals hierarchical structure.

7. Diffusion

Diffusion-based methods define communities through nodes grouped by shared propagation states, actions, or information. This category naturally supports directed and dynamic communities, while multidimensional networks remain unaddressed in the reviewed approaches.

A diffusion community groups nodes reached by propagation of the same property, action, or information.
The meta-procedure performs diffusion or percolation under transmission rules, then groups nodes ending in the same state.
Influence-based communities can consist of entities affected by the same fixed sources, linking community discovery with influence spread and flow maximization.
Reviewed diffusion approaches include label propagation, dynamic node coloring, edge-resistor methods, influence models, GuruMine, DegreeDiscountIC, and mixed-membership blockmodels.
Directed and dynamic communities are natural outcomes of diffusion models because information spread follows asymmetric relations and evolves over time.
Label propagation assigns nodes the majority neighbor label and groups identical labels in O(m + n) time; ties can produce overlaps.Densely connected groups quickly converge on a shared label, while equal maxima allow a node to belong to multiple communities.

8. Closeness

Closeness-based methods define communities as groups whose members reach one another in unusually few hops. Random walks operationalize this idea by clustering nodes that frequently co-occur, but path-based methods inherit limitations for multidimensional networks.

A small-world community contains nodes reachable from one another in far fewer edges than the network’s average shortest path.
The meta-procedure performs multiple random walks and clusters nodes that frequently appear together in a walk.
Closeness algorithms inherit bridge-detection weaknesses because paths are central to their community definitions, especially in multidimensional networks.
Random-walk methods: Walktrap, DOCS, and Infomap are highlighted as major random-walk community discoverers, with Infomap combining information theory and random walks.
Random-walk methods: Walktrap measures similarity from random-walk behavior, treating communities as regions where walks frequently explore the same nodes.
Random-walk methods: Walk length must balance topology coverage against excessive length, which makes probabilities depend only on destination degree.

9. Structure Definition

Structure-based methods require communities to satisfy precise topological rules rather than merely exhibit density or closeness. They seek maximal instances of the chosen structure, offering flexible definitions but potential incremental-processing drawbacks.

A structure community is a node set with a precise edge count and topology satisfying explicit structural rules.
The corresponding procedure efficiently finds all maximal network structures satisfying the desired constraints.
Unlike traditional graph mining, community discovery returns all vertex groups forming the target structure rather than distinct patterns with support.
The reviewed structural approaches include clique percolation, bipartite clique percolation, s-plex enumeration, and maximal-clique methods.
Structural definitions can encode overlapping, weighted, directed, or multidimensional features, but their incremental scalability is identified as a downside.

k-cliques.

The survey presents clique-based structures and their relaxations for discovering communities with explicit topology. Clique percolation supports overlapping groups, while Bi-Clique addresses sparse affiliation networks where ordinary k-cliques can fail.

Clique percolation defines a community as k-cliques connected through adjacency, where adjacent cliques share k −1 nodes.
The method constructs a clique-overlap matrix and retains clique connections meeting the required overlap threshold to identify k-clique communities.
Clique-percolation communities may overlap because distinct chains of cliques can share vertices.
S-plexes: An s-plex relaxes clique structure by requiring each vertex in a size-k set to have minimum degree at least k −s.
S-plexes: The s-plex enumeration algorithm removes insufficiently connected candidates, uses the complement graph and pivot sets, and runs in O(knm).
Bi-Clique: Bi-Clique targets sparse bipartite affiliation networks and detects structures between 2-clique and 3-clique communities where k-clique methods often fail.The approach preserves bipartite linkage structure instead of relying on a lossy one-mode projection.

10. Link Clustering

Link clustering defines communities over relations rather than nodes, so nodes can belong to multiple communities through their links. Reviewed methods project or compare links, then apply clustering and optimize the resulting structure.

Link communities cluster relations belonging to particular relational environments, while entities belong to the communities of their associated links.
This formulation naturally produces overlapping, and often hierarchical, network structures because links have unique memberships while nodes inherit multiple memberships.The approach also ignores relation direction when links are undirected.
A basic strategy constructs a projection graph whose nodes represent original links, measures link proximity, and applies a classical clustering algorithm.
Reviewed approaches include random-walk proximity with modularity, arbitrary edge-distance measures with hierarchical clustering, and a Bayesian approach.
A line-graph implementation computes modularity after projecting the node-link incidence matrix, with total complexity O(2mk log n).
Hierarchical Link Clustering uses Jaccard similarity between adjacent edges, builds a link dendrogram, and cuts it by optimizing partition density.The dendrogram leaves are original links, whereas its branches represent link communities.

11. Link Maximum Likelihood [52]

Link Maximum Likelihood extends link clustering to multidimensional networks by modeling and testing partitions of edges across different dimensions.

The method generates a model for the observed multidimensional network under a proposed partition of edges into link communities.
It evaluates the proposed edge communities with a maximum-likelihood procedure resembling Expectation Maximization.

12. No Definition

The “No Definition” category covers frameworks that impose desired community features through preprocessing or postprocessing rather than a shared intrinsic community definition. It includes hybrid, multidimensional, Bayesian hierarchical, and expectation-maximization approaches.

These frameworks often attach desired community features to existing algorithms through preprocessing or postprocessing operations.
The category’s definition treats communities as sets with particular features, regardless of why their nodes are grouped.
The survey excludes methods such as evolutionary clustering and CONGA when they already provide an explicit community definition.
The reviewed methods include a Bayesian/non-Bayesian hybrid, analyst-specified multidimensional discovery, Bayesian hierarchical modeling, and expectation maximization.
12.1. Hybrid: The hybrid framework uses non-overlapping algorithms to provide hints to an overlapping Bayesian core, reflecting cases where nodes’ links require multiple memberships.
12.1. Hybrid: Its coalescing strategies incorporate hints as node attributes, initial seeds, or priors, with Gibbs sampling for inference and additional complexity O(nk ¯K).
12.2. Multidimensional: The multidimensional method weights relation matrices and uses an analyst’s example to reconstruct a hidden relation before community discovery.Ridge regression predicts hidden relation strengths after estimating combination coefficients.
12.3. Bayesian Hierarchical: The Bayesian hierarchical approach samples maximum-likelihood dendrograms and merges them into a consensus dendrogram, with average complexity expected not to exceed O(n2).Its worst-case time complexity is exponential.

13. Experiments

The experiments compare selected community-discovery algorithms on a Facebook ego network to illustrate which desired structural features methods can naturally represent or struggle with.

The evaluation aims to clarify which desired community features each algorithm category can represent naturally or has difficulty handling.
The benchmark is a Facebook ego network containing 261 nodes and 1,722 edges, with visually identifiable dense areas, gray regions, and smaller cliques.The authors also had knowledge of the actual partition but withheld detailed data for privacy reasons.
Figure 15 depicts the benchmark network used for the experimental evaluation.
The survey excludes methods lacking an available implementation, duplicating another included method, or failing to produce a result within two hours and 1GB of memory.
All evaluation measures accept partitions represented as node sets that may overlap.

• Modularity

The evaluation compares community-discovery categories using measures of topology, overlap, and community structure. Results show that different definitions favor different network properties, while some categories expose limitations of particular measures or methods.

• Modularity: Modularity is computed only for non-overlapping partitions because the standard measure is not defined for overlapping results.The review notes that overlapping versions of modularity exist, but evaluates the original formulation only on non-overlapping outputs.
• Modularity: Flake-ODF measures the fraction of community nodes having fewer internal than external edges, averaged across communities.The measure complements modularity by assessing whether nodes are more connected outside their assigned cluster than inside it.
• Modularity: Evaluation measures consistently assign lower scores to overlapping partitions in the same network, indicating that they should be refined to handle overlap.The authors report this pattern across the measures tested, not only for modularity.
• Modularity: Feature Distance methods support varied features but can produce counterintuitive topology, with SocDim and Autopart scoring poorly on density-based evaluations.Autopart performs poorly on modularity, while both methods receive higher Flake-ODF values, meaning external edges are often more numerous than internal ones.
• Modularity: Internal Density methods achieve high internal edge volume, whereas Closeness methods favor different community scales and densities.Modularity has the highest reverse-conductance score among the Internal Density methods; Walktrap favors larger denser groups, while Infomap favors smaller sparser ones.
• Modularity: K-Clique’s strict structure leaves some nodes unassigned, while Link Community methods produce highly overlapping partitions.The K-Clique overlap ratio is below one, whereas Link Community algorithms obtain very high overlap scores.

14. Related Works

Earlier reviews organized community-discovery methods by application area, technique, practical performance, or broad community concepts. The paper argues that researchers also need a classification based on the definitions of community adopted by the algorithms.

14. Related Works: Several prior reviews cover community-discovery methods, with Fortunato and Castellano’s work described as among the most comprehensive.These reviews examine definitions, extraction features, categories, techniques, or algorithmic performance from different perspectives.
14. Related Works: Fortunato and Castellano organize methods by techniques and features but do not classify algorithms according to their underlying community definitions.The paper presents this distinction as the reason their review is less suited to users seeking methods for a specified community concept.
14. Related Works: Other reviews introduce community concepts or compare algorithms practically, but do not provide a definition-based classification.Porter and Schaeffer begin discussing different definitions, while Danon and colleagues emphasize complexity and performance comparisons.
14. Related Works: Newman’s review follows historical fields of application, and graph-mining surveys describe classical edge-density concepts without being devoted specifically to community discovery.Benchmark graphs have also been proposed for testing community-discovery algorithms.

15. Conclusions

The survey presents a manual for selecting community-discovery algorithms according to the analyst’s definition of community and the network features that matter. It proposes a definition-based classification, documents feature support, and identifies overlap analysis and future multidimensional methods as open directions.

15. Conclusions: The survey aims to answer which community-detection algorithm analysts should use given their definition of a community.This perspective is intentionally orthogonal to reviews aimed primarily at researchers developing new detection algorithms.
15. Conclusions: The authors propose a meta definition of community and classify methods by how their definitions relate to it.The review presents categories such as Internal Density and Community Structure Definition, together with complexity and category-level strengths and weaknesses.
15. Conclusions: The classification still needs an extensive study of overlap among community definitions, algorithms, input-output features, quality functions, and search strategies.The authors suggest representing these connections as a graph to obtain a clearer view of the community-discovery problem.
15. Conclusions: The review adds graph-partition features such as multidimensionality and overlapping communities, helping analysts choose methods by supported features as well as community definition.The paper cautions that a longer feature list does not necessarily make an approach better than a specialized method.
15. Conclusions: Future work includes identifying important future features, extracting truly multidimensional communities, and handling hierarchical and overlapping organization simultaneously.The paper leaves prediction of the most important future features as an open question.