Line Graphs, Link Partitions and Overlapping Communities

I Introduction

Finding hidden patterns or regularities in data sets is a universal problem which has a long tradition in many disciplines from computer science fiedler to social sciences Z77 . For example, when the data set can be represented as a graph, i.e. a set of elements and their pairwise relationships, one often searches for tightly knit sets of nodes, usually called communities or modules. The identification of such communities is particularly crucial for large network data sets that require new mathematical tools and computer algorithms for their interpretation. Most community detection methods find a partition of the set of nodes where most of the links are concentrated within the communities fort ; mason . Here the communities are the elements of the partition, and so each node is in one and only one community.

A popular class of algorithms seek to optimise the modularity $Q$ of the partition of the nodes of a graph $G$ N ; guimera ; Blondel ; Rotta ; RB06 . The simplest definition of modularity for an undirected graph, i.e. the adjacency matrix A is symmetric, is GN

where $W=\sum_{i,j}A_{ij}$ and $k_{i}=\sum_{j}A_{ij}$ is the degree of node $i$. The indices $i$ and $j$ run over the $N$ nodes of the graph $G$. The index $C$ runs over the communities of the partition $\mathcal{P}$. Modularity counts the number of links between all pairs of nodes belonging to the same community, and compares it to the expected number of such links for an equivalent random graph in which the degree of all nodes has been left unchanged. By construction $|Q|\leq 1$ with larger $Q$ indicating that more links remain within communities then would be expected in the random model. Uncovering a node partition which optimises modularity is therefore likely to produce useful communities.

This node partitioning approach has, however, the drawback that nodes are attributed to only one community, which may be an undesirable constraint for networks made of highly overlapping communities. This would be the case, for instance, for social networks, where individuals typically belong to different communities, each characterised by a certain type of relation, e.g. friendship, family, or work. In scientific collaboration networks (for example project2 ), authors may belong to different research groups characterised by different research interests. Such inter-community individuals are often of great interest as they broker the flow of information between otherwise disconnected contacts, thereby connecting people with different ideas, interests and perspectives Burt2004 ; LP09 .

Only a few alternative approaches have been proposed in order to uncover overlapping communities of nodes, for example PDF ; nicosia ; fortuna . Our suggestion is to define communities as a partition of the links rather than of the set of nodes. A node may then have links belonging to several communities and in this it belongs to several communities. The central node in a Bow Tie graph is a simple example, see Fig. 1. This link partition approach should be especially efficient in situations when the nodes of a network are connected by different types of links, i.e. in situations where the nodes are heterogeneous while the links are very homogeneous. In the case of the social network mentioned above, this would occur when the friendship network and work network of individuals only have a very small overlap.

This paper is organised as follows. In section II, we review a definition of modularity which uses the statistical properties of a dynamical process taking place on the nodes of a graph. In section III, we propose three dynamical processes taking place on the links of the graph and derive their corresponding modularities, now defined for a partition of the links of a network. To do so, we make connections to the concept of a line graph and with the projection of bipartite networks. In section IV, we optimise the three modularities for some examples and interpret our results. In section V we conclude and propose ways to improve our method.

II Dynamical formulation of modularity

To motivate our link partition quality function, let us first consider how to interpret the usual modularity $Q$ (1) in terms of a random walker moving on the nodes delvenne ; LDB08 . Suppose that the density of random walkers on node $i$ at step $n$ is $p_{i;n}$ and the dynamics is given by

From now on, we will only consider networks that are undirected (the adjacency matrix is symmetric), connected (there exists a path between all pairs of nodes), non-bipartite (it is not possible to divide the network into two sets of nodes such that there is no link between nodes of the same set), and simple (without self-loops nor multiple links). If the first three conditions are respected, it is easy to show Chung that the stationary solution of the dynamics is generically given by $p_{i}^{*}=k_{i}/W$.

Let us now consider a node partition $\mathcal{P}$ of the network and focus on one community $C\in\mathcal{P}$. If the system is at equilibrium, it is straightforward to show that the probability a random walker is in $C$ on two successive time steps is

while the probability of finding two independent walkers at nodes in $C$ are

