Grant: Discovery Grants Program - Individual

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