TY - GEN
T1 - Fast direction-aware proximity for graph mining
AU - Tong, Hanghang
AU - Faloutsos, Christos
AU - Koren, Yehuda
PY - 2007
Y1 - 2007
N2 - In this paper we study asymmetric proximity measures on directed graphs, which quantify the relationships between two nodes or two groups of nodes. The measures are useful in several graph mining tasks, including clustering, link prediction and connection subgraph discovery. Our proximity measure is based on the conceptof escape probability. This way, we strive to summarize the multiple facets of nodes-proximity, while avoiding some of the pitfalls to which alternative proximity measures are susceptible. A unique feature of the measures is accounting for the underlying directional information. We put a special emphasis on computational efficiency, and develop fast solutions that are applicable in several settings. Our experimental study shows the usefulness of our proposed direction-aware proximity method for several applications, and that our algorithms achieve a significant speedup (up to 50,000x) over straight forward implementations.
AB - In this paper we study asymmetric proximity measures on directed graphs, which quantify the relationships between two nodes or two groups of nodes. The measures are useful in several graph mining tasks, including clustering, link prediction and connection subgraph discovery. Our proximity measure is based on the conceptof escape probability. This way, we strive to summarize the multiple facets of nodes-proximity, while avoiding some of the pitfalls to which alternative proximity measures are susceptible. A unique feature of the measures is accounting for the underlying directional information. We put a special emphasis on computational efficiency, and develop fast solutions that are applicable in several settings. Our experimental study shows the usefulness of our proposed direction-aware proximity method for several applications, and that our algorithms achieve a significant speedup (up to 50,000x) over straight forward implementations.
KW - Graph mining
KW - Proximity
KW - Random walk
UR - http://www.scopus.com/inward/record.url?scp=36849093960&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=36849093960&partnerID=8YFLogxK
U2 - 10.1145/1281192.1281272
DO - 10.1145/1281192.1281272
M3 - Conference contribution
AN - SCOPUS:36849093960
SN - 1595936092
SN - 9781595936097
T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
SP - 747
EP - 756
BT - KDD-2007
T2 - KDD-2007: 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Y2 - 12 August 2007 through 15 August 2007
ER -