This observation allows us to reinterpret $Q$ as a summation over the communities of the difference of these two probabilities. This interpretation suggests natural generalisations of modularity allowing to tune its resolution. Indeed, $Q$ is based on paths of length one but it can readily be generalised to paths of arbitrary length as

where $T_{ij}=A_{ij}/k_{j}$. This quantity is called the stability of the partition delvenne . Because $k_{j}$ is an eigenvector of eigenvalue one of T, one can show that the symmetric matrix $X(n)_{ij}=(T^{n})_{ij}k_{j}$ corresponds to a time-dependent graph where the degree of node $i$ is always equal to $k_{i}$. Therefore $R({\mathbf{\textsf{A}}},n)$ can be interpreted as the modularity of $X(n)_{ij}$, a matrix that connects more and more distant nodes of the original adjacency matrix $A$ as time $n$ grows LDB08 . It can be shown that optimising (5) typically leads to partitions made of larger and larger communities for increasing times and that the optimal partition when $n\rightarrow\infty$ is made of two communities delvenne ; LDB08 .

III Link partition

The above discussion suggests that we should look at a random walker moving on the links of network in order to define the quality of a link partition. Such a walker would therefore be located on the links instead of the nodes at each time $n$ and move between adjacent links, i.e. links having one node in common. In the case of the random walk on the nodes (2), a walker at node $i$ follows one of its links with probability $1/k_{i}$, i.e. all links are treated equally. However, a link between nodes $i$ and $j$ is characterised by two quantities $k_{i}$ and $k_{j}$, so a random walk on the links is more subtle. In the following, we will focus on two different types of dynamical process that account differently for the degrees $k_{i}$ and $k_{j}$ (see Fig. 2).

In the first process, a walker jumps with the same probability $1/(k_{i}+k_{j}-2)$ to one of the links leaving $i$ and $j$. When $k_{i}\neq k_{j}$, the walker goes with a different probability through $i$ or $j$, and we therefore call this process an “link-link random walk” (see Fig 2A).

In the second process, a walker jumps to one of the two nodes too which it is attached, say $i$, then moves to an link attached to that node (excluding the link it came from). Thus it will arrive at an link leaving node $i$ with a probability $1/(2(k_{i}-1))$, and similarly it will arrive at a link attached to the other node $j$ with probability $1/(2(k_{j}-1))$. We will refer to this as a “link-node-link random walk” (see Fig 2B). This process is well-defined unless the link is a leaf, namely one of its extremities has a degree one, say $i$. In that case, the walker will jump with a probability $1/(k_{j}-1)$ to one of the links leaving $j$.

These two types of dynamics are different in general except if the degrees at the extremities $i$ and $j$ of each link are equal. In the case of a connected graph, this condition is equivalent to demanding that the graph is regular, i.e. the degree of all the nodes is a constant. When this condition is not respected, the link-link random walk favours the passage of the walker through the extremity having the largest degree. The difference between the two processes will be maximal when the network is strongly disassortative, namely when links typically relate nodes with very different degrees assortativity .

III.2 Projecting the incidence matrix

In order to study these two types of random walk more carefully, it is useful to represent a network $G$ by its incidence matrix B. The elements $B_{i\alpha}$ of this $N\times L$ matrix ($L$ is the number of links) are equal to $1$ if link $\alpha$ is related to node $i$ and otherwise. The incidence matrix of $G$ may be seen as the adjacency matrix of a bipartite network, $I(G)$ (see Fig.3B), the incidence graphAn incidence graph is usually defined in terms of the incidence of a set of lines with a set of points in a Euclidean space of finite dimension. Here we have a special case where we imbed our graph $G$ in some Euclidean space of no particular interest, and each link of $G$ is a line which always intersects with exactly two points. of $G$ where the two types of nodes correspond to the nodes and the links of the original graph $G$. By construction, all the information of the graph is incorporated in B. For instance, the degree $k_{i}$ of a node $i$ and the number of nodes $k_{\alpha}$ attached to a link $\alpha$ (always equal to two) are given by

The $N\times N$ adjacency matrix A of the graph $G$ can also be obtained

