Beyond Single Metrics: An ANP-Based Multicriteria Approach to Centrality in Social Networks

TL;DR

Identifying influential nodes in Online Social Networks (OSNs) is critical for viral marketing and information diffusion. However, relying on a single metric like "Degree" or "Betweenness" is often misleading. This paper proposes a decision-making framework using the Analytic Network Process (ANP) to synthesize multiple centrality measures, resulting in more robust and efficient identification of truly "central" users.

Problem & Motivation: The Limitation of One-Dimensionality

In the study of graph theory applied to social systems, Centrality Measures (CMs) are the standard toolkit. However, the authors argue that each CM—be it Degree (popularity), Closeness (proximity), or Betweenness (gatekeeping)—only offers a partial perspective.

The structural complexity of modern OSNs means that a node might have many connections (high degree) but be located in a peripheral cluster, limiting its global influence. Conversely, a node with few connections might sit on a bridge between two massive communities (high betweenness). The authors’ core insight is that centrality is a multi-dimensional construct; thus, selecting the most influential node should be treated as a Multiple Criteria Decision Making (MCDM) problem.

Methodology: The Analytic Network Process (ANP)

The proposed method moves away from simple heuristics and towards a formal mathematical framework provided by ANP. Unlike the simpler Analytic Hierarchy Process (AHP), ANP accounts for interdependencies between criteria.

1. The Structure

The model identifies three clusters:

• Goal (G): To select the most central node.
• Criteria (C): Degree, Betweenness, and Closeness.
• Alternatives (A): The actual nodes in the network.

2. The Supermatrix Calculation

The relationships are modeled using an unweighted supermatrix ($S_U$), which captures how each CM influences the others and how nodes perform under each CM.

The process then involves:

1. Normalization: Creating a stochastic weighted supermatrix ($S_W$).
2. Convergence: Raising the matrix to a high power ($S_L=S_W^k$) until the values stabilize. This represents the long-term relative influence weights of each node.

Experiments: Real-World Performance

The authors validated their method using four real OSN subgraphs from Facebook and Orkut. They simulated an "advertisement spreading" scenario where a node is selected and the number of reached users is tracked over several rounds.

• Baseline Comparison: They compared the ANP method against individual CMs (Degree, Closeness, Betweenness) and a Random selection.
• Network Metrics:

Key Result: The "Friends of Friends" Effect

While Degree Centrality often performs well in the very first round (it hits the most immediate neighbors), the ANP method begins to dominate from the second round onwards. This is because the ANP approach selects nodes that aren't just popular, but are strategically positioned to reach "friends of friends" more effectively.

Critical Analysis & Conclusion

Takeaway

The paper successfully demonstrates that a multicriteria approach provides more insurance against the "blind spots" of individual metrics. By using ANP, researchers can capture the synergy between different types of structural Importance.

Limitations

1. Computational Cost: Calculating the limit supermatrix for very large graphs (millions of nodes) is computationally expensive, as $S_U$ grows with the number of nodes.
2. Global Knowledge: The method currently requires full knowledge of the network topology, which is rarely available in real-time streaming social data.

Future Outlook

Future research should focus on local ANP approximations—calculating influence based on a node's local neighborhood rather than the entire graph—to make this multicriteria approach viable for massive-scale industry applications.