test
server time: root: http://itiis.org
current_path: /journals/tiis/digital-library/22126
current_url: http://itiis.org/journals/tiis/digital-library/22126
Mining Highly Reliable Dense Subgraphs from Uncertain Graphs
  • KSII Transactions on Internet and Information Systems
    Monthly Online Journal (eISSN: 1976-7277)

Mining Highly Reliable Dense Subgraphs from Uncertain Graphs

Vol. 13, No. 6, June 29, 2019
10.3837/tiis.2019.06.012, Download Paper (Free):

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.


Statistics

Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2015)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article

[IEEE Style]
L. Yihong, H. Ruizhi and H. Decai, "Mining Highly Reliable Dense Subgraphs from Uncertain Graphs," KSII Transactions on Internet and Information Systems, vol. 13, no. 6, pp. 2986-2999, 2019. DOI: 10.3837/tiis.2019.06.012.

[ACM Style]
LU Yihong, HUANG Ruizhi, and HUANG Decai. 2019. Mining Highly Reliable Dense Subgraphs from Uncertain Graphs. KSII Transactions on Internet and Information Systems, 13, 6, (2019), 2986-2999. DOI: 10.3837/tiis.2019.06.012.