Name
Abstract | ||
|---|---|---|
Structural-context similarities between vertices in graphs, such as the Jaccard similarity, the Dice similarity, and the cosine similarity, play important roles in a number of graph data analysis techniques. However, uncertainty is inherent in massive graph data, and therefore the classical definitions of structural-context similarities on exact graphs don't make sense on uncertain graphs. In this paper, we propose a generic definition of structural-context similarity for uncertain graphs. Since it is computationally prohibitive to compute the similarity between two vertices of an uncertain graph directly by its definition, we investigate two efficient approaches to computing similarities, namely the polynomial-time exact algorithms and the linear-time approximation algorithms. The experimental results on real uncertain graphs verify the effectiveness of the proposed structural-context similarities as well as the accuracy and efficiency of the proposed evaluation algorithms. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/ICDM.2013.22 | ICDM |
Keywords | Field | DocType |
uncertain graph,jaccard similarity,polynomial-time exact algorithm,approximation theory,dice similarity,data analysis,computational complexity,structural-context similarities,cosine similarity,graph theory,graph data analysis techniques,linear-time approximation algorithm,structural-context similarity | Graph theory,Approximation algorithm,Data mining,Discrete mathematics,Modular decomposition,Cosine similarity,Vertex (geometry),Computer science,Approximation theory,Theoretical computer science,Jaccard index,Computational complexity theory | Conference |
Volume | Issue | ISSN |
null | null | 1550-4786 |
Citations | PageRank | References |
5 | 0.41 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zhaonian Zou | 1 | 331 | 15.78 |
| Jianzhong Li | 2 | 3196 | 304.46 |