Big graph mining for the web and social media: algorithms, anomaly detection, and applications
Big graph mining for the web and social media: algorithms, anomaly detection, and applications
复制标题
DOI：
10.1145/2556195.2556198
复制
发表时间：
2014-02
期刊：
影响因子：
--
通讯作者：
U. Kang;L. Akoglu;Duen Horng Chau
中科院分区：
文献类型：
--
作者：
U. Kang;L. Akoglu;Duen Horng Chau
图表无处不在：社交网络、计算机网络、移动电话网络、万维网、蛋白质交互网络等等。磁盘存储的较低成本、社交网络网站和Web 2.0应用程序的成功以及数据源的高可用性使得生成的图形达到了前所未有的规模。它们现在以太字节甚至拍字节来衡量，拥有超过数十亿个节点和边缘。在大图形上寻找模式有很多应用，包括网络安全、社交媒体挖掘（Facebook、Twitter）和欺诈检测等。本教程将涵盖与在大规模图形中寻找模式和异常以及意义相关的主题，并将其应用于社交媒体和Web中的现实问题。具体来说，我们的目标是回答以下问题：我们如何扩展具有数十亿条边的大规模图的图挖掘算法？我们如何在如此大规模的图表中发现异常呢？我们如何理解驻留在磁盘上的大图形，我们可以做什么以及如何做可视化分析？我们如何使用算法和异常检测技术来解决在社交媒体和网络中发挥关键作用的具有挑战性的现实问题？我们的教程由三个主要部分组成。我们从十亿尺度图的可扩展图挖掘算法开始，包括结构分析、特征求解、存储和索引、图布局和图压缩。接下来，我们描述了在社交媒体上应用的大规模图的异常检测技术。最后，我们在前面的部分讨论了利用这些算法和异常检测技术的可视化分析技术。
Graphs are everywhere: social networks, computer net- works, mobile call networks, the World Wide Web, protein interaction networks, and many more. The lower cost of disk storage, the success of social networking websites and Web 2.0 applications, and the high availability of data sources lead to graphs being generated at unprecedented size. They are now measured in terabytes or even petabytes, with more than billions of nodes and edges. Finding patterns on large graphs have a lot of applica- tions including cyber security on the Web, social media min- ing (Facebook, Twitter), and fraud detection, among others. This tutorial will cover topics related to finding patterns and anomalies and sensemaking in large-scale graphs with appli- cations to real-world problems in social media and the Web. Specifically, we aim to answer the following questions: How can we scale up graph mining algorithms for massive graphs with billions of edges? How can we find anomalies in such large-scale graphs? How can we make sense of disk-resident large graphs, what and how can we do visual analytics? How can we use the algorithms and anomaly detection techniques to solve challenging real-world problems that play key role in social media and the Web? Our tutorial consists of three main parts. We start with scalable graph mining algorithms for billion-scale graphs, in- cluding structure analysis, eigensolvers, storage and index- ing, and graph layout and graph compression. Next we de- scribe anomaly detection techniques for large scale graphs with applications on social media. Finally, we discuss vi- sual analytics techniques which leverage these algorithms and anomaly detection techniques in the previous parts.