Clustering Uncertain Graphs

Preprint English OPEN
Ceccarello, Matteo; Fantozzi, Carlo; Pietracaprina, Andrea; Pucci, Geppino; Vandin, Fabio;
(2016)
  • Subject: Computer Science - Data Structures and Algorithms

An uncertain graph $\mathcal{G} = (V, E, p : E \rightarrow (0,1])$ can be viewed as a probability space whose outcomes (referred to as \emph{possible worlds}) are subgraphs of $\mathcal{G}$ where any edge $e\in E$ occurs with probability $p(e)$, independently of the oth... View more
  • References (23)
    23 references, page 1 of 3

    [1] S. Asthana, O.D. King, F.D. Gibbons, and F.P. Roth. Predicting protein complex membership using probabilistic network reliability. Genome Research, 14(4):1170-1175, 2004.

    [2] E. Adar and C. Re. Managing uncertainty in social networks. IEEE Data Engineering Bullettin, 30(2):15-22, 2007.

    [3] A. Biswas and R. Morris. ExOR: opportunistic multi-hop routing for wireless networks. ACM SIGCOMM Computer Communication Review, 35(4):133-144, 2005.

    [4] J. Ghosh, H.Q. Ngo, S. Yoon, and C. Qiao. On a routing problem within probabilistic graphs and its application to intermittently connected networks. In 26th IEEE INFOCOM, pages 1721-1729, 2007.

    [5] P. Boldi, F. Bonchi, A. Gionis, and T. Tassa. Injecting uncertainty in graphs for identity obfuscation. PVLDB, 5(11):1376-1387, 2012.

    [6] Leslie G. Valiant. The complexity of enumeration and reliability problems. SICOMP, 8(3):410-421, 1979.

    [7] M.O. Ball. Computation compexity of network reliability analysis: An overview. IEEE Transactions on Reliability, R-35(3):230-239, 1986.

    [8] R. Jin, L. Liu, B. Ding, and H. Wang. Distance-constraint reachability computation in uncertain graphs. PVLDB, 4(9):551-562, 2011.

    [9] M. Potamias, F. Bonchi, A. Gionis, and G. Kollios. k-nearest neighbors in uncertain graphs. PVLDB, 3(1):997-1008, 2010.

    [10] S.E. Schaeffer. Graph clustering. Computer Science Review, 1(1):27-64, 2007.

  • Related Research Results (1)
    Inferred by OpenAIRE
    software
    ugraph software on GitHub
    72%
  • Related Organizations (2)
  • Metrics
Share - Bookmark