Many natural and human systems can be represented as networks, including the Internet, social interactions, food webs, and transportation and communication flows. One thing that these types of networks have in common, is that they can each be represented as a series of vertices (or nodes) and edges (or links). This blog entry presents a nice description of networks, highlighting the differences between various network types (directed, undirected, weighted, unweighted, etc.).
According to this paper, many networks are found to display “community structure”, which basically refers to groupings of vertices where within-group edge connections are more dense than between-group edge connections. In order to detect and delineate these groupings, Leicht & Newman (2008) present a nice “modularity” optimisation algorithm which is designed to find a “good” division of a network by maximising
where \(s\) is a vector whose elements define which group each node belongs to, and \(\mathbf{B}\) is the so-called modularity matrix, with elements
where \(A_{ij}\) is an element in the adjacency matrix \(\mathbf{A}\), \(k_{i}^{in}\) and \(k_{j}^{out}\) are the in- and out-degrees of the vertices, and \(m\) is the total sum of edges in the network. In practice, this can be extended to directed networks by considering the matrix \(\mathbf{B} + \mathbf{B}^T\) (for an explanation of why this is the case, see Leicht & Newman).
It is relatively straight-forward to extend the above modularity optimisation algorithm to the case of a weighted network by computing the modularity matrix using the in- and out-strength(see link to blog post above) of the vertices instead of the degree. This is similar to the concept presented in Newman (2004), and indeed the theory of the modularity algorithm holds for this more general case (note that an unweighted network can simply be represented as a weighted network where the edge weights are all set to 1). As such, our new modularity matrix can be computed as
where \(m = \sum_{i}s_{i}^{in} = \sum_{j} s_j^{out}\), and \(s\) represents the vertex strength. As such, using the above new definition of \(\mathbf{B}\), the modularity of a directed, weighted network is computed as
My current research uses a modified modularity optimisation algorithm to compute functional regions for Ireland based on a range of socio-economic variables. The goal is to provide a consistent framework for computing functional regions which are comparable across different countries and/or regions.
C
References
Leicht, E. A. & Newman, M. E. J.(2008). Community structure in directed networks. Physical Review Letters, 100(11), 118703.
Newman, M. E. J.(2004). Analysis of weighted networks. Physical Review E, 70(5), 056131.
