Abstract
How should we gather information in a network, where each node's visibility is limited to its local neighborhood? This problem arises in numerous real-world applications, such as surveying and task routing in social networks, team formation in collaborative networks and experimental design with dependency constraints. Often the informativeness of a set of nodes can be quantified via a submodular utility function. Existing approaches for submodular optimization, however, require that the set of all nodes that can be selected is known ahead of time, which is often unrealistic. In contrast, we propose a novel model where we start our exploration from an initial node, and new nodes become visible and available for selection only once one of their neighbors has been chosen. We then present a general algorithm NETEXP for this problem, and provide theoretical bounds on its performance dependent on structural properties of the underlying network. We evaluate our methodology on various simulated problem instances as well as on data collected from social question answering system deployed within a large enterprise.
Introduction: The Challenge of Local Visibility
In many real-world scenarios—like routing a technical question through a corporate social network or a web crawler discovering new pages—we lack a global view of the network. Instead, we operate under local visibility: we only know about the nodes we have already reached and their immediate neighbors.
Standard submodular optimization techniques typically assume that the entire ground set of items is known upfront. This paper addresses the "active exploration" challenge: maximizing a utility function (e.g., finding a team of experts) when candidates must be discovered incrementally. This introduces a fundamental explore-exploit dilemma: should one select a node for its immediate value (exploitation) or a "hub" node that might reveal more valuable nodes later (exploration)?
The NETEXP Algorithm
To navigate this trade-off, the authors propose NETEXP (Network Exploration). The algorithm intelligently balances two strategies using a randomized interleaving approach:
- Exploration: To expand the visible network, NETEXP employs a look-ahead strategy. Rather than simply picking high-degree nodes, it searches for "chains" of nodes (typically 2 steps deep) that maximize the exposure of previously unseen parts of the graph. This helps build a "backbone"—a connected dominating set—efficiently.
- Exploitation: The algorithm selects nodes that provide the highest immediate marginal gain to the utility function among currently visible nodes.
- Interleaving: At each step, the algorithm flips a biased coin (with probability $\epsilon$) to decide whether to explore or exploit.
Theoretical analysis shows that the size of the set selected by NETEXP is bounded by network properties, such as maximum degree and the size of the smallest backbone, relative to the optimal solution.
Experimental Evaluation
The researchers evaluated NETEXP against three distinct types of data:
- Erdős-Rényi Random Graphs: Uniform network structures used for baseline testing.
- Preferential Attachment Graphs: Scale-free networks mimicking the "rich-get-richer" connectivity of real-world social networks.
- IM-an-Expert (IMX): A real-world Microsoft enterprise social Q&A dataset with 5,000 experts embedded in a tree of 180,000 nodes.
Key Results and Insights
- Superior Performance: NETEXP significantly outperformed baselines that focused solely on exploration (high-degree nodes) or exploitation (best visible nodes).
- Real-World Efficacy: On the IMX dataset, NETEXP demonstrated a substantial "utility gap" over other methods, proving its effectiveness in large-scale organizational searches.
- The Power of Look-ahead: Looking just two steps ahead ($l=2$) proved highly effective for navigation, mirroring human social strategies.
- Robust Parameterization: A simple 50/50 split ($\epsilon = 0.5$) proved robust across diverse network types.
- Small-World Efficiency: In preferential attachment models, the cost of local visibility is polylogarithmic, allowing the algorithm to find high-value nodes very quickly.
Conclusion and Future Work
NETEXP provides a principled framework for information gathering under local visibility constraints. While effective, future work could address the computational costs of deeper look-aheads in dense networks and explore scenarios with noisy utility estimates or dynamic network structures. Adaptive exploration, where $\epsilon$ is adjusted based on local network density, remains a promising avenue for further optimization.
Summary updated