Connection Subgraphs in Social Networks
Connection Subgraphs in Social Networks
复制标题
社交网络中的连接子图
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
A. Tomkins
中科院分区：
文献类型：
--
作者：
C. Faloutsos;K. McCurley;A. Tomkins
连接子图是社交网络中最能捕捉两个人之间关系的小（即可见）子图。我们提出了一个正式的定义，这个问题，和一个理想的解决方案的基础上计算的电流在电网络中，或等效的，基于随机游动的加权图。然后，我们给出了一系列近似的理想解决方案，真实的产生高质量的连接子图非常大的（核心外）的社会网络图。我们描述了一个工作的原型，我们展示的结果来自万维网的社交网络图包含1500万个节点和9600万个边缘，我们的原型在几秒钟内产生良好的质量响应。
A connection subgraph is a small (ie, viewable) subgraph of a social network that best captures the relationship between two people. We present a formal definition of this problem, and an ideal solution based on computation of current in electrical networks, or equivalently, based on random walks on weighted graphs. We then give a series of approximations to the ideal solution that produce high-quality connection subgraphs in real time on very large (out of core) social network graphs. We describe a working prototype, and we demonstrate results on a social network graph derived from the World Wide Web containing 15 million nodes and 96 million edges, for which our prototype produces good quality responses within a few seconds.