Mining large graphs: Algorithms, inference, and discoveries
Mining large graphs: Algorithms, inference, and discoveries
复制标题
挖掘大图：算法、推理和发现
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
C. Faloutsos
中科院分区：
文献类型：
--
作者：
U. Kang;Duen Horng Chau;C. Faloutsos
我们如何在具有数十亿个节点和边的图上找到不适合内存的模式和异常？如何为这种TB级的图形使用并行性？在这项工作中，我们专注于推理，这往往对应，直观地说，“内疚的协会”的情况。例如，如果一个人是吸毒者，那么他的朋友很可能也是;如果社交网络中的一个节点是男性，那么他的约会对象很可能是女性。我们展示了如何使用Hadoop平台，通过我们提出的HADoop线图固定点（Ha-Lfp），一个有效的并行算法，稀疏的十亿级图，在这样巨大的图上进行推理。我们的贡献包括：（a）设计的哈LFP，观察它对应于一个固定点的线图诱导从原来的图形;（B）可扩展性分析，表明我们的算法规模以及与边缘的数量，以及与机器的数量;和（c）实验结果两个私人，以及两个最大的公开可用的图形-网络图形从雅虎！(6.6 10亿条边和0.24Tera字节），以及Twitter图（37亿条边和0.13Tera字节）。我们使用世界上最快的50台超级计算机之一M45来评估我们的算法，我们报告了我们的算法发现的模式和异常，否则这些模式和异常是不可见的。
How do we find patterns and anomalies, on graphs with billions of nodes and edges, which do not fit in memory? How to use parallelism for such terabyte-scale graphs? In this work, we focus on inference, which often corresponds, intuitively, to “guilt by association” scenarios. For example, if a person is a drug-abuser, probably its friends are so, too; if a node in a social network is of male gender, his dates are probably females. We show how to do inference on such huge graphs through our proposed HAdoop Line graph Fixed Point (Ha-Lfp), an efficient parallel algorithm for sparse billion-scale graphs, using the Hadoop platform. Our contributions include (a) the design of Ha-Lfp, observing that it corresponds to a fixed point on a line graph induced from the original graph; (b) scalability analysis, showing that our algorithm scales up well with the number of edges, as well as with the number of machines; and (c) experimental results on two private, as well as two of the largest publicly available graphs — the Web Graphs from Yahoo! (6.6 billion edges and 0.24 Tera bytes), and the Twitter graph (3.7 billion edges and 0.13 Tera bytes). We evaluated our algorithm using M45, one of the top 50 fastest supercomputers in the world, and we report patterns and anomalies discovered by our algorithm, which would be invisible otherwise.