Optimizing node discovery on networks: problem definitions, fast algorithms, and observations

DOI10.1016/J.INS.2018.10.036MaRDI QIDQ2201666zbMATH OpenOpenAlexFDO

Authors Junzhou Zhao, Pinghui Wang, John C. S. Lui

Publication date 29 September 2020

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.04307

zbMATH Keywords

random walkgreedy algorithmMCMC simulationsubmodular/supermodular set function

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

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.

Recommendations

• A fast and effective heuristic for discovering small target sets in social networks
• Discovering small target sets in social networks: a fast and effective algorithm
• scientific article; zbMATH DE number 6474901
• Maximizing social influence in nearly optimal time
• Structural search and optimization in social networks

Cites work

• scientific article; zbMATH DE number 3934150 (Why is no real title available?)
• scientific article; zbMATH DE number 3580314 (Why is no real title available?)
• scientific article; zbMATH DE number 878897 (Why is no real title available?)
• A note on maximizing a submodular set function subject to a knapsack constraint
• A note on maximizing the spread of influence in social networks
• An analysis of approximations for maximizing submodular set functions—I
• Axioms for Centrality
• I/O-efficient calculation of \(H\)-group closeness centrality over disk-resident graphs
• Maximizing PageRank via outlinks
• Probability Inequalities for Sums of Bounded Random Variables
• Probability and statistics with reliability, queuing, and computer science applications
• The Effect of New Links on Google Pagerank
• The budgeted maximum coverage problem
• Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments

Cited in

(1)

• Towards Fewer Seeds for Network Discovery

This page was built for publication: Optimizing node discovery on networks: problem definitions, fast algorithms, and observations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2201666)