This operation (7) can be interpreted as a projection of the bipartite incidence graph $I(G)$ onto the unipartite network $G$ project1a ; project1b . In a similar way, an adjacency matrix for the links can be obtained by projecting the bipartite network onto its links. In the following, we will focus on two standard types of projection that, as we will show, are directly related to the two random walks introduced above.

III.2.2 Line graph

The simplest way to project a bipartite graph consists of taking all the nodes of one type for the nodes of the projected graph. A link is added between two nodes in this projected graph if these two nodes had at least one node of the other type in common in the original bipartite graph. The operation (7) is of this type. When applied to the links $\alpha$ of the graph $G$, the second type of vertex in the bipartite incidence graph $I(G)$, it leads to the $L\times L$ adjacency matrix $C$ whose elements are

It is easy to verify that this adjacency matrix is symmetric and that its elements are equal to 1 if two links have one node in common, and zero otherwise. It is interesting to note that this adjacency matrix corresponds to another well known graph, usually called the line graph of G line and denoted by $L(G)$ (see Fig.3C). It is a simple graph with $L$ nodes. By construction, each node $i$ of degree $k_{i}$ of the original graph $G$ corresponds to a $k_{i}$ fully connected clique in $L(G)$. Thus it has $\sum_{i}k_{i}(k_{i}-1)/2=O(\langle k^{2}\rangle N)$ links. Line graphs have been studied extensively and among their well-known properties, Whitney’s uniqueness theorem states that the structure of $G$ can be recovered completely from its line graph $L(G)$, for any graph other than a triangle or a star network of four nodes Whitney . This result implies that projecting the incidence matrix onto $L(G)$ does not lead to any loss of information from the network structure. This is a remarkable result that is not generally true when projecting generic bipartite networks.

It is now straightforward to express the dynamics of link-link random walk (Fig.2A) in terms of the projected adjacency matrix $C$

Now $p_{\alpha;n}$ is the density of random walkers on link $\alpha$ at step $n$, $k_{\alpha}=\sum_{\beta}C_{\alpha\beta}=(k_{i}+k_{j}-2)$ and where $i$ and $j$ are the extremities of $\alpha$. This dynamical process therefore only depends on the sum of the degrees $i$ and $j$. The stationary solution is found to be $p_{\alpha}^{*}=k_{\alpha}/W$, where $W=\sum_{\alpha\beta}C_{\alpha\beta}$. When $G$ is simple, then $W=\sum_{i}(k_{i}-1)k_{i}$. By reapplying the steps described in LDB08 , it is now straightforward to derive a quality function for the link partition $\mathcal{P}$ of the graph $G$

This is just the usual modularity (1) for a graph with adjacency matrix C.

As we noted, a single node $i$ in $G$ leads to a connected clique of $k_{i}(k_{i}-1)/2$ links in the line graph $L(G)$. This seems to suggest that the line graph $L(G)$ gives too much prominence to the high degree nodes of the original graph $G$. Our response is to define a weighted line graph whose links are scaled by a factor of $O(1/k_{i})$.

III.2.3 Weighted line graph

In order to derive the quality of a link partition associated to the link-node-link random walk, it is useful to project the incidence matrix in a different way and to define another graph $D(G)$ with a symmetric adjacency matrix given by

This weighted line graph has the intuitive property that the degree $k_{\alpha}=\sum_{\beta}D_{\alpha\beta}$ of a link $\alpha$ is equal to two (a link always has two extremities) unless $\alpha$ is a leaf in $G$ (then $k_{\alpha}=1$ except for one trivial case). For example this weighted line graph of the Bow Tie network is shown in Fig.3D. Only if $G$ is regular will this weighted line graph $D(G)$ be equivalent (up to an overall scale) to the original unweighted line-graph $L(G)$.

This construction is a well-known method for projecting bipartite networks. For instance in the case of collaboration networks project2 the $(k_{i}-1)$ normalisation is justified by the desire that two authors should be less connected if they wrote a joint paper with many co-authors than a paper with few authors.

This weighted line graph allows us to write the dynamics of the link-node-link random walk in a natural way

and, by reusing the above arguments to define another quality function for the link partition $\mathcal{P}$ of a graph

III.3 Projection of a node random walk

