Dynamical analysis of interlocking directorates using graph edit distance

In this work we study network dynamics, with particular reference to time-dependent socio-economic networks. In recent years, network theory has been gaining more and more relevance in the study of systems where elements interact in forming complex relational patterns. Providing both tools for representing the interconnections among elements and tools to formally investigate relational structures, network theory leads to a deeper understanding of the global properties of such systems. Up to now, research has mainly focused on a static analysis of networks, with the basic goal to characterize their global and local features by means of different structural indicators. Then researchers' interest is shifting towards network dynamics and towards the study of structural changes of time-dependent relational systems. Common approaches to network dynamics involve the comparison over time of one or more structural indicators, tracking their time evolution in order to investigate the dynamics of the underlying network. In our work we embed networks into a larger structure, namely a lattice equipped with a metric, and analyze their dynamics in terms of paths within the lattice. The fundamental distinction is between structural and non-structural dynamics, the first occurring when the topology of the network changes over time, the second referring to changes that can be described just in terms of permutations among vertex labels. In real cases, both kinds of dynamics may occur at the same time, and we propose a way to separately measure them. The distance between two networks is measured counting the minimum number of edge additions or removals, needed to transform one network into the other. Similarly, the structural component is measured computing the minimum number of edge additions and removals required to make one network isomorphic to the other. This notion of structural distance is basically the same as the so-called graph edit distance (GED). In its original formulation, GED defines the dissimilarity of two (possibly labeled) graphs by the minimum amount of distortions –insertion and deletion of nodes and edges, and label changes– that are needed to transform one graph into the other, neglecting node permutations. Exact calculation of the GED is a computationally intractable problem, except for very small graphs; thus we have implemented an approximate algorithm based on beam search, which is an approximate variant of the A* heuristic search algorithm, in order to obtain a good estimate of the GED even for large graphs. For sake of simplicity, here we limit ourselves to networks which evolve keeping the vertex set fixed. Notwithstanding this limitation, our methodology proves effective in capturing the distinction between structural and non-structural changes and helps getting new insights into real network dynamics. As an application we use our methodology to study the relationships among companies sharing one or more directors. The expression interlocking directorates refers to the well-known phenomenon of corporate directors serving in more than one corporate with consequences on the strategic connections among companies. Interlocking directorates gives rise to the corporate board network. We test our approach against a subnetwork extracted out of it, analyzing the dynamics of the local network of three important Italian firms from different sectors (financial, industrial and publishing) from 2007 to 2011.