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 col-laborative 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 submodu-lar 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 neigh-bors has been chosen.  We then present a general algorithm NET E XP 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