Abstract: This paper addresses the challenge of maximizing a submodular utility function in a network where node visibility is restricted to local neighborhoods. We introduce NETEXP, an algorithm that balances exploration of the network structure with exploitation of known high-value nodes. Evaluated on synthetic and real-world datasets, NETEXP demonstrates superior performance compared to pure exploration or exploitation strategies, effectively navigating unknown network topologies to find optimal information sources.
The Challenge of Local Visibility
Most submodular optimization problems assume a "global view" where all potential elements are known. However, in real-world networks like social platforms or corporate directories, visibility is often local. One only discovers new nodes by interacting with their neighbors. This creates a fundamental trade-off: should one select a known "good" node (exploitation) or a node that might reveal even better options (exploration)?
As illustrated above, starting from an initial set $S$, the algorithm can only "see" nodes within a certain distance ($l_1, l_2$). To reach high-value nodes like $v_{12}$, it must first select intermediate "bridge" nodes that expand its horizon.
The NETEXP Algorithm
The proposed NETEXP (Network Exploration) algorithm addresses this by strategically interleaving two steps:
- Exploration: Selecting nodes that maximize "exposure" to unseen parts of the network, often targeting hubs or high-degree nodes to unlock the map.
- Exploitation: Selecting nodes within the currently visible set that offer the highest marginal utility (e.g., the most relevant expert).
A parameter $\epsilon$ controls this balance. Additionally, NETEXP utilizes "look-ahead chains" to build a backbone of the network, ensuring the search doesn't get trapped in local clusters.
Experimental Evaluation
The authors evaluated NETEXP on three distinct types of networks:
- Erdős-Rényi Random Graphs: A standard baseline for random connectivity.
- Preferential Attachment Models: Synthetic networks that mimic the "rich-get-richer" structure of real social networks.
- IM-an-Expert (IMX): A real-world dataset from a Microsoft social Q&A system, involving 5,000 experts within a 180,000-node organizational tree.
Key Results and Insights
- Superior Utility: In all tests (Figures 2a-c), NETEXP significantly outperformed pure strategies. Pure exploitation (VAL) hits a plateau because it gets stuck in local neighborhoods. Pure exploration (DEG) eventually finds the best nodes but is inefficient in the short term.
- The "Sweet Spot": As shown in the parameter analysis (Figure 2f), there is an optimal value for $\epsilon$ (around 0.5) that maximizes utility per node selected. This confirms that a balanced approach is essential for efficiency.
- Small-World Efficiency: The researchers proved that in "small-world" networks, NETEXP can reach high-value nodes in polylogarithmic steps, meaning the penalty for local visibility is manageable in most human social structures.
Conclusion
NETEXP provides a robust framework for active exploration in networks. By treating exploration as a necessary investment to enable future exploitation, it achieves performance competitive with "omniscient" algorithms that have full network visibility. Future work will explore handling noisy utility observations and dynamic exploration rates that adapt as the network map becomes more complete.
Summary updated