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

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

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).