Studying Human Dynamics at a Massive Scale: The Development and Assessment of a Distributed Approach for Effective Visualization of 100+ Million-Node Social Networks

大规模研究人类动力学：一亿节点社交网络有效可视化分布式方法的开发和评估

• 批准号: RGPIN-2019-05617
• 负责人: Gruzd, Anatoliy
• 金额: $ 2.04万
• 依托单位: Ryerson University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=715624
• 关键词: Studying; Human; Dynamics; Massive; Scale

Graphs of Online Social Networks (OSNs) - representing social media participants, their relationships and interactions - are an area of growing interest and significant investigation. Visual layouts of these graphs are a common tool used by researchers in a wide variety of fields to help understand network's underlying structures, form hypotheses, and communicate research results. Graphs can reveal information about the network's structure that may be difficult to determine through quantitative and qualitative methods alone. As OSNs are often very large, and growing ever larger as more people (and IoT devices) join various social media platforms. Existing layout techniques to display massive OSN data are computationally expensive; often, their implementations are not easily scalable and usually require an extraordinary amount of time and resources to render. In this work, we will propose and evaluate a distributed computing method to significantly speed up the completion time of social network graph visualization. Existing literature identifies problems with layout of large networks, and alludes to how distributed computing and other techniques might be possible solutions, but so far little empirical research work has been done to implement and test these suppositions. Currently, scholars who are relying on network visualizations in their data exploration and analysis are using work around such as data reduction and filtering techniques to address the scalability issues of current network visualization tools. Our method will build upon existing graph layout techniques, and will put forward a novel graph partitioning scheme that is better-suited for laying out graphs with small-world, scale-free network properties; properties that are naturally occurring in online social networks. Our method will be implemented and evaluated using a popular distributed system for graph processing -- Spark GraphX. The evaluation phase will be based on large-scale anonymized networks collected from social media platforms including Twitter, Flickr, Reddit, and will include both algorithm- and user-based evaluation. The overarching goal of this initiative is to develop and test a new distributed graph partitioning technique for visualizing networks with 100 million+ nodes, share its machine- and user-driven evaluation, and distribute a ready-to-use open source library that can be used by network scholars in various domains (and not just in the area of social media).

在线社交网络（OSN）的图形-表示社交媒体参与者，他们的关系和互动-是一个日益增长的兴趣和重要的调查领域。这些图形的视觉布局是研究人员在各种领域使用的常用工具，以帮助理解网络的底层结构，形成假设，并传达研究结果。图表可以揭示有关网络结构的信息，这些信息可能难以单独通过定量和定性方法确定。由于OSN通常非常大，并且随着越来越多的人（和物联网设备）加入各种社交媒体平台而变得越来越大。现有的显示大量OSN数据的布局技术在计算上是昂贵的;通常，它们的实现不容易扩展，并且通常需要大量的时间和资源来渲染。在这项工作中，我们将提出并评估一种分布式计算方法，以显着加快社交网络图可视化的完成时间。 现有的文献确定了大型网络布局的问题，并暗示如何分布式计算和其他技术可能是可能的解决方案，但到目前为止，很少有实证研究工作已经完成，以实现和测试这些假设。目前，在数据探索和分析中依赖网络可视化的学者正在使用数据缩减和过滤技术等方法来解决当前网络可视化工具的可扩展性问题。 我们的方法将建立在现有的图形布局技术，并将提出一种新的图形分区方案，更适合布局图与小世界，无标度网络属性，自然发生在在线社交网络的属性。我们的方法将使用流行的分布式图形处理系统Spark GraphX来实现和评估。评估阶段将基于从Twitter、Flickr、Reddit等社交媒体平台收集的大规模匿名网络，并将包括基于算法和基于用户的评估。 该计划的总体目标是开发和测试一种新的分布式图分区技术，用于可视化具有1亿多个节点的网络，分享其机器和用户驱动的评估，并分发一个可供网络学者在各个领域（而不仅仅是社交媒体领域）使用的现成开源库。