Evolution of Social Networks: The Power of Clique-Superposition

TL;DR

How do millions of local interactions form the global structure of a social network? This paper moves beyond simple node-to-node link models by proposing the Clique-superposition model. By viewing network evolution as a series of social events (cliques), the authors successfully replicate new weighted patterns observed in DBLP and social bookmarking data that previous SOTA generators missed.

Background: Beyond Preferential Attachment

While the classic Barabási-Albert (BA) model explained the "rich-get-richer" phenomenon through degree-based preferential attachment, it lacked a sociological basis. In reality, we don't just "match" with a stranger; we meet groups of people through shared events—a meeting, a research paper, or a tag on a resource.

The authors pivot to Scott Feld's theory: a social network is the result of superposed cliques of different sizes. This "event-driven" intuition suggests that the fundamental unit of growth isn't an edge, but a subgraph.

New Patterns in Weighted Networks

Before building their generator, the authors identified three new "signatures" of real-world networks using datasets from CiteULike, Delicious, and DBLP:

1. Weight Distribution Power Law (WDPL): The frequency of edge weights (how many times two people interact) follows a power law.
2. Strength Distribution Power Law (SDPL): Node strength (sum of weights of adjacent edges) acts as a microscopic indicator of importance, also following a power law.
3. Edge Weight Addition: The probability of an interaction frequency increasing decreases as the current frequency or the addition value increases.

Methodology: The Clique-Superposition Model

The core mechanism is elegant: in each evolution step, the model either adds a new node or selects an existing node (a "newcomer") and connects it to a size-$k$ clique.

Figure 1: The model treats social networks as projections of hidden actor-event affiliation networks.

The Engine: KEWLS Algorithm

To find these cliques efficiently in a growing graph, the authors use the KEWLS (k-Edge weighting Local Search) algorithm. This allows the generator to find complete subgraphs of size $k$ (sampled from a persistent power law) and link them to the newcomer. This naturally creates a "rich-get-richer" effect because nodes in larger cliques are mathematically more likely to be part of the sub-cliques chosen for new connections.

Experimental Validation

The model was tested against varying parameters ($p_{node}$ for growth pace and $\beta$ for clique size distribution).

Figure 2: The synthetic networks successfully replicate the Power Law distributions (WDPL/SDPL) found in real-world data.

Key Findings:

• Densification: The generated graphs satisfy the Densification Power Law ($E(t)\propto N(t{)}^{\alpha }$), meaning the network gets denser over time.
• Clustering: Unlike random graphs, the Clique-superposition model maintains a high clustering coefficient, a hallmark of "Small World" social structures.
• Robustness: The parameter $\beta$ (clique size distribution) had a stable effect, showing the model is robust to different types of event distributions.

Conclusion and Future Outlook

The Clique-superposition model serves as a bridge between sociology and graph mining. By focusing on the event as the catalyst for the link, it provides a more authentic blueprint for generating synthetic social data.

Limitations: The model currently focuses on undirected networks. The next frontier involves extending this to directed graphs (e.g., following/follower relationships) and exploring how these clique structures influence information diffusion or community detection.

Ref: Yan, F., et al. "Evolution of Social Networks – New patterns and a new generator." Peking University.