Source-linked AI summary
Quantifying social group evolution
Gergely Palla, Albert-Laszlo Barabasi, Tamas Vicsek
TL;DR
Community dynamics are difficult to characterize because overlapping groups continually change membership. The paper combines clique-percolation community detection with an evolution-matching algorithm to study scientist-collaboration and mobile-phone networks, finding that small groups persist through stable membership whereas large groups persist through turnover.
Problem
Community evolution involves changing membership, but the dynamics of small and large groups remain insufficiently characterized.
Method
The paper applies weighted clique percolation and matches communities across time using joint graphs to track overlapping community evolution.
Results
Small communities have longer lifetimes with nearly unchanged membership, whereas large communities persist longer when their membership changes continuously.
Takeaways & Limitations
Community stability follows different patterns by scale: strong persistent relationships support small groups, while ongoing member replacement supports large institutions.
Abstract
from arXiv · showhide
The rich set of interactions between individuals in the society results in complex community structure, capturing highly connected circles of friends, families, or professional cliques in a social network. Thanks to frequent changes in the activity and communication patterns of individuals, the associated social and communication network is subject to constant evolution. Our knowledge of the mechanisms governing the underlying community dynamics is limited, but is essential for a deeper understanding of the development and self-optimisation of the society as a whole. We have developed a new algorithm based on clique percolation, that allows, for the first time, to investigate the time dependence of overlapping communities on a large scale and as such, to uncover basic relationships characterising community evolution. Our focus is on networks capturing the collaboration between scientists and the calls between mobile phone users. We find that large groups persist longer if they are capable of dynamically altering their membership, suggesting that an ability to change the composition results in better adaptability. The behaviour of small groups displays the opposite tendency, the condition for stability being that their composition remains unchanged. We also show that the knowledge of the time commitment of the members to a given community can be used for estimating the community's lifetime. These findings offer a new view on the fundamental differences between the dynamics of small groups and large institutions.
METHODS
The method identifies communities as connected unions of adjacent k-cliques and tracks their evolution by analyzing joint graphs formed from consecutive network snapshots.
- Locating communities: Communities are unions of k-cliques connected through chains of overlaps sharing k−1 nodes.In weighted networks, links weaker than the threshold w* are ignored; the method uses k and w* as parameters.
- Locating communities: For weighted networks, community detection depends on the k-clique size k and weight threshold w*.The threshold excludes links weaker than w*, while k determines the clique size used to construct communities.
- Identifying evolving communities: The evolution algorithm constructs a joint graph from the union of links in each pair of consecutive snapshots and extracts its CPM community structure.This joint structure relates communities identified at time t and t+1.
Supplementary Information is linked to the online version of the paper at www.nature.com/nature · Figure legends
The figure legends describe community structure and evolution in co-authorship and phone-call networks, focusing on age, persistence, stationarity, membership turnover, and inter-community links.
- Figure legends: For small co-authorship communities, the peak in <τ*> lies near ζ = 1, whereas for large communities it shifts toward lower ζ values.The communities still alive at the dataset’s final time step were excluded from this investigation.
- Figure legends: The same stationarity-dependent pattern is observed in the phone-call network, with the highlighted white line marking optimal stationarity.Panels c and d show the corresponding results for the two networks.
- Figure legends: Figure 1 depicts local community structure around randomly selected nodes in both the co-authorship and phone-call networks.Panel c compares the average largest same-zip-code subset in phone-call communities with random sets.
- Figure legends: Larger communities are on average older, as shown by the size dependence of normalized community age.The plotted quantity is the age τ for communities of size s divided by the average age of all communities <τ>.
- Figure legends: The legends analyze community autocorrelation across different sizes using two-week time units.The autocorrelation function C(t) is averaged over communities and initial times t0.
- Figure legends: Figure 3 encodes community turnover by distinguishing old members, newcomers, and members abandoning the community at the next time step.Column height represents actual community size; departing old and new members use different colors.
- Figure legends: Figure 4 relates member departure and community disintegration to members’ aggregated link weights within and outside their communities.Panel a uses p_l as a function of wout/(win + wout), while panel b gives p_d as a function of an aggregated-weight ratio.