Interest in algorithms for community detection in networked systems has increased over the last decade, mostly motivated by a search for scalable solutions capable of handling large-scale networks. Multilevel approaches provide a potential solution to scalability, as they reduce the cost of a community detection algorithm by applying it to a coarsened version of the original network. The small-scale solution thus obtained is then projected back to the original large-scale model to obtain the desired solution. However, standard multilevel methods are not directly applicable to bipartite network models and the literature lacks studies on multilevel optimization applied to such networks. This article addresses this gap and introduces a novel multilevel method based on onemode projection that allows executing traditional multilevel methods in bipartite network models. The approach has been validated with an algorithm that solves the Barber's modularity problem. It attained improved runtime performance, whilst solution accuracy is shown to be statistically equivalent to that of the standard method.
Complex networks are relational structures that
represent many real-world systems composed by
a large number of highly interconnected
dynamical units. Many such systems exhibit a natural
bipartite (or two-layer) structure, in which the set
of units (known as vertices) is split into two
disjoint subsets (layers) and connections (known as
edges) are established between units placed in
different layers. Document-word
Community structures, defined as groups of
vertices densely connected to each other within a
group, but sparsely connected to other groups,
are an important and frequent property of many
such networks. Vertices that belong to the same
community usually share common properties and
play similar roles in a network system. Therefore,
the identification of a community structure in
networked systems contributes to a better
understanding of their topological structure and dynamical
processes
Community detection algorithms aim at
subdividing a set of vertices into k communities for
minimizing the number of edges connecting
vertices placed in different communities. This is
a hard combinatorial optimization problem, in
which the goal is to optimize a given cost function,
such as modularity
To overcome this problem, researchers have resorted to multilevel approaches, in which: i. an original network is continuously reduced through a collapsing of vertices and edges (coarsening phase); ii. an initial community structure is obtained on the coarsest network (solution phase); and iii. the initial solution is successively projected back over the inverse sequence of coarsened networks, until the original network (projection and refinement phase).
Many multilevel community detection
algorithms have been developed for handling unipartite
or one-mode networks. Some studies introduced
multilevel community detection methods for
specific types of networks; for instance, Abou-Rjeili
and Karypis
However, the above-mentioned approaches are not directly applicable to bipartite networks, since standard coarsening methods rely on collapsing pairs of connected vertices, assuming that all vertices are of the same type. In bipartite networks, vertices in different layers are not connected and should not be collapsed. Coarsening bipartite networks requires collapsing pairs that belong to the same layer (represent entities of the same type) and are not connected by edges.
This article addresses this gap and introduces a novel one-mode projection-based multilevel method that enables applying standard coarsening algorithms to bipartite networks. Tests conducted on a large set of synthetic network models have shown that it can be combined with a community detection method, yielding good speedup with no significant loss in solution quality.
The remainder of the paper is organized as follows: Section 2 reviews some basic concepts on networks and provides a brief overview of standard multilevel approaches; Section 3 introduces the proposed multilevel formulation for bipartite networks and its implementation; Section 4 presents results from an empirical study on a large synthetic test suite; finally, Section 5 summarizes the results and discusses potential applications and future work. 2
This section describes the terminology and fundamental concepts required to understand the proposed solution. 2.1
A unipartite network is given by GpV, E, !q, where V “ tv1, v2, ..., vnu is the set of vertices, E “ te1, e2, ..., eku is the set of edges connecting vertices, such that ei “ pv, uq “ tpu, vq “ pv, uq | u, v P V u and ! “ tw1, w2, ..., wku is the set of weights, so that each wi P R is associated with a corresponding edge ei. Two vertices are said to be neighbors if they are connected by at least one edge.
A bipartite network is given by GpV, E, !q, V is partitioned into two sets V1 and V2 so that V1 X V2 “ H, V1 “ tu1, u2, . . . , unu is a set (or layer) of vertices, V2 “ tv1, v2, . . . , vmu is another set of vertices and E “ te1, e2, ..., eku is the set of edges connecting vertices from different layers, i.e. for all pu, vq P E, u P V1 and v P V2 and E Ñ V1 x V2. Similarly, ! “ tw1, w2, ..., wku is the set of edge weights. Figure 1 illustrates a bipartite network.
Bipartite networks can be transformed into
unipartite networks through one-mode projections
If two vertices share more than a single common neighbor, their connection in the unipartite projection should reflect this topology. In weighted unipartite projections, the number of common neighbors between two vertices is assigned as their edge weight, as illustrated in Figure 3 for a particular pair of projected vertices.
4 1
3 2 5 4 3 5 Multilevel optimization reduces the number of operations required to solve a combinatorial problem. Common applications in the literature include partitioning and community detection algorithms in networks. The rationale behind the multilevel strategy is to execute a complex optimization algorithm, that can not be executed on a very large network, on a reduced version of this network which requires a much smaller number of operations. The results obtained in the smaller network are then projected back to get the solution relative to the original network.
Let us consider a unipartite network
G0pV0, E0, !0q and assume its size (in terms
of edges and vertices) prevents the execution of a
target algorithm. A multilevel approach could be
applied as follows
Initial solution phase. The target algorithm is applied to network Gm. As |Vm| is sufficiently small, the target algorithm can be run in feasible time. In the present study, the target is a community detection algorithm.
Uncoarsening phase. The solution obtained in the coarsest network Gm is projected back, through the intermediate levels Gm´1, Gm´2, ¨ ¨ ¨ , G1, until it is obtained in the network G0.
The coarsening phase is an iterative process that constructs a sequence of reduced versions of the initial network G0. The vertices of a network Gi are collapsed into super-vertices to obtain a network Gi`1. Edges incident to the original vertices are joined to obtain the edges incident to a supervertex. The coarsening process is split into two phases, namely matching and coarsening.
In the matching phase, edges, or vertex pairs, are selected to collapse. Once an edge in Gi has been collapsed, its incident vertices are joined into a super-vertex. Any vertex from Gi with no incident edge selected is inherited by Gi`1. In the present study, we employed two matching methods introduced by Karypis and Kumar (1998), namely: Random Matching (RM). In this approach vertices are visited in a random order. If a vertex v has not been matched yet, one of its unmatched neighbors is selected. If such a vertex u exists, the pair pv, uq is included in the matching set, otherwise v remains unmatched. Although it may yield poor results, RM has complexity Op|E|q.
Heavy edge matching (HEM). This approach minimizes the edge-cut by selecting a maximal matching formed by the edges with heavier weights. Similarly to RM, vertices are also visited in random order. However, unlike RM, vertices v and u are matched if edge pv, uq has maximum weight over all valid edges incident to v. Although HEM does not guarantee that the matching obtained has maximum weight, it yields better results than RM with equivalent asymptotic complexity.
Next, the coarsening phase starts and a coarser network Gi`1 can be created directly from the matching by joining each pair of matched vertices into a single super-vertex (sV ). Edges incident to sV , called super-edges, are obtained by joining the edges incident to vertices tu, vu P Vi. The weight of the resulting super-edge is given by the sum of the weights of all edges incident to tu, vu P Vi.
The target algorithm (community detection, in our case) is then evaluated in the coarsest network Gm to obtain an initial solution. As |VM | † | V0|, the algorithm converges faster and generates an initial solution in feasible time.
In uncoarsening phase, the initial solution is successively projected back to G0. At each level, each super-vertex sv “ tu, vu P Vi`1 is expanded to its original vertices in Vi, i.e. u and v, and the solution is projected through the intermediate levels Gm´1, Gm´2, ..., G0. For each decomposed sv P Vi`, its original vertices tu, vu P Vi are assigned to the same community of their parent sv P Gi. Figure 4 illustrates this process: supervertex sv “ t4, 5u (Figure 4(a)) is expanded to its original vertices 4 and 5, which are assigned to the same community of sv.
2
8 1 3 4,5 (a) 6 9 7 2 3 1 4
5 (b) 6 9 7 8 This section introduces a multilevel community detection method that handles bipartite networks. Standard methods do not consider vertices of different types, whereas in bipartite networks, layers usually represent different types of entities that should be handled independently. Therefore, typical coarsening methods, such as RM or HEM, are not directly applicable. Nonetheless, they can be applied to a projection of G, P “ GV , GU , since in a one-mode projection all vertices are of the same type. Weighted one-mode projection methods enable applying any standard coarsening algorithm to bipartite networks after a transformation process. We rely on this concept to introduce a multilevel community detection method applicable to bipartite networks.
Algorithm 3.1 summarizes the implementation of the proposed one-mode projection-based multilevel community detection (OPM). It comprises the phases of coarsening (lines 1-6), community detection (line 7) and uncoarsening (lines 8-10). The inputs are the initial bipartite network G “ pV, E, , ! q, a maximal number of levels L “ tLi | Li P r0, ns Ä Zu 6 |L| “ 2 and a reduction factor for each layer rf “ trfi | rfi P p0, 0.5s Ä Ru 6 |rf | “ 2.
The bipartite network initially undergoes a
onemode projection transformation, being split into
two unipartite networks G1 and G2. The
coarsening process is then applied to each unipartite
network (line 3), level by level, until each one has
been reduced by the desired factor. The process
comprises a matching step (line 4) and a
coarsening step (line 5). In this study, we have adopted the
aforementioned coarsening and matching methods
HEM and RM
An initial community structure Sl is then obtained on the coarsest bipartite network Gl, at level l (line 7). As Gl and Sl are, respectively, the input and output (Sl representing the community structure of network Gl), different algorithms for community detection can be considered. Depending on the settings of the coarsening phase, the coarsest bipartite network can be very small, so that computationally expensive algorithms can be employed with limited impact on overall performance. Finally, in the subsequent uncoarsening phase (lines 8-10), solution Sl is projected back to G0 through the space of intermediate solutions Sl´1, Sl´2, ..., S1, S0 (line 9). Following the guidelines proposed by Karypis and Kumar (1998) for the uncoarsening process, solution Sl is constructed from Sl`1 simply by assigning vertices tu, vu P Vl to the same community of their parent super-vertex sV P Vl`1. 4
In order to evaluate the proposed solution, we implemented OP M and investigated whether it could yield solutions of quality statistically equivalent to that of a standard community detection approach, whilst increasing its scalability to larger networks.
Beckett
mance relative to the state-of-the-art methods for community detection. However, it is a computationally costly algorithm prohibitive for largescale networks.
We employed our proposed framework to create
a multilevel implementation of LP Awb` (from
now on identified as the OP M algorithm) that
adopts HEM or RM as the coarsening methods,
i.e. OP Mhem and OP Mrm, respectively. Both
were executed with parameters rf “ 0.5 and L “
r1, 2, 3s in a set of 15 synthetic weighted bipartite
networks, identified as R1-R15. The synthetic
networks were obtained by a community model
described by
The performance was measured with the
normalized mutual information (NMI), which
compares a solution found by a particular algorithm
with a reference solution
Table 1 shows the accuracy values measured by NMI on the 15 synthetic networks. The highest values are shown in bold and values equal to or higher than those of the baseline solution are highlighted with a gray background. The best performances were achieved by OP Mhem with one level of coarsening (L “ 1) on 11 out of the 15 networks. The baseline community detection algorithm LP Awb` yielded the best performance in 3 networks, whereas the worst results were obtained with OP Mrm for (L “ 1). In one of on the 15 synthetic networks, OP Mhem and LP Awb` were equivalent.
Indeed, the random strategy RM yields very poor accuracies, which renders its application unfeasible in real contexts. However, the greedy strategy HEM yielded accuracy values similar to those of LP Awb`. Furthermore, limited coarsening levels (mainly L “ 1) yielded higher accuracy values, whereas accuracy decreases as the coarsening level (L “ 3) increases. For L “ 3 the extensive collapsing of vertices tends to blur the boundaries between adjacent communities. The effect of parameter L depends on network size, i.e. 1available from http://igraph.org/python/
LevelsrLs Name differences in algorithm accuracy are likely to decrease as network sizes increase, which suggests that higher values of L might be adopted when handling larger networks.
A Nemenyi post-hoc test (Demsˇar, 2006) was applied to the results in Table 1 to detect statistical differences in the performances of the different algorithms. The results are shown in Figure 5 for (a) L “ 1, (b) L “ 2 and (c) L “ 3. The critical difference (CD) is indicated at the top of each diagram and the methods’ average ranks are placed on the horizontal axes (better ranked on the left). A black line connecting algorithms indicates no significant difference has been detected between them. The critical value of F-statistics with 2 and 28 degrees of freedom and at 90% is 2.50 for all diagrams.
When L “ 1 (Figure 5(a)), OP Mhem was ranked best, followed by LP Awb` and OP Mrm. Furthermore, no statistically significant difference was observed between OP Mhem and LP Awb`. For L “ 2 (Figure 5(b)), OP Mhem and LP Awb` were ranked first, and no statistically significant difference was observed between them. Finally, for L “ 3 (Figure 5(c)) LP Awb` was ranked first, with a statistically significant difference be(c) L “ 3
The scalability of OP M was also assessed considering its performance on each individual network. Table 2 shows the absolute execution times (in seconds) of the algorithm in each network - values refer to average times relative to 30 executions.
The longest execution time of LP Awb` was 302,442 seconds (time to process the largest network, R15) and the shortest was 14 seconds (time to process the smallest one, R1). The most expensive OP Mhem (L “ 1) consumed 36,409 seconds in R15 and 3 seconds in R1. Therefore, OP Mhem run 8.3 to 4.6 times faster than LAP wb`, relative to their maximum and minimum execution times, respectively. The maximum and minimum times of the least expensive OP Mrm (L “ 3) were 903 seconds and 3 seconds, respectively. Therefore, OP Mrm runs 335 to 14 times faster than LAP wb`. 5
This article has introduced an approach that enables using the multilevel paradigm for scaling a community detection algorithm to handle largescale bipartite networks. While previous multilevel methods consider only unipartite networks, our one-mode projection-based multilevel method enables handling bipartite networks with standard coarsening algorithms.
Tests on a large suite of synthetic networks have shown that this solution yields results with accuracy comparable to that of standard methods, demanding considerably shorter execution times. We tested two popular matching strategies for coarsening, namely HEM and RM. RM yielded expressive speedups or even improved the asymptotic convergence, but with poor results regarding accuracy, which prevents its practical application. However, HEM achieved rather good approximation in terms of accuracy and acceptable speedups, e.g., execution times over 8 times shorter as compared to the standard method.
Some issues that deserve further investigation include: using refinement strategies in the uncoarsening process and parallel or distributed paradigms to further increase scalability, as well as further exploring how the choice of rf , the reduction factor parameter, impacts accuracy and speedups.
Author A. Valejo is supported by a scholarship from the Brazilian Federal Agency for Support and Evaluation of Graduate Education (CAPES). This work has been partially supported by the State of Sa˜o Paulo Research Foundation (FAPESP) grants 15/14228-9 and 17/05838-3; and the Brazilian Federal Research Council (CNPq) grants 302645/2015-2 and 305696/2013-0.