Source-linked AI summary
Uncovering space-independent communities in spatial networks
Paul Expert, Tim Evans, Vincent D. Blondel, Renaud Lambiotte
TL;DR
Spatial constraints can dominate topology and make standard community detection recover geographic rather than underlying organization. The paper modifies modularity with a distance-aware null model, and tests it on mobile-phone data and spatial benchmarks, where it reveals non-spatial community structure more clearly.
Problem
Spatial constraints strongly affect connectivity, while standard network tools and modularity can overlook space and produce communities dominated by geographic factors.
Method
The paper incorporates node positions into modularity’s null model through a distance-dependent deterrence function measured from network data.
Results
The spatial modularity recovers an almost perfect Belgian bipartition reproducing linguistic separation, while standard modularity uncovers 18 spatially compact modules.
Takeaways & Limitations
Factoring out spatial effects can reveal hidden structural or cultural similarities and supports quantitative exploration of spatially distributed networks.
Takeaways & Limitations
Absolute modularity values from the standard and spatial null models cannot be directly compared, and modularity retains known resolution and landscape-degeneracy limitations.
Abstract
from arXiv · showhide
Many complex systems are organized in the form of a network embedded in space. Important examples include the physical Internet infrastucture, road networks, flight connections, brain functional networks and social networks. The effect of space on network topology has recently come under the spotlight because of the emergence of pervasive technologies based on geo-localization, which constantly fill databases with people's movements and thus reveal their trajectories and spatial behaviour. Extracting patterns and regularities from the resulting massive amount of human mobility data requires the development of appropriate tools for uncovering information in spatially-embedded networks. In contrast with most works that tend to apply standard network metrics to any type of network, we argue in this paper for a careful treatment of the constraints imposed by space on network topology. In particular, we focus on the problem of community detection and propose a modularity function adapted to spatial networks. We show that it is possible to factor out the effect of space in order to reveal more clearly hidden structural similarities between the nodes. Methods are tested on a large mobile phone network and computer-generated benchmarks where the effect of space has been incorporated.
1 Social Networks and Space
Social-network communities reflect both structural mechanisms and spatial or social proximity, which can mingle distinct forces and obscure homophilious effects and hidden similarities.
- Social ties reflect structural mechanisms such as triadic closure, reciprocity, and reinforcement, alongside homophily and focus constraint.
- Geographic proximity creates opportunities for face-to-face contact and encounters, making it a dominant factor in focus constraint.
- Homophily and focus constraint can reinforce one another because frequent contact promotes uniformity and similar individuals often share neighborhoods.
- Community detection mingles potentially antagonistic forces, limiting conclusions about the mechanisms underlying uncovered modules.
- The paper asks whether known spatial positions can be used to remove space’s effect and clarify homophilious and hidden structural or cultural similarities.
2 Modularity and Space
The paper adapts modularity for spatial networks by replacing the standard structural null model with one that incorporates distance-dependent expectations. The resulting measure favors connections stronger than expected at a given distance and can recover non-spatial organization.
- Community detection partitions nodes into locally dense modules without specifying their number or size in advance, using modularity to assess within-community link abundance.
- Modularity compares observed within-community weights with expected weights from a null model constrained by known network information.
- The standard Newman-Girvan null model preserves node strengths and assumes a well-mixed network where connectivity determines link probabilities.
- The spatial null model incorporates node positions and uses a distance-dependent deterrence function measured directly from data, while conserving total network weight.
- Spatial modularity favors node pairs more connected than expected at their distance, thereby tending to identify communities driven by non-spatial factors.
- The spatial constraint can be relaxed to tune the characteristic network size and the resolution at which communities are uncovered.
- In empirical data, distances are binned to smooth the deterrence function, with bin-size dependence examined separately.
3 Numerical validation
The spatial modularity method is evaluated on Belgian mobile-phone data and controlled spatial benchmarks. It recovers linguistically meaningful communities and remains accurate across parameter settings where standard Newman–Girvan modularity fails.
- Belgian mobile phone data: The Belgian network contains 571 communes, with calls aggregated over six months and commune client counts denoted by N_i.The 19 Brussels communes are merged into one.
- Belgian mobile phone data: NG modularity yields 18 spatially compact communities, whereas Spa modularity yields 31 communities and an almost perfect linguistic bipartition.The two largest Spa communities contain about 75% of communes.
- Belgian mobile phone data: Spa assigns Brussels to the French-speaking community despite its location in Flanders, consistent with Brussels being approximately 80% French-speaking.Smaller communities arise partly from hard partitioning, which cannot represent overlapping communities.
- Statistical tests: The original network is significantly more modular than weight-randomized networks, and the z-score is an order of magnitude larger for Spa than for NG.Spatial randomization produces a negative z-score because randomizing node positions loses useful information.
- Statistical tests: Partitions found by NG and Spa are genuinely different, while weight-randomized partitions show VI values of 0.09 for NG and 0.58 for Spa.In the original data, the VI between NG and Spa partitions is 0.38; Spa becomes similar to NG when space is irrelevant, with VI 0.16 in the relevant randomized networks.
- Gravity Model Benchmark: On spatial benchmarks, Spa outperforms NG increasingly as link density rises and perfectly identifies communities as ρ → ∞ for every λ_different < 1.NG fails even for small λ_different, whereas Spa remains accurate across a wide parameter range.
4 Discussion
The paper adapts modularity to account for spatial constraints, enabling spatial networks to reveal non-spatial structural patterns. The framework is intended for broad spatially distributed systems and can use physical or attribute-based separation.
- 4 Discussion: The method incorporates spatial location into the modularity null model to uncover unknown attributes such as homophilious relations.It compares empirical connectivity with expectations that include non-structural attributes.
- 4 Discussion: The framework is proposed for quantitative exploration of spatially distributed systems across a wide range of networks.
- 4 Discussion: Separation can be defined by node attributes rather than physical distance, such as age differences in social networks.The paper states that this can reveal other relationship types with little extra computational effort.
- 4 Discussion: The approach can support partitioning when modules are pervasively overlapping by incorporating relevant information.
Supplementary Information
The supplementary material defines the spatial null model through distance-dependent empirical interactions and relates it to the standard Newman-Girvan model. It also describes interpolation between spatial and topological expectations.
- Supplementary Information: The supplement contains analyses of null models, multiscale modularity, datasets, bin-size effects, and randomized significance tests.
- Supplementary Information: The spatial null model uses node importance and physical distance, unlike the standard model, whose connection probability is proportional to degree.
- Supplementary Information: The spatial null model preserves the total interaction weight between nodes at each distance.For the mobile phone network, Ni is the number of clients in commune i, and f(d) is estimated from empirical data.
- Supplementary Information: When Ni equals degree and f(d) is distance-independent, the spatial null model reduces to the Newman-Girvan null model.
- Supplementary Information: A mixing parameter ξ interpolates between the spatial and standard null models.
B Multi-scale Modularity
The paper extends spatial modularity to examine nested communities, while noting that single-partition modularity is inadequate for multiscale systems. Belgian mobile-phone communities show dominant linguistic structure with finer regional subdivisions.
- B Multi-scale Modularity: Standard modularity produces one partition, which is unsatisfactory for systems containing nested modules at different scales.
- B Multi-scale Modularity: Increasing γ decreases the characteristic size of modules in the optimal partition.
- B Multi-scale Modularity: Q = 0.019 and z score = 91 for the Northern community, versus Q = 0.064 and z score = 425 for the Southern community.The whole-system z score is 803, and the Southern value is attributed to bilingual Brussels.
- B Multi-scale Modularity: The decomposition confirms linguistic division as dominant while revealing finer regional subdivisions.Examples include local dialects and cultural differences between cosmopolitan Brussels and rural Walloon areas.
- B Multi-scale Modularity: Figure 3 decomposes the two main Belgian communities into sub-communities, with node size proportional to commune client counts.
C Weights in the Belgian mobile phone data
The Belgian mobile-phone network aggregates calls between communes while retaining heterogeneity in commune size. This choice preserves user-level weighting and links commune-level modularity to constrained user-network partitions.
- C Weights in the Belgian mobile phone data: The network uses Aij as the total number of calls between users in communes i and j.It is a fully connected 571-commune matrix aggregated from customer-customer communication data.
- C Weights in the Belgian mobile phone data: The analysis retains strong commune-size heterogeneity rather than normalizing weights by NiNj.The authors state that modularity should account for node importance in the null model.
- C Weights in the Belgian mobile phone data: Aggregating commune links gives each user equal importance and makes commune-level modularity equivalent to optimizing the user network under a same-commune constraint.
- C Weights in the Belgian mobile phone data: Figure 4 shows commune sizes spanning several orders of magnitude between the largest and smallest communes.
D Size of the communities
Spa produces two dominant communities and many negligible ones, whereas NG produces communities of broadly similar size. This pattern holds whether size is measured by communes or customers.
- Spa’s two largest communities account for about 75% of all communes.
- Spa finds two large communities while the remaining communities are negligible in size.
- NG finds communities with broadly similar sizes rather than Spa’s highly concentrated size distribution.
- The size comparison uses commune counts in Figure 5 and customer counts in Figure 6.
- Measured by customers, Spa again assigns more than 70% of the population to its two largest communities.
E Binning distance
The spatial modularity analysis evaluates distance effects across multiple bin sizes and selects 5 km as the most representative choice. The deterrence function is also compared before and after position randomization.
- Eight distance-bin sizes from 1 to 200 km are evaluated to determine an appropriate binning scale.
- The deterrence function is plotted for multiple bin sizes ranging from 1 km to 200 km.
- The 5 km deterrence function is compared between the original network and a network with randomized positions.
- 5 km is the bin size closest to all others and therefore the most representative of the system.
F Gravity Model Benchmark: Averages
Averaging over 100 benchmark realizations shows that Spa reconstructs the planted communities perfectly across a substantially broader parameter range than NG.
- Spa offers perfect reconstruction over a significantly broader range of interaction-strength and link-density parameters than NG.
- The averaged benchmark evaluates recovered partitions against known community structure over interaction strength and link density.
G Bipartition of the mobile phone data
For the Belgian mobile phone network, Spa yields a North–South bipartition consistent with the country’s linguistic division, while NG favors Brussels and its surroundings versus the rest of Belgium.
- The spectral bipartition comparison indicates a positive second eigenvalue for NG but a negative one for Spa.
- Spa recovers the correct communities across a much wider parameter range than NG in the spatial benchmark.
- Spa gives a North–South bipartition consistent with Belgium’s linguistic division, whereas NG selects Brussels and its neighborhood against the rest of the country.
- The benchmark visualizes 40 nodes with λdifferent = 0.5 and displays the 20% of links having the highest probabilities.