Source-linked AI summary
Community detection in networks: Structural communities versus ground truth
Darko Hric, Richard K. Darst, Santo Fortunato
TL;DR
Community detection commonly assumes that topology reveals node classes, but evidence has been limited by the scarcity of networks with node classifications. The paper compares popular algorithms with metadata groups across diverse large networks and finds substantial separation, with many metadata groups not recovered by standard methods. This suggests that metadata groups are not necessarily correlated with structurally detected communities and may require non-topological inputs.
Problem
Evidence for whether structural communities correspond to non-topological node classes has been limited by the scarcity of network datasets containing node classifications.
Method
The paper compares partitions and individual communities produced by popular detection algorithms with metadata groups across a collection of real and synthetic network datasets.
Results
A substantial difference separates structural communities from metadata groups: large networks generally show low overlap, and no method performs particularly well across the collection.
Takeaways & Limitations
Metadata groups are not necessarily correlated with communities found by standard methods, so detecting them may require non-topological inputs.
Takeaways & Limitations
The node classifications may not always be reliable, and the study cannot exclude datasets where metadata groups match structural communities more closely.
Abstract
from arXiv · showhide
Algorithms to find communities in networks rely just on structural information and search for cohesive subsets of nodes. On the other hand, most scholars implicitly or explicitly assume that structural communities represent groups of nodes with similar (non-topological) properties or functions. This hypothesis could not be verified, so far, because of the lack of network datasets with information on the classification of the nodes. We show that traditional community detection methods fail to find the metadata groups in many large networks. Our results show that there is a marked separation between structural communities and metadata groups, in line with recent findings. That means that either our current modeling of community structure has to be substantially modified, or that metadata groups may not be recoverable from topology alone.
I. INTRODUCTION
Community detection uses network topology to identify cohesive node subsets, often assuming these structural communities reveal non-topological classes or functions. This paper tests that assumption by comparing algorithmic communities with metadata groups in diverse networks.
- Motivation: Community detection seeks subgraphs with dense internal links and comparatively sparse external links.Such structure is often interpreted as evidence that nodes belong to the same class.
- Motivation: Structural community methods are commonly expected to reveal hidden node attributes when those attributes are otherwise inaccessible.The paper describes this as an implicit assumption in the field.
- Study goal: The study tests whether popular algorithms recover metadata groups across a collection of network datasets, comparing both whole partitions and individual communities.Metadata groups are derived from non-topological node information.
- Study goal: The comparison finds poor agreement between detected structural communities and metadata groups for all methods examined.The paper therefore questions whether purely topological detection can extrapolate hidden node features.
- Terminology: Metadata groups are not assumed to be structural communities, because the study treats their correspondence as an empirical question.The paper uses “metadata groups” rather than “ground truth” to avoid presuming that correspondence.
A. Network datasets
The study assembles network datasets with node metadata for constructing groups that can be compared with communities detected from topology. The collection includes classical benchmarks, larger real networks, and preprocessing for consistent analysis.
- Dataset collection: The dataset collection uses node metadata to create groups that approximate communities, spanning classical and large network datasets.The authors classify the collection into two broad groups and provide full dataset details elsewhere.
- Classical networks: Classical datasets include karate, football, polblogs, polbooks, and the LFR benchmark with built-in topological communities.Their metadata groups represent factions, conferences, political alignment, or benchmark communities.
- Large and challenging networks: More challenging datasets include Debian dependencies, PGP email signatures, autonomous-system topology, Facebook university networks, Flickr, and LiveJournal.Their groups are based on tags, domains, user-entered attributes, user groups, or explicit memberships.
- Preprocessing: All networks were converted to undirected, unweighted graphs, and analysis retained only each network’s largest weakly connected component.Nodes outside that component were dropped.
- Preprocessing: Disconnected metadata groups were split into connected components, and groups with fewer than three members were dropped.This preprocessing reflects that community detection methods cannot associate disconnected groups.
B. Community detection methods
The study evaluates a varied collection of community detection methods, including algorithms for disjoint and overlapping communities and methods based on different structural principles.
- Method collection: The method collection includes algorithms from varied theoretical frameworks, with some supporting overlapping communities and others producing only disjoint communities.Method–dataset combinations that did not finish on the largest datasets were excluded.
- Algorithm families: Louvain uses greedy modularity optimization, while Infomap uses information compression of random walks.InfomapSingle is a variant that returns one partition rather than a hierarchy.
- Algorithm families: LinkCommunities clusters edges, CliquePerc scans rolling-clique regions, and Conclude grows communities using edge-centrality distances.These methods represent distinct structural strategies within the evaluated collection.
- Dataset characterization: The dataset table reports basic network properties, including ranges for fb100 networks and metadata groups and group-count ranges across amazon’s 11 hierarchical levels.These values are calculated after the indicated preprocessing.
- Algorithm families: Ganxis uses label propagation, while GreedyCliqueExp starts from small clique seeds and expands them with a local fitness function.The collection therefore includes both propagation- and clique-based approaches.
III. STRUCTURAL PROPERTIES OF NODE GROUPS FROM METADATA
Metadata groups exhibit structural properties that vary across datasets and with group size. Group link density generally decreases as groups grow, while embeddedness is especially low in large online social networks.
- Group size: Metadata-group size distributions are skewed across all datasets, with power-law tail exponents around −2.This resembles size-distribution behavior reported for communities detected in real networks.
- Link density: Link density decreases as metadata-group size increases across the datasets.The paper attributes this to sparse real graphs, where link counts scale roughly linearly with node counts while possible links scale quadratically.
- Embeddedness: Embeddedness measures the ratio of a group’s internal degree to its total degree and indicates how well the group is separated from the rest of the graph.Higher embeddedness means weaker connection to nodes outside the group.
- Link density: Figure 2 plots metadata-group link density against group size, with separate curves for each dataset.The key comparison is how the density–size relationship varies across datasets.
- Embeddedness: Some datasets, such as Amazon, contain groups with high embeddedness, whereas large online social networks have very low embeddedness that is fairly independent of group size.Low embeddedness makes metadata groups more difficult for community detection algorithms to identify.
IV. PARTITION LEVEL ANALYSIS
The study compares detected structural partitions with metadata groups using overlapping-cover NMI, while accounting for incomplete and mismatched node coverage. NMI grids also compare partitions produced by different algorithms and parameter settings.
- The analysis uses a generalized Normalized Mutual Information measure that supports comparisons between covers containing overlapping groups.The measure is adapted from information theory for comparing non-topological group structures with detected partitions.
- NMI comparisons use only nodes present in both partitions to handle mismatched coverage between metadata and detected groups.This best-case choice generally increases scores, while comparisons below 10% overlapping-node coverage are omitted.
- NMI grids display metadata-to-detected-partition similarity alongside similarity between structural partitions from different algorithms.Tiles are subdivided when methods return multiple hierarchical or parameter-dependent partitions.
A. PGP NMI grid analysis
The PGP NMI grid reveals substantial variation among algorithmic layers and generally modest similarity between detected structural partitions and metadata groups. Several methods produce internally similar layers, but cross-method and metadata alignment differs by algorithm and level.
- Structural partition comparisons: Most algorithms return layers that are quite similar to one another, including Infomap, Louvain, and Oslom.Cross-method comparisons nevertheless show selective alignment, such as Infomap’s highest layer with middle Louvain layers.
- Structural partition comparisons: LinkCommunities’ threshold 0.25 produces the most cross-algorithm-similar partitions, except relative to Copra and Oslom and partly CliquePerc.Lower Infomap, Louvain, and Oslom levels also tend to resemble partitions from other algorithms more closely.
- Metadata comparison: Metadata-to-detected-partition NMI scores are generally around 0.3, with lower Infomap and Louvain layers scoring better than their higher layers.Galgorithm-specific patterns include nearly identical Ganxis scores, while metadata intersections with higher CliquePerc layers cover under 10% of nodes and are discarded.
B. Overall NMI scores
Best-per-dataset-and-algorithm NMI scores show a clear dataset-size and benchmark pattern: recovery is strongest on LFR and small classical datasets, but weak on most large real-world networks. The results are not explained simply by failed optimization, since Louvain partitions can optimize modularity better than the metadata partition while still differing from it.
- Evaluation procedure: The reported best NMI scores are generally higher than scores from comparing individual partition levels because the analysis selects the best score for each dataset-algorithm pair.This selection reflects that real applications would not reveal which returned layer corresponds most truthfully to the desired partition.
- Overall pattern: Best-score NMI results divide into three groups: highest recall on LFR, fairly high scores on small classical datasets, and weak recovery on large datasets.The small classical set includes karate, football, polblogs, and polbooks.
- Overall pattern: Scores for most large networks rarely exceed 0.3 and sometimes fall below 0.1, while amazon is an exception with a much higher score.The amazon result is attributed to some metadata levels being partially recoverable.
- Interpretation: For as-caida, metadata, most-similar Louvain, and best-modularity Louvain partitions have modularity Q values of 0.3839, 0.5064, and 0.5176, respectively.Thus, the Louvain partitions have higher Q values than the metadata partition despite their comparison being part of the recovery analysis.
V. COMMUNITY LEVEL ANALYSIS
Community-level analysis evaluates whether individual metadata groups match detected communities using Jaccard-based recall and precision. Across large networks, these matches are usually weak, with benchmark graphs performing better and narrowing group classes rarely improving prediction.
- Measures: Jaccard score measures the node-set overlap between each known group and detected community, ranging from zero to one.The score uses intersection divided by union and indicates match quality.
- Measures: Recall assigns each known group its best Jaccard match among detected communities, while precision reverses this direction for each detected community.Recall evaluates known-group detection; precision evaluates correspondence of detected communities to known groups.
- Evaluation: The analysis compares every known group with every detected community, retaining matchings whose intersection covers more than 10% of graph nodes.Rank-Jaccard plots sort groups by score and summarize average recall or precision through the curve average.
- Results: Performance is usually close to zero in large networks, whereas classic benchmark graphs generally allow most communities to be recovered.Online social networks often show almost no metadata groups reflected in detected communities; amazon is a partial exception, with 20% of groups above 0.6 maximal recall Jaccard score.
- Results: LinkCommunities often has higher recall because it detects more communities, but its precision is very low; method performance otherwise varies by network.On the largest graphs, Louvain and InfomapSingle have worse recall than Oslom, while Oslom has lower precision.
- Results: Restricting analysis to groups selected by size, density, cohesiveness, or attribute type generally does not increase predictive power on most networks.The analysis includes fb100 attributes such as class year, field of study, and residence.
VI. CONCLUSIONS
The study systematically compares structural communities with metadata groups and finds a substantial, network-dependent mismatch across large real networks. Structural communities remain important for network dynamics, but current topological methods should not be expected to reliably reveal non-topological content.
- Conclusions: Community detection methods were systematically compared with metadata partitions on large real network datasets.The comparison covered both whole partitions and individual communities.
- Conclusions: Detected communities had low similarity to metadata groups, with low overlap in both directions.This pattern appeared across the methods used in the analysis.
- Conclusions: Restricting comparisons by group size, link density, or embeddedness did not produce major improvements.Results depended more on the network than on the specific method, and no method performed particularly well on any large dataset.
- Limitations: The conclusions depend on node classifications that may not always be reliable, although the diverse datasets showed a consistent message.The authors also note that other datasets could exhibit closer matches.
- Implications: The findings leave two possibilities: community models may need substantial modification, or metadata groups may not be recoverable from topology alone.Possible relevant structural features include degree correlations, loop density, and dense overlaps.
- Implications: Structural communities still affect network dynamics such as diffusion, synchronization, and opinion formation.The authors therefore distinguish the importance of detecting topological communities from their usefulness for inferring content.
Appendix A: Dataset descriptions
The study evaluates diverse real and benchmark networks, using metadata-defined groups and several community-detection methods. Dataset coverage is broad, but scalability and coverage limitations exclude some algorithm–dataset combinations and detected layers.
- Datasets: The collection spans social, information, technological, collaboration, software-dependency, Internet, political, and benchmark networks.Examples include Facebook university networks, Amazon copurchases, DBLP collaborations, AS-level Internet data, and synthetic LFR graphs.
- Datasets: Benchmark datasets include karate, football, political books, political blogs, and the synthetic LFR graph.Their metadata groups represent events such as a club split, conferences, political alignment, or benchmark communities.
- Datasets: fb100 contains 100 separate US university Facebook networks with metadata for dorm, majors, graduation year, former high school, and gender.These attributes form separate groupings for analysis; gender metadata were discarded.
- Methods: The evaluated methods include Infomap, InfomapSingle, and Louvain, alongside other methods in the broader collection.Infomap uses random-walk compression, while Louvain performs hierarchical modularity maximization.
- Methods: Some methods could not complete on the largest datasets, and detected communities smaller than three nodes were removed.These exclusions reflect computational restrictions and preprocessing choices.
- Coverage limitations: Higher-order CliquePerc layers and suboptimal LinkCommunities parameter settings covered less than 10% of dataset nodes.Such layers were marked separately, while slow algorithms were absent from some large-dataset results.
Appendix D: Additional community-level analysis
Additional analyses examine whether metadata-group detectability varies with group properties and metadata type. Detectability improves mainly for highly embedded groups, while broad results remain poor and precision shows no comparable embeddedness pattern.
- Analysis design: The analysis tests group size, density, and embeddedness as possible predictors of recall and precision.Known groups are matched to detected communities regardless of detected layer or group properties.
- as-caida group properties: Most methods detect large as-caida groups better than small ones, but their performance curves are generally close.Some algorithms show a more visible spread across group sizes.
- Dataset comparison: On the classic benchmark datasets, algorithms are relatively successful at detecting metadata groups, although cross-algorithm stability remains below expectation.For fb100, graduation-year groups were detected best among the reported features.
- as-caida group properties: Higher density appears associated with higher performance because density is correlated with inverse group size.The apparent advantage for less dense groups is therefore linked to group-size differences.
- as-caida group properties: Recall and precision are highest for the most embedded groups and decrease as embeddedness decreases.High embeddedness corresponds to groups that are more weakly attached to the rest of the network.
- fb100 metadata: Across fb100 metadata types, few groups are recovered by any method.LinkCommunities has higher recall but much lower precision because it returns many more detected groups.
- as-caida group properties: Precision does not show a particular embeddedness range with higher performance, unlike recall.The precision analysis finds no comparable embeddedness-dependent outliers.