Spanning Graphs: A Structural Shortcut to Maximum Social Influence
2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining
This paper introduces a novel approach to the Influence Maximization (IM) problem by extracting acyclic spanning graphs from social networks to eliminate feedback loops. The authors propose two main algorithms, SCG-algorithm and SDG-algorithm, which utilize closeness centrality to construct structured paths that optimize influence spread under the Independent Cascade Model (ICM).
TL;DR
Maximizing influence in a social network is often hampered by the complex, "loopy" nature of human connections. This paper proposes a radical simplification: strip the cycles. By extracting an acyclic spanning graph—essentially a backbone of the network—and selecting seeds from this structure, the authors achieve superior influence spread compared to using the raw, noisy graph.
The Problem: The Loop Trap
Influence Maximization (IM) aims to find "seed" nodes that trigger the largest cascade of information. Since the seminal work of Kempe et al. (2003), it has been known that this is NP-hard.
The authors identify a specific inefficiency in current heuristics: Feedback Loops. In models like the Independent Cascade Model (ICM), once a node is active, it stays active. However, in a dense graph, influence often cycles back to already-active nodes. This "transitivity" confuses standard centrality measures, leading them to pick seeds that have high local density but poor global reach.
Methodology: Pruning for Performance
The authors propose that by removing cycles, we can focus on the most direct paths of propagation. They introduce two primary algorithms:
- SCG-Algorithm (Spanning Connected Graph): Designed for undirected, connected networks. It uses Closeness Centrality to find the most "central" node and builds a spanning tree level by level.
- SDG-Algorithm (Spanning Di-Graph): Designed for directed and potentially unconnected networks, resulting in a spanning forest.
Core Logic
The construction starts at the node with the minimum closeness centrality (the "physical" center of the manifold). Edges are only preserved if they link to a node not yet reached in the spanning process, effectively turning the network into a directed hierarchy.
Above: An example of a Dolphin social network transformed into its acyclic backbone (Tree).
Experimental Evidence
The authors tested their hypothesis on two significant datasets: com-Amazon (334k nodes) and Enron Email (36k nodes). They compared seed sets derived from the original graph vs. the acyclic spanning graph using three heuristics:
- Degree Heuristic
- Degree Discount
- Diffusion Degree
Key Result: Spanning Graphs Win
In every test case, the spanning graph seeds outperformed the original graph seeds. This suggests that the "structural noise" of cycles actually leads traditional heuristics to make suboptimal seed choices.
The chart clearly shows the influence spread (Y-axis) of the spanning graph approach (T) consistently exceeding the initial graph (G) across different seed set sizes (k).
Critical Insight & Conclusion
Why does this work? By forcing the graph into a tree structure, the algorithm emphasizes long-range reach over local clustering. Standard heuristics are often "tricked" by highly clustered nodes that have many neighbors but are isolated from the rest of the network. The spanning graph approach ensures that seeds are chosen based on their ability to move information across distinct "levels" of the network.
Takeaway: When dealing with massive social data, simplifying the topology to an acyclic state is not just a computational convenience—it's a strategic advantage for identifying the true drivers of viral growth.
Future Work: Integrating this acyclic extraction with more modern "Continuous-Time" models or investigating how it handles dynamic networks where edges appear and disappear over time.