Measuring Large-Scale Dynamic Graph Similarity by RICom: RWR with Intergraph Compression
作者： Jaekoo Lee , Gunn Kim , Sungroh Yoon
关键词:
摘要: By how much is a large-scale graph transformed over time or by significant event?' 'how structurally similar are two graphs?' the questions that this paper attempts to address. The proposed method efficiently calculates and accurately produces similarity. Our approach based on well-known random walk with restart (RWR) algorithm, which quantifies relevance between nodes express structural connection characteristics of graphs. Intergraph compression, inspired interframe merges input graphs reorders their contributing improved process-data storage efficiency processing convenience. This boon RWR algorithm for representation via intergraph compression can be used show similarity because sub-matrix blocks reordered concentrate nonzero elements. In performing inter-node relevance, efficient in space requirement results more quickly conventional transformation schemes. We demonstrate validity our through experiments apply it usage data public transportation SmartCard large metropolitan area suggest usefulness algorithm.
sci-hub.se 参考文章(15)
Konstantinos Konstantinides, Vasudev Bhaskaran, Image and Video Compression Standards: Algorithms and Architectures Kluwer Academic Publishers. ,(1997)
Diane J Cook, Lawrence B Holder, None, Mining Graph Data : Wiley-Interscience,. ,(2006)
Amy N. Langville, Carl D. Meyer, Google's PageRank and Beyond: The Science of Search Engine Rankings ,(2006)
Danai Koutra, Joshua T. Vogelstein, Christos Faloutsos, DELTACON: A Principled Massive-Graph Similarity Function arXiv: Social and Information Networks. ,(2013)
Danai Koutra, Tai-You Ke, U. Kang, Duen Horng Chau, Hsing-Kuo Kenneth Pao, Christos Faloutsos, Unifying guilt-by-association approaches: theorems and fast algorithms european conference on machine learning. pp. 245- 260 ,(2011) , 10.1007/978-3-642-23783-6_16
Sungroh Yoon, Jessica C Ebert, Eui-Young Chung, Giovanni De Micheli, Russ B Altman, Clustering protein environments for function prediction: finding PROSITE motifs in 3D BMC Bioinformatics. ,vol. 8, pp. 1- 12 ,(2007) , 10.1186/1471-2105-8-S4-S10
Yasuhiro Fujiwara, Makoto Nakatsuji, Takeshi Yamamuro, Hiroaki Shiokawa, Makoto Onizuka, Efficient personalized pagerank with accuracy assurance Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '12. pp. 15- 23 ,(2012) , 10.1145/2339530.2339538
Yongsub Lim, U Kang, Christos Faloutsos, SlashBurn: Graph Compression and Mining beyond Caveman Communities IEEE Transactions on Knowledge and Data Engineering. ,vol. 26, pp. 3077- 3089 ,(2014) , 10.1109/TKDE.2014.2320716
Yongkweon Jeon, Sungroh Yoon, Multi-Threaded Hierarchical Clustering by Parallel Nearest-Neighbor Chaining IEEE Transactions on Parallel and Distributed Systems. ,vol. 26, pp. 2534- 2548 ,(2015) , 10.1109/TPDS.2014.2355205
Hanghang Tong, Christos Faloutsos, Jia-Yu Pan, Fast Random Walk with Restart and Its Applications international conference on data mining. pp. 613- 622 ,(2006) , 10.1109/ICDM.2006.70