.png){kind=icon}
返回
Set-based approximate approach for lossless graph summarization
.png){kind=icon}
PRE
AI
DOI：10.1007/s00607-015-0454-9.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Graph summarization is valuable approach to analyze various real life phenomenon, like communities, influential nodes, and information flow in a big graph. To summarize a graph, nodes having similar neighbors are merged into super nodes and their corresponding edges are compressed into super edges. Existing methods find similar nodes either by nodes ordering or perform pairwise similarity computations. Compression-by-node ordering approaches are scalable but provide lesser compression due to exhaustive similarity computations of their counterparts. In this paper, we propose a novel set-based summarization approach that directly summarizes naturally occurring sets of similar nodes in a graph. Our approach is scalable since we avoid explicit similarity computations with non-similar nodes and merge sets of nodes in each iteration. Similarly, we provide good compression ratio as each set consists of highly similar nodes. To locate sets of similar nodes, we find candidate sets of similar nodes by using locality sensitive hashing. However, member nodes of every candidate set have varying similarities with each other. Therefore, we propose a heuristic based on similarity among degrees of candidate nodes, and a parameter-free pruning technique to effectively identify subset of highly similar nodes from candidate nodes. Through experiments on real world graphs, our approach requires lesser execution time than pairwise graph summarization, with margin of an order of magnitude in graphs containing nodes with highly diverse neighborhood, and produces summary at similar accuracy. Similarly, we observe comparable scalability against the compression-by-node ordering method, while providing better compression ratio.
Keyword:
Graph summarization
LSH
MDL
Degree similarity
Auto pruning
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
2.8
论文数:
2.3K
被引数:
3.5K
机构
引用论文
Personalized highway pilot assist considering leading vehicle’s lateral behaviors考虑前导车辆横向行为的个性化高速公路驾驶辅助.png)
Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile Engineering
Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile EngineeringIF0
PREAI
分享收藏Setting the stage: Feedback environment improves outcomes for a 360-degree-feedback leader-development program.设定背景：反馈环境有助于改善360度反馈领导力发展项目的成果。
PREAI
分享收藏分享收藏
查看更多内容