Skeleton-based Clustering in Big and Streaming Social Networks

我们设计了新的方法来集群大规模的静态和动态的在线社交网络。我们的方法是基于骨架结构，这些骨架结构表示并放大了局部内聚力的变化，并且是在局部定义的，以便于高效计算。除了简化集群问题，它们还将提供对社区动态的新理解，更直接地捕捉社会参与者的代理。在线社会关系和互动中的发现模式是当今大数据最突出的应用之一，主要是由于数据收集的相对容易及其经济和政治价值。虽然这一过程生成的数据是海量的，但它源于对整个系统了解有限的个人的行为。因此，我们的工作假设是，局部结构捕获主要趋势的程度足以为划分或重叠集群的算法提供信息。此外，我们期望个体属性数据的集成将提高经验相关性，持久骨架结构的定义将产生更可靠的群落动力学概念。我们将结合稀疏化、填充和节点属性，提出最新的局部确定骨架结构的方法，并研究其在可扩展到大数据的新型近似图聚类算法中的应用。我们的目标是通过利用社会网络的特殊特性或满足于近似结果来获得近线性最坏情况下的运行时间的算法。虽然整体算法效率很重要，但我们将额外强调算法工程，以增加和利用局部性。考虑流数据将是一个必要的要求，因为在线社交网络通常会生成二进制事件序列。为了处理海量图，我们还开发了用于图聚类及相关问题的外部记忆算法。为了支持算法的验证和实验评估，我们特别强调了社交网络的生成模型。由于集群问题的普遍性，该项目的预期结果包括用于其他应用领域的大数据分析工具。

We devise novel methods to cluster large-scale static and dynamic online social networks. Our approach is based on skeleton structures that represent and amplify variation in local cohesion, and that are defined locally to facilitate efficient computation. In addition to simplifying the clustering problem, they shall also provide a novel understanding of community dynamics, capturing more directly the agency of social actors.Finding patterns in online social relationships and interactions is one of the most prominent applications of big data today, largely driven by the relative ease of data collection and its economic and political value. While this process-generated data is massive, it stems from the actions of individuals with bounded knowledge of the entire system. Our working hypothesis is therefore that local structures capture major trends to an extent sufficient to inform algorithms for partitioning or overlapping clusters. Moreover, we expect the integration of individual attribute data to boost empirical relevance, and the definition of persistent skeleton structures to yield more reliable concepts of community dynamics.Combining sparsification with imputation and nodal attributes, we will advance recent approaches to locally-determined skeleton structures and study their utility for novel and approximate graph clustering algorithms that scale to big data. We are aiming at algorithms with near-linear worst-case running times by exploiting special characteristics of social networks or settling for approximate results. While overall algorithmic efficiency is important, we will place additional emphasis on algorithm engineering to increase and exploit locality. Consideration of streaming data will be a necessary requirement as online social networks typically generate sequences of dyadic events. In order to cope with massive graphs we also develop external memory algorithms for graph clustering and related problems. In support of the validation and experimental evaluation of algorithms we place particular emphasis on generative models for social networks. Due to the pervasive nature of clustering problems, the expected outcome of this project includes tools for big data analysis in other application areas.