The random walks proposed in the previous sections have been defined on the line graph, and therefore consist of walkers moving among adjacent links of the original graph $G$. However, such processes can not be related to the original random walk (3) on the nodes of $G$, because a walker moving on links can pass at two subsequent steps through the same node of $G$ while such self-loops are forbidden in (3). This observation suggests an alternative approach where the dynamics would be driven by the original random walk (3) but would be projected on the links of the network. To do so, let us assume that a walker has not moved yet and is located at node $i$. In that case, it is reasonable to assume that all the neighbouring links of $i$ are connected by a weight $1/k_{i}$. The corresponding adjacency matrix $E$ for the links is therefore given by

E is constructed when a walker is located on a node and has not moved yet. The motion of the walker according to (3) generates a new adjacency matrix, ${\mathbf{\textsf{E}}}_{1}$, defined as

where we note that ${\mathbf{\textsf{E}}}_{1}={\mathbf{\textsf{E}}}{\mathbf{\textsf{E}}}-{\mathbf{\textsf{E}}}$. The corresponding graph is still regular with $k_{\alpha}=\sum_{\beta}E_{1;\alpha\beta}=2$, and it is again weighted with self-loops. The quality function associated with this dynamics is simply

This quality function is particularly interesting because it has a simple relationship to the modularity of the original graph, $Q({\mathbf{\textsf{A}}})$ of (1). To show this let us assign a weight $V_{\alpha c}$ representing the strength of the membership of link $\alpha$ in community $c$. Such weights may be defined and constrained in many ways. For instance, in a link partition we have $V_{\alpha c}V_{\alpha d}=\delta_{cd}$ for any $\alpha$, i.e. every link $\alpha$ belongs to just one community. In order to translate $V_{\alpha c}$ into a community structure on the nodes, it is natural to use the incidence matrix, B of (7) and to define the rectangular matrix $V_{ic}$ through

If $V_{\alpha c}$ is an link partition then the projected node community structure $V_{ic}$ is simply the fraction of links in community $c$ incident at node $i$. Also if $\sum_{c}V_{\alpha c}=1$ then so is $\sum_{c}V_{ic}=1$.

Now using the definition of the adjacency matrix in (7), we find that the modularity of the original graph $G$ for some node community $V_{ic}$ is

Thus finding modularity optimal link partitions of the line graph with adjacency matrix ${\mathbf{\textsf{E}}}_{1}$ of (15), is equivalent to the optimisation of the modularity of the original graph but with a different constraint on the node community $V_{ic}$ from that imposed when finding node partitions.

IV Empirical analysis

In the previous sections, we have proposed three quality functions $Q({\mathbf{\textsf{C}}})$, $Q({\mathbf{\textsf{D}}})$ and $Q({\mathbf{\textsf{E}}}_{1})$ for the partition of the links of a network $G$. Each represents a different dynamical process and therefore explores the structure of the original graph $G$ in a different way. In order to tune the resolution of the optimal partitions, it is straightforward to define the stabilities $R({\mathbf{\textsf{C}}},n)$, $R({\mathbf{\textsf{D}}},n)$ and $R({\mathbf{\textsf{E}}}_{1},n)$ of the three processes by generalising the concept of modularity to paths of arbitrary length (see section II). The optimal partitions of these quality functions can be found by applying standard modularity optimisation algorithms to the corresponding line graphs. In this paper, we have used two different algorithms Blondel ; Rotta and have verified that both algorithms give consistent results.

As a first check, let us look at the Bow Tie graph of Figure 1. The optimisation of the three quality functions $Q({\mathbf{\textsf{C}}})$, $Q({\mathbf{\textsf{D}}})$ and $Q({\mathbf{\textsf{E}}}_{1})$ lead to the expected partition into two triangles, with the values $Q({\mathbf{\textsf{C}}})$=0.1, $Q({\mathbf{\textsf{D}}})=0.278$, $Q({\mathbf{\textsf{E}}}_{1})=0.167$. In this case, the central node belongs equally to the two link communities, a situation which is a far superior way to split the network than a node partition. The best node partition gives $Q({\mathbf{\textsf{A}}})=0.111$ when three nodes in one triangle form one community and the remaining two nodes form a second community.

In order to compare node partitions and link partitions in the following, we will use the idea of a ‘boundary link’ and a ‘boundary node’. A boundary link of a node partition is one which connects two nodes from different communities. We will then define a boundary node of an link partition to be a node which is connected to links from more than one link community. Thus the central node of the Bow Tie graph is a boundary node.

IV.2 Karate Club

A less contrived graph is the Karate club of Zachary Z77 , which is made of thirty four members. Historically this split into two distinct factions. It is standard to compare the partition produced by a community detection method to the actual split of the club. The node partition having the largest value of modularity $Q({\mathbf{\textsf{A}}})=0.420$ contains four communities, but the resolution can be lowered by optimising the stability $R({\mathbf{\textsf{A}}},n)$ for larger values of $n$. When $n$ is large enough, the optimal partition is always made of two communities (see Figure 4), e.g. $R({\mathbf{\textsf{A}}},11)=0.078$, that agree with Zachary’s partition into “sink” and “source” communities Z77 using the Ford-Fulkerson binary community algorithm FF56 .

The link partitions found by optimising $Q({\mathbf{\textsf{C}}})=0.5$, $Q({\mathbf{\textsf{D}}})=0.53$ and $Q({\mathbf{\textsf{E}}}_{1})=0.36$ are shown in Fig. 5. They are respectively made of $4$, $7$ and $3$ communities. These three partitions are consistent with the historical two-way split of the network, as the boundary links of the two-way partition of Fig. 4 are always connected to a boundary node of a link partition. In general, however, the three optimal partitions are as different as their corresponding dynamical processes are. The most striking difference is observed around node $1$. In the node partition optimising $Q({\mathbf{\textsf{A}}})$, this node is connected to several boundary links and connects the community of nodes (5,6,7,11,17) to the rest of the network. Such a position is consistent with the link partitions obtained from $Q({\mathbf{\textsf{D}}})$ and $Q({\mathbf{\textsf{E}}}_{1})$, but not with the link partition optimising $Q({\mathbf{\textsf{C}}})$. In this latter case, one observes that node 1 is rather the focus of one of the link communities on the left hand side in Fig. 5. This difference originates from the high degree of node 1 which implies that a link-link random walk is biased to pass through this node (see Fig. 2), and therefore heavily connects its adjacent links. This is a general problem of the unweighted line graph C that gives too much emphasis to high degree nodes (also noted in ABL09 ) and therefore tends to produces communities centred around hubs. Such a problem does not take place for the weighted line graphs D and ${\mathbf{\textsf{E}}}_{1}$, and in both these cases node 1 is a boundary node, part of several communities. The main difference between the optimal partitions of $Q({\mathbf{\textsf{D}}})$ and $Q({\mathbf{\textsf{E}}}_{1})$ is the number of the communities in each, as expected because the line graph ${\mathbf{\textsf{E}}}_{1}$ connects more distance links of the original graph than D. Let us also note that the optimal partition of $Q({\mathbf{\textsf{E}}}_{1})$ resembles very much the one of $Q({\mathbf{\textsf{A}}})$, as suggested by (20).

Before concluding, let illustrate how longer random walks can be used to tune the resolution of the link partition. We focus on the weighted line graph D, whose optimal partition into seven communities is difficult to compare against the standard two and four community node partitions of Fig. 4. Let us therefore focus on the stability $R({\mathbf{\textsf{D}}},n)$, which is based on paths of length $n$ of a random walker on D. As expected, larger and larger communities are uncovered when $n$ is increased and, when $n$ is large enough, we obtain a two way link partition (see Fig.6) that shows a perfect match with the node partition shown in Fig.4.

IV.3 Word Associations

As a final example, let us use the University of South Florida Free Association Norms data set NMS98 to create a simple networkWe take the sum of the two forward strengths of all pairs of normed word and add a link only if the total is greater than $0.025$. We end up with 5018 words connected by 58536 links and from this a line graph with 1266910 links is created. in the manner of PDF . We obtain a link partition by optimising the modularity for the weighted line graph D of (11) but where the null model term $(k_{\alpha}k_{\beta})/W^{2}$ has been scaled by a factor of $10.0$ in order to control the resolution RB06 and in this case obtain 321 communities in the whole network. The corresponding quality function can be seen as a linear approximation of the stability $R({\mathbf{\textsf{D}}},n)$ LDB08 . It is easier to optimise for large networks.

In Fig.7 we show part of the network near the word ‘bright’ which is part of eleven communitiesThe eleven communities which contain ‘bright’ are well characterised by the following subsets of words:- (‘brave’, ‘bold’, ‘daring’), (‘bright’, ‘light’, ‘sunshine’), (‘gone’, ‘fade’, ‘dim’), (‘power’, ‘electric’, ‘lightening’, ‘flash’), (‘brain’, ‘intelligence’, ‘brilliant’), (‘great’, ‘wonderful’, ‘gifted’), (‘pen’, ‘paper’, ‘highlight’), (‘handle’, ‘lit’, ‘on’, ‘switch’, ‘lever’), (‘cloudy’, ‘gray’, ‘shiny’, ‘sunny’), (‘space’, ‘sky’, ‘moonlight’, ‘stars’), (‘assume’, ‘illusion’, ‘imagination’, ‘vivid’). However ‘bright’ has sixteen of its twenty nine links in the community containing ‘sunshine’ and ‘light’ with just a single link to eight of its eleven communities.. The topology of our communities is much less constrained than those of k-clique percolation PDF which means we can pick out a wider range of structures. There are some tight clique-like subsets, e.g. the names of the planets. At the other extreme the method finds more tree like structures such as the sequence ‘lit-on-switch-lever-handle’ which is the backbone of another community linked to bright. On the other hand this flexibility in the structure can produce a confusing picture since many words are members of several communities though mostly having just one or two links per community. For instance for the word ‘bright’, it is linked to eight of its eleven communities by just one link. However one can exploit this feature to start to define strength of membership in different communities. For instance for visualisation, we have found it useful to view only those words which have a large number of links within one community, as in Fig.7.

V Discussion

When describing a network, there seems to be a natural tendency to put the emphasis on its nodes whereas a graph is a both a set of nodes and a set of links. It is therefore not surprising that node partitioning has been studied extensively in recent years while link partitioning has been overlooked so far. In this paper, we have shown that the quality of a link partition can be evaluated by the modularity of its corresponding line graph. We have highlighted that optimising the modularity of some of our weighted line graphs uncovers meaningful link partitions. Our approach has several advantages. A key criticism of the popular node partitioning methods is that a node must be in one single community whereas it is often more appropriate to attribute a node to several different communities. Link partitioning overcomes this limitation in a natural way. Moreover, the equivalence of a link partition of a graph $G$ with the node partitioning of the corresponding line graph $L(G)$ means that one can use existing node partitioning code with only the expense of producing a line graph transformation and an $O(\langle k^{2}\rangle/\langle k\rangle)$ increase in memory to accommodate the larger line graph. Even the memory cost can be reduced to be $O(1)$ since we have shown our link partitioning is equivalent to a process occurring on the links of the original graph $G$, so a line graph need not be produced explicitly.

Our method can be seen as a generalisation of the popular k-clique percolation PDF , which finds sets of connected k-cliques. By way of comparison we find collections of two-cliques which are more densely connected than expected in an equivalent null model. Thus the link partitioning of our paper can be seen as an extension of two-clique percolation that allows for the uncovering of finer modules, i.e. two-clique percolation trivially uncovers connected components. An interesting generalisation would be to apply our approach to the case of triangles, 4-cliques, etc. To do so, one has to replace the incidence matrix (relating nodes and links) by a more general bipartite graph, representing the membership of nodes in a clique of interest. Our random walk analysis in terms of this bipartite graph would then proceed in the same fashion, and should allow to uncover finer modules than those obtained by k-clique percolation.

All our expressions also hold for the case of weighted networks. Even multiedges can be accommodated if we start from the incidence matrix, B. However the beauty of our approach is that any type of graph analysis, be it community detection or something else, can be applied to a line graph rather than the original graph. In this way, one can view a network from a completely different angle yet use well established techniques to obtain fresh information about its structure.

References