Bi-dynamic matrix converter

Download links

Introduction

This program is based on an idea first proposed in an article by Chiara Broccatelli, Martin Everett, and Johan Koskinen, entitled Temporal dynamics in covert networks and published in 2016 in the journal Methodological Innovations (vol 9, pp. 1-14). The program was written by Wouter Spekkink. All mistakes that might exist in the program are his.

Bi-dynamic line graphs

In their article, Brocatelli et al. (2016) introduce bi-dynamic line-graphs (BDLG) to depict co-participation of actors in events. Co-participation of actors in events is often captured in two-mode networks. In matrix form, a two-mode network is usually presented as an incidence matrix with actors in rows, and events in columns, like so (example based on article mentioned above):

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. This is done by multiplying the incidence matrix to a weighted adjacency matrix, which can be achieved by converting 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 (some authors prefer to dichomotise the relationships):

Although this gives insight in the ties that emerge from the events in which actors participate, the drawback is that valuable information (such as information on the order of events in which ties occurred) is lost. 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) use line-graphs to incorporate information about timing in the data representation. 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 there are two types of ties, mutual (or reciprocal) and directed. Mutual ties only exist between nodes that indicate different actors that are involved in the same event (e.g., A1<->B1). These ties represent “temporal proximity” of actor-event combinations, since they show who collaborates with whom. Directed ties, instead, connect all the nodes representing the same actor. These ties capture the “temporal sequence” of actor-event combinations, and indicate the continued presence of actors throughout events (e.g., A1->A2->A4). These directed ties are the result of a reduction criterion that Brocatelli et al. 2016 apply, which prevents the inclusion of redundant information that is produced in the transformation of a two-mode network into a line-graph. This process creates mutual ties between all actor-event combinations that include the same actor. However, we only need a single path to be able to track the involvement of actors in events over time. 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 edges A1->A4, A4->A1, A2->A1 and A4->A2 introduce redundant information about the continued involvement of actor A, and can therefore be excluded. The reduction criterion leads to an elegant presentation of information that allows researchers to trace actors’ involvement in the studied events. Actors that are only involved in one event, and only by themselves, will be represented by an empty row in the BDLG matrix. The matrix form of the BDLG thus becomes as follows (there are no isolates in this example).

The program

Based on the ideas outlined above, Wouter Spekkink wrote a simple tool that converts incidence matrices into BDLG matrices. The program expects the user to import a csv-file with the incidence matrix of the two-mode network. The program assumes that the columns of the incidence matrix are ordered in time from left to right. The order of the actors is unimportant.

  • The tool can export the matrix itself to a csv-file. In addition, the tool can export a node list and edge list, where the edge list contains the same information as the matrix, whereas the nodes list also includes some variables that indicate, for each node, the event that is part of the node (Order_Original), the actor that is part of the node (Actor), and the order in which the events occurred (Order_Closed).

Running the program

The Windows version of the program can be run by simply opening the application. The Linux version can be run by using the accompanying shell script. It might be necessary to change permissions for the shell script first, by typing the following in the console:

> sudo chmod+x ./bdlg-matrix.sh

Using the program with Gephi

A quick way to visualise the results is to use the tool to export the node list and edge list, and import these into Gephi. Importing of the edge list and node list should be done from Gephi’s data laboratory. The user should make sure that the order variables of the node list are imported as numeric variables (doubles are the safest option, but integers should also work in most situations). To make useful plots of the results, the user should make sure to also install the Event Graph Layout (this can be done from within the Plugins menu of Gephi). The user should then select one of the order variables as the order variable for the Event Graph Layout plugin. The Actor variable can be used to give nodes colours based on the actors associated with them. This allows one to more easily spot lineages in the graph.

Dependencies

The program was written in C++, and with the help of Qt4.8 libraries. Thus, Qt4.8 must be installed on your system if you wish to build the program yourself. The source code of the tool can be found here.

Known issues and updates

  • 2017-03-20: The reference in the accompanying Readme file was incorrect. The current compressed archives include the Readme files with the correct reference.
  • 2017-03-23: Problems occurred when importing multiple files after each other. This should be fixed in the current downloads. In addition, the tool did not yet capture isolates in the bi dynamic line graph. This has now been fixed.
  • 2017-03-25: Found additional bug when exporting certain matrices. This bug has now also been fixed.
  • 2017-03-27: I received some feedback on the Readme file from lead author of the paper that inspired the tool, and made adjustments accordingly.