Abstract
Traditional influence maximization (IM) assumes a complete map of a social network is available to identify optimal seed nodes for information diffusion. However, in real-world applications such as public health interventions, mapping a network is often the most significant bottleneck. This paper introduces the concept of exploratory influence maximization and proposes ARISEN, an algorithm that identifies influential individuals by querying only a tiny fraction of an unknown network. By leveraging the inherent community structure of human social networks, ARISEN achieves near-optimal influence spread with minimal data collection effort.
Introduction
In fields like international development or public health, practitioners aim to spread critical information—such as HIV prevention strategies or improved farming techniques—by identifying "peer leaders." Standard IM algorithms require a complete graph of the social network as input. For vulnerable populations or regions with limited digital footprints, gathering this data via exhaustive surveys is considered impractical and labor-intensive.
This research addresses the gap between theoretical IM and practical constraints. The authors prove that while finding influencers in a completely random unknown graph is mathematically impossible without near-total visibility, the problem becomes solvable when the network possesses a predictable structure, specifically dense clusters or communities.
Methodology: The ARISEN Algorithm
The authors formalize the Jump-Crawl model for network exploration. In this model, an algorithm can either "jump" to a random node in the population or "crawl" by asking a visited node to reveal its neighbors. Each action carries a cost, necessitating an information-efficient approach.
ARISEN (Algorithm for Real-time Influence-maximization in Socially-Evolved Networks) exploits Community Structure through a four-step process:
- Sampling: Selecting a set of random starting nodes via "jumps."
- Local Exploration: Performing short random walks ("crawls") around those nodes to map local neighborhoods.
- Weighting: Calculating a weight for each sampled node based on these local subgraphs to estimate its global influence potential.
- Selection: Choosing the final seed nodes based on these calculated weights.
The approach is grounded in the Stochastic Block Model (SBM), a statistical framework for generating graphs with realistic community densities.
Experimental Evaluation
ARISEN was validated using both synthetic data and high-stakes real-world social networks:
- Homeless Youth: Social tie data from shelters where peer-led health interventions are common.
- Rural Indian Villages: Household networks from a village setting.
- Synthetic Networks: Graphs generated via SBM to test the algorithm under controlled levels of community density.
Key Results
ARISEN was compared against common field heuristics, such as random node selection and the "friends of friends" approach (selecting the highest-degree neighbor of a random node).
As shown in the results for the "india-2" dataset, ARISEN consistently outperformed all baselines. Notably, the algorithm achieved a significant fraction of the "Global Optimum" (the theoretical maximum influence if the entire network were known) while querying only a small fraction ($K/n$) of the total nodes. The algorithm also proved robust even when the underlying parameters of the community structure were estimated rather than known perfectly.
Discussion and Future Work
The research highlights that information efficiency—how much of the graph must be seen—is as critical as computational efficiency. By focusing on local subgraphs, ARISEN demonstrates that one does not need to know how distant communities connect to identify local hubs that drive global influence.
Future work will focus on providing full theoretical performance bounds and extending the model to complex contagions, where influence requires multiple exposures. Additionally, the authors aim to adapt the algorithm for dynamic networks where social ties shift over time, presenting a moving target for exploratory maximization.
Summary updated