Crawling the Community Structure of Multiplex Networks

Ricky Laishram, Jeremy D. Wendt, Sucheta SoundarajanAAAI 2019 · DOI

Introduction

Real-world networks are inherently complex and often multiplex, where nodes are connected through multiple types of relationships or "layers." For instance, a social network might include layers for email, physical meetings, and phone calls. A common research goal is to map the community structure of a specific layer. However, data acquisition is rarely uniform in cost; some layers are easily accessible ("cheap"), while others require significant resources or are "dark" ("expensive").

The central challenge addressed in this work is: How can we efficiently discover the community structure of an expensive network layer by leveraging information from cheaper, correlated layers?

The MultiComSample (MCS) Algorithm

The authors propose MultiComSample (MCS), a strategic crawling algorithm that treats network exploration as a multi-armed bandit problem. MCS operates in two distinct phases:

  1. Initial Sampling (RNDSample): The algorithm begins with random walks on the cheaper layers to establish a baseline understanding of the network's connectivity.
  2. Hierarchical Bandit Sampling (MABSample): This core component uses an $\epsilon$-greedy strategy across three hierarchical levels to optimize queries in the expensive layer:
  3. Layer Bandit: Selects the cheap layer most similar to the target expensive layer based on edge overlap.
  4. Community Bandit: Identifies which community within the selected layer is likely to provide the most structural information.
  5. Role Bandit: Determines the optimal node "type" (e.g., high-degree hubs or bridge nodes) to query next.

MCS is designed to handle both Reliable (RQR) and Unreliable (UQR) query models, the latter accounting for missing data common in real-world "dark" networks.

Experimental Evaluation

The performance of MCS was evaluated on diverse real-world multiplex networks, including Twitter datasets, High Energy Physics co-authorship (CaHepPhTh), and the NoordinTop terrorist network.

Performance comparison of MCS against baselines across three datasets under Reliable (RQR) and Unreliable (UQR) query models.

As shown in the results, MCS consistently outperforms standard baselines like Random Walk (RW) and its variants. Under tight budget constraints (e.g., querying only 20% of nodes), MCS achieves a 9% to 25% improvement in similarity scores in reliable settings. Its advantage is even more pronounced in unreliable settings, where it outperforms baselines by up to 49%.

Real-World Scalability

Beyond controlled datasets, the authors tested MCS against the live Twitter API. This test demonstrated the algorithm's ability to scale to massive, dynamic systems.

Real-world edge discovery rate on the live Twitter API comparing MCS to standard Random Walk (RW).

The real-world evaluation confirms that MCS discovers edges significantly faster than standard random walks, making it a practical tool for large-scale network analysis where API rate limits or costs are a factor.

Key Insights and Future Directions

The success of MCS highlights the power of cross-layer synergy. Even partially correlated cheap layers can serve as effective proxies for expensive ones. Furthermore, the algorithm's robustness to noise (UQR) makes it uniquely suited for sensitive domains like counter-terrorism or epidemiological tracking.

Future work may involve dynamically learning structural roles during the crawl, as the current implementation relies on a fixed set of predefined roles. Additionally, extending the framework to fully directed graphs could broaden its applicability to a wider range of information networks.

Summary updated

BibTeX
@inproceedings{laishram2019crawling,
  author = {Ricky Laishram and Jeremy D. Wendt and Sucheta Soundarajan},
  title = {{Crawling the Community Structure of Multiplex Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.3301168},
}
Figure