Title: Optimizing Node Discovery on Networks: Problem Definitions, Fast Algorithms, and Observations,
Abstract: Many people dream to become famous, YouTube video makers also wish their
videos to have a large audience, and product retailers always hope to expose
their products to customers as many as possible. Do these seemingly different
phenomena share a common structure? We find that fame, popularity, or exposure,
could be modeled as a node's discoverability on some properly defined network,
and all of the previously mentioned phenomena can be commonly stated as a
target node wants to be discovered easily by the other nodes in the network. In
this work, we explicitly define a node's discoverability in a network, and
formulate a general node discoverability optimization problem, where the goal
is to create a budgeted set of incoming edges to the target node so as to
optimize the target node's discoverability in the network. Although the
optimization problem is proven to be NP-hard, we find that the defined
discoverability measures have good properties that enable us to use a greedy
algorithm to find provably near-optimal solutions. The computational complexity
of a greedy algorithm is dominated by the time cost of an oracle call, i.e.,
calculating the marginal gain of a node. To scale up the oracle call over large
networks, we propose an estimation-and-refinement approach, that provides a
good trade-off between estimation accuracy and computational efficiency.
Experiments conducted on real-world networks demonstrate that our method is
thousands of times faster than an exact method using dynamic programming,
thereby allowing us to solve the node discoverability optimization problem on
large networks.