Mining Highly Reliable Dense Subgraphs from Uncertain Graphs = Mining Highly Reliable Dense Subgraphs from Uncertain Graphs

다국어 초록 (Multilingual Abstract)

The uncertainties of the uncertain graph make the traditional definition and algorithms on mining dense graph for certain graph not applicable. The subgraph obtained by maximizing expected density from an uncertain graph always has many low edge-probability data, which makes it low reliable and low expected edge density. Based on the concept of β-subgraph, to overcome the low reliability of the densest subgraph, the concept of optimal β-subgraph is proposed. An efficient greedy algorithm is also developed to find the optimal β-subgraph. Simulation experiments of multiple sets of datasets show that the average edge-possibility of optimal β-subgraph is improved by nearly 40%, and the expected edge density reaches 0.9 on average. The parameter β is scalable and applicable to multiple scenarios.

참고문헌 (Reference)

1 Gao Yuan, "Uncertain Graph and Uncertain Network" Tsinghua University 2013

2 Rual J F, "Towards a proteome-scale map of the human protein-protein interacrion network" 437 (437): 1173-1178, 2005

3 Tsourakakis C, "The k-cliques densest subgraph problem" ACM 1122-1132, 2015

4 Sozio M, "The community-search problem and how to plan a successful cocktail party" ACM 939-948, 2010

5 Bhattacharya S, "Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams" 173-182, 2015

6 Szklarczyk D, "STRING v10 : protein–protein interaction networks, integrated over the tree of life" 43 : 447-452, 2015

7 Zou Z, "Polynomial-time algorithm for finding densest subgraphs in uncertain graphs" MLG 2013

8 Khuller S, "On Finding Dense Subgraphs" 597-608, 2009

9 Seidman S B, "Network structure and minimum degree" 5 (5): 269-287, 1983

10 Fratkin E, "MotifCut : regulatory motifs finding with maximum density subgraphs" 22 (22): 150-157, 2006

11 Zhu R, "Mining top-k dense subgraphs from uncertain graphs" 39 (39): 1570-1582, 2016

12 Zou Zhaonian, "Mining Top-k maximal cliques from large uncertain graphs" 36 (36): 2146-2155, 2013

13 Zou Z, "Mining Frequent Subgraph Patterns from Uncertain Graph Data" 22 (22): 1203-1218, 2010

14 Charikar M, "Greedy approximation algorithms for finding dense components in a graph" ACM 84-95, 2000

15 Zou Z, "Finding top-k maximal cliques in an uncertain graph" 649-652, 2010

16 Cheng J, "Finding maximal cliques in massive networks by h*-graph" ACM 447-458, 2010

17 Goldberg A V, "Finding a maximum density subgraph" University of California at Berkeley 1984

18 Andersen R, "Finding Dense Subgraphs with Size Bounds" 25-37, 2009

19 Provo A, "Enumeration of maximal cliques from an uncertain graph" 29 (29): 543-555, 2017

20 Wang W, "Emergence of a DNA-damage response network consisting of Fanconianaemia and BRCA proteins" 8 (8): 735-748, 2007

21 Epasto A, "Efficient Densest Subgraph Computation in Evolving Graphs" International World Wide Web Conferences Steering Committee 300-310, 2015

22 Jin R, "Distance-constraint reachability computation in uncertain graphs" 4 (4): 551-562, 2011

23 Jin R, "Discovering highly reliable subgraphs in uncertain graphs" ACM 992-1000, 2011

24 Bahmani B, "Densest subgraph in streaming and MapReduce" 5 (5): 454-465, 2012

25 Tsourakakis C, "Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guarantees" ACM 104-112, 2013

26 Angel A, "Dense subgraph maintenance under streaming edge weight updates for real-time story identication" 5 (5): 574-585, 2012

27 Bonchi F, "Core de-composition of uncertain graphs" ACM 1316-1325, 2014

28 Gao X, "Connectedness Index of Uncertain Graphs" 21 (21): 127-137, 2013

29 Kollios G, "Clustering Large Probabilistic Graphs" 25 (25): 325-336, 2013

30 XIULIAN GAO, "CONNECTEDNESS INDEX OF UNCERTAIN GRAPH" 21 (21): 127-137, 2013