Monthly Archives: March 2017

Bi-dynamic line graphs

Bi-dynamic line graphs

Two days ago Frank Boons and I had the opportunity to present some of our ongoing work during a session of the Mitchell Centre Seminar Series. In addition to receiving some very useful feedback on our work and meeting interesting people, we were introduced to some of the ideas that members of the Mitchell Centre are working on. One of these ideas immediately grabbed our attention, which is the idea to represent social processes in bi-dynamic line graphs (BDLGs), as laid out in this paper by Chiara Brocatelli, Martin Everett, and Johan Koskinen. These graphs can be used to visualise the (joint) involvement of actors in events, showing which actors worked together over time, and allowing one to trace the involvement of actors throughout the process.

The basic ideas behind BDLGs

A BDLG can be understood as a special projection of a two-mode network of actors and events. In matrix form, a two-mode network is usually presented as an incidence matrix with actors in rows, and events in columns, like so (this example was taken from the paper mentioned earlier):

In Social Network Analysis, it is common to convert two-mode networks to one-mode networks that indicate which actors participated in the same events (and how many times they participated in events together). In fact, this is what I usually do myself, and it is the central idea underlying the Dynamic Networks Tool. It can be done by converting the incidence matrix to a weighted adjacency matrix, which can be achieved by multiplying the incidence matrix with a transposed version of itself. If we would do that for the incidence matrix above, we would get the following adjacency matrix:

Although this gives insight in the ties that emerge from the events in which actors participate, the drawback is that all temporal information is lost; only a static network remains. This can be solved partially by making separate adjacency matrices for different segments of the incidence matrix, but the choice for the size of the segments is always arbitrary, and information about changes within each segment is still lost (see Brocatelli et al. 2016 for a discussion on this).

Brocatelli et al. (2016) propose BDLGs as an alternative projection of two-mode networks that have a temporal dimension. In a BDLG the edges between actors and events of the original two-mode graph are ‘converted’ to nodes. For example, the edge between actor A and event 1 in the original two-mode graph becomes the node A1 in the BDLG. In a BDLG, two types of relationships can exist between these nodes. Mutual (or reciprocal) edges only exist between nodes that indicate actors that are involved in the same event (e.g., A1<->B1). Edges with only one direction indicate the continued presence of actors throughout events (e.g., A1->A2->A4). To prevent the inclusion of redundant information in the BDLG, Brocatelli et al. (2016) also introduce the rule that transitive paths are always reduced to a single path. For example, if actor A was involved in events 1, 2, and 4, it is only necessary to create the edges A1->A2 and A2->A4. The edge A1->A4 introduces redundant information about the continued involvement of actor A, and can therefore be excluded. This rule leads to more elegant presentations¬†that allow researchers to trace actors’ involvement in the studied process. The matrix form of the BDLG thus becomes as follows (rows with only 0 values, as well as their corresponding columns, have been removed from the matrix):

A new tool

When I read the paper that outlines these ideas, I was immediately enthusiastic, because the approach fits well with the approach to studying social processes that Frank Boons and I have been developing ourselves, and because it offers a new (to me) and interesting way to study network dynamics in social processes. I therefore set out to write a script for R that can be used to convert incidence matrices into BDLG matrices. I quickly decided to go a bit further, and write a standalone tool for this in C++.

The benefit of the tool that I wrote is that, in addition to converting incidence matrices into BDLG matrices, the tool can export a node list and edge list that can be imported into a visualisation program like Gephi. Also, node and edge lists allow you to include variables, such as variables that hold information on the temporal dimension of the nodes.

I wrote a layout plugin for Gephi, called the Event Graph Layout, some years ago. This layout is great for creating BDLG visualisations, because it allows one to layout nodes in order of occurrence from left to right, and uses a force-based algorithm for the layout of the nodes on the vertical axis. Thus, by using the BDLG matrix converter tool in combination with the Event Graph Layout, one can make useful visualizations in a matter of minutes.

Getting the tool

The tool can be downloaded for Windows and for Linux from this web page. No additional software is required to use the tool, but I highly recommend to use it in combination with Gephi, and the Event Graph Layout plugin for Gephi. The tool is completely free, and the source code of the tool can be found here.