Drawing and Visualisation of Dynamic Multivariate Graphs for Social Networks

Networks, or graphs, are pervasive in our modern society. A network consists of entities, or nodes, and a set of relationships between those entities, or edges. When we consider social media services (Facebook, Twitter, etc), nodes correspond to user accounts and edges would be friendships between these users. Nodes often have information associated with them, or attributes. In a social network, these attributes could be as simple as demographic data or information that a particular user has at a given time. In an intelligent infrastructure setting, where nodes and edges correspond to a road network, the level of congestion along stretches of road would be an attribute of the network. In general, networks that have attributes associated with their nodes and edges are called multivariate networks and are an emerging area of information visualisation.

Multivariate networks can also be dynamic. That is, either the structure of the network itself or the attributes associated with the nodes and edges can change over time. In a social network setting, friendships are formed and are broken, evolving the network. Information that a friend might have can spread from node to node cascading through the network structure. In a city, new roadways can be built or closed, corresponding to structural changes in the network. Levels of congestion vary throughout the course of the day and therefore the attributes can change as well. Networks where the structure and/or attributes change over time are dynamic multivariate networks and understanding how they operate is critical for these applications and many others. In information visualisation, this emerging area has received much recent attention.

The challenge of this work occurs when the network structure and/or the attributes change over time and we would like to visualise these changes effectively. As many networks, particularly social networks, do not have inherent spatial positions for the nodes, we are free to choose these positions. Also, we are free to choose the encodings for the attributes. However, we must do so in a way that is both computationally efficient and perceptually effective for the end user of the visualisation.

In this work, we look at perceptually effective ways for drawing and visualising dynamic multivariate graphs. We work closely with research scientists at the Oxford Internet Institute to ensure impact on software that is already in use with various user communities. For this work, we are inspired by studies in psychology and perception in order to drive the design of algorithms to draw the graph and interactive methods for their visualisation. We concentrate on methods for drawing and visualising both evolving structure and evolving attributes. In order to ensure our algorithms conform to the desired perceptual criteria, we evaluate our computational processes through metric evaluations and evaluate our visualisations through user centred experimentation. By working closely with our collaborators in social networks, we ensure the work is relevant for analysing social networks.

Impact is embedded into the proposed research. This impact lies directly in the area of social networks and sociology, influencing applications already in use by various user communities. The algorithms developed and validated as part of this research have the potential to assist projects conducted at the Oxford Internet Institute that have been designed to improve the quality of life of users involved in two projects. We will work closely with the OII in order to accelerate this impact.

Network visualisation in sociology is rapidly becoming essential to robust methods for data collection and interpretation. The results from the proposed research will be applied to several on-going projects such as CollegeConnect, funded by the Bill and Melinda Gates Foundation, and the RADAR project, funded by the National Institute of Health and administered by the Feinberg School of Medicine at Northwestern University. In both cases, Dr. Bernie Hogan[1] is employing network data collection methods and requires visualisation tools in order to make sense of this data.

CollegeConnect helps high school students find out about university by processing and visualising data from their social media platforms. By providing a visualisation of their Facebook network, the application makes ties to communities that the potential student may know to help them with these education-related decisions. This information is especially important if the student does not know someone directly who has gone to university themselves. As social media networks are pervasive, it also increases the accessibility of this information to a wider audience of young adults.

The second application processes contagion patterns in HIV networks. In this project, the research team aims to combine a number of different networks including: drug, sex and social networks across multiple participants in order to help these groups. Both projects require extensive visualisations. While it is understood that visualisation is important for increasing respondent satisfaction and decreasing burden, the network visualisation methods that work best for these circumstances have still to be understood.

The algorithms developed as part of this project have the potential for a significant impact on both projects. This research will help increase respondent satisfaction and increase retention rates of participants in these programs. These projects intend to collect longitudinal data and having functional and successful visualisations is a key part of this process. The expertise of the PI in the generation of new visualisation approaches for multivariate networks will help support these two software systems that are already in use. In particular, these visualisation systems will benefit from drawing upon the knowledge base of experimentally validated best practices for visualisation. Thus, by supporting contemporary work on multivariate network visualisation, such as the research proposed in this grant, we can accelerate the impact of this research not only in the area of sociology and social networks but on two visualisation applications already in use by these communities.

A second possible impact area that we intend to pursue is that of intelligent infrastructure for sustainable cities. Multivariate networks have the potential for substantial impacts in this area: from traffic flows through a city to the flow of information across social media services. Although this impact area is secondary to this grant, we intend to initiate research activities that explore the possibilities for applying this research to the area of intelligent infrastructure. Both industrial and academic communities will be encouraged to participate in these activities.

[1] http://www.oii.ox.ac.uk/people/?id=140