Distributed Core Decomposition in Probabilistic Graphs

Qi Luo (), Dongxiao Yu, Feng Li (), Xiuzheng Cheng (), Zhipeng Cai () and Jiguo Yu ()
Additional contact information
Qi Luo: School of Computer Science and Technology, Shandong University, No. 72 Binhai Road, Qingdao 266237, P. R. China
Dongxiao Yu: School of Computer Science and Technology, Shandong University, No. 72 Binhai Road, Qingdao 266237, P. R. China
Feng Li: School of Computer Science and Technology, Shandong University, No. 72 Binhai Road, Qingdao 266237, P. R. China
Xiuzheng Cheng: School of Computer Science and Technology, Shandong University, No. 72 Binhai Road, Qingdao 266237, P. R. China
Zhipeng Cai: Department of Computing Science, Georgia State University, Atlanta, USA
Jiguo Yu: School of Computer Science and Technology, Qilu University of Technology, Jinan, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2021, vol. 38, issue 05, 1-23

Abstract: This paper initializes distributed algorithm studies for core decomposition in probabilistic graphs. Core decomposition has been proven to be a useful primitive for a wide range of graph analyses, but it has rarely been studied in probabilistic graphs, especially in a distributed environment. In this work, under a distributed model underlying Pregel and live distributed systems, we present the first known distributed solutions for core decomposition in probabilistic graphs, where there is an existence probability for each edge. In the scenario that the existence probability of edges are known to nodes, the proposed algorithm can get the exact coreness of nodes with a high probability guarantee. The proposed algorithm can also be used to efficiently update the coreness of nodes in dynamic graphs, where a set of edges are inserted/deleted into/from the graph. In the harsher case that the existence probability is unknown, we present a novel method to estimate the existence probability of edges, based on which the coreness of nodes with small approximation ratio guarantee can be computed. Extensive experiments are conducted on different types of real-world graphs and synthetic graphs. The results illustrate that the proposed algorithms exhibit good efficiency, stability and scalability.

Keywords: Probabilistic graph; core decomposition; distributed algorithm (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S021759592140008X
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:38:y:2021:i:05:n:s021759592140008x

Ordering information: This journal article can be ordered from

DOI: 10.1142/S021759592140008X

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().