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

DOI10.1016/J.INS.2018.10.036zbMATH Open1443.90328arXiv1703.04307OpenAlexW2753387861MaRDI QIDQ2201666FDOQ2201666

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

Publication date: 29 September 2020

Published in: Information Sciences (Search for Journal in Brave)

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.

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

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
• Maximizing social influence in nearly optimal time
• Structural search and optimization in social networks

zbMATH Keywords

random walkgreedy algorithmMCMC simulationsubmodular/supermodular set function

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• Title not available (Why is that?)
• Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments
• The budgeted maximum coverage problem
• An analysis of approximations for maximizing submodular set functions—I
• The Effect of New Links on Google Pagerank
• Probability and Statistics with Reliability, Queuing and Computer Science Applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• A note on maximizing the spread of influence in social networks
• Maximizing PageRank via outlinks
• A note on maximizing a submodular set function subject to a knapsack constraint
• Axioms for Centrality
• I/O-efficient calculation of \(H\)-group closeness centrality over disk-resident graphs

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)