As big data is getting collected in every sciences and other applications too, visual analytics is starting to gain traction with graph based applications to help the users understand their data. Community detection has become an important operation in such applications. It reveals the groups that exist within real world networks without imposing prior size or cardinality constraints on the set of communities. The Louvain method is a multi-phase, iterative heuristic for modularity optimization. It was originally developed by Blondel et al. [1], the method has become increasingly popular owing to its ability to detect high modularity community partitions in a fast and memory-e cient manner. To parallelize this solution multiple heuristics are used, that were rst introduced in [2]. For graph organization the ForceAtlas algorithm is used that is part of the Gephi toolkit [3]. This method is responsible to assign coordinates in a 2D space for every node in such a way that they will not overlap on each other. In this paper CPU based parallel implementations are provided for these sequential algorithms, and are tested on a single processor with 8 threads, where a 7 fold performance increase was achieved on test data taken from the CERN developed Collaboration Spotting's database, that involves patents and publications to visualize the connections in technologies among its collaborators.
The Collaboration Spotting [
Interactive means that the user can always navigate the map that he or she is looking at. Every user starts from their own user de ned technology-gram, that is populated by the users as they are exploring the di erent technologies, requesting the connected papers and patents. From there they can start navigating based on di erent properties of the papers and patents at hand. They can take a look at the organizations working on a speci c technology or nding out what kind of keywords the authors used in their respective publications.
The tool is generic as it is capable to handle all kind of data until it ts a prede ned graph database schema. Right now the tool is not only about patents and publications, but within CERN it starts to provide visualization to di erent experiments and departments based on their data and their own needs.
As this application may handle graphs with tens of thousands of nodes and hundreds of thousands of edges per user, it is clear that the overall system needs to be able to process even millions of nodes and edges at any given time. And because the tool is supposed to give an interactive session for every user it has to be fast and reliable to serve the user requests seamlessly.
We take a look at the community detection problem, what procedures are used to do the computations and what heuristics were applied on the system and we will also describe how to make the interactive visualization useful to the users by applying force-directed algorithms on the graphs. Taking all processes and providing parallelization on them, in overall we were able to achive a speedups up to 7. 2
Let G(V; E; !) be an undirected weighted graph, where V represents the set of vertices, E is the set of edges and ! is a weighting function that gives every edge in E a positive weight. If the input graph is unweighted, then we consider the weight of the edges to be 1. The graph is allowed to have loops, so edges like (i; i) are valid, while multiple edges should not be present. Let the adjacency list of vertex i be the following: (i) = jj(i; j) 2 E. Let i denote the weighted degree of vertex i, such as i = Pj2 (i) !(i; j). Let #V denote the number of vertices in graph G, #E the number of edges, and W the sum of all edge weights such as #E = 12 Pi2V i. To detect the communities we would like to partition the vertex set V into an arbitrary number of disjoint communities, each with di erent sizes (0 < n #V ). We will use C(i) to denote the community containing vertex i. Let Ei!C be the set of all edges connecting vertex i to vertices in community C. Also let ei!C contain the sum of the edge weights in Ei!C .
Let degC denote the sum of the degrees of every vertices in community C, which will give us the degree of the whole community.
ei!C =
X (i;j)2Ei!C
!(i; j) degC = X
i i2C
Even with the groups generated by community detection helping to understand what is in the data we are looking at, it is still di cult to handle. To be fully useful we need to provide a readable representation that could be easily understood by users. This helps us to make interactions with the graph possible, while maintaining a fast and versatile system. 2.1
Let S = C1; C2; :::; Ck be the set of every community in a given partitioning of the vertex set V in G(V; E; !),
where 1 k #V . Modularity Q of the partitioning S is given by the following [
X ei!C(i) 2W i2V
X ( degC
2W C2S degC 2W )
Modularity is widely used for community detection while it has issues such as resolution limit [
On a given G(V; E; !) the problem of community detection is to compute the partitioning S of communities
that produces the maximum modularity. This problem has been shown to be NP-Complete [
In 2008 Blondel et al. presented an algorithm for community detection[
Once this calculation is done, the algorithm selects one of the neighboring communities that would provide
the maximum modularity gain, as the new community for i, and it also updates the necessary structures
that are maintained to hold the communities and its properties. On the other hand, if all the gains are
negative, the vertex stays in its own community. An iteration ends once all vertices are checked. As a
result the modularity is a monotonically increasing function, that is spread across the multiple iterations of a
phase. When the algorithm converges within a phase, it moves to the next one by reducing all vertices of a
community to a single "meta-vertex"[
The result is graph G0(V 0; E0; !0), which then becomes the input for the consecutive phase. Multiple phases are processed until the modularity converges. At any given iteration, let Qi!C(j) represent the modularity gain that resulting from moving vertex i from its current community C(i) to a di erent community C(j). This is given by:
Qi!C(j) = ei!C(j) + 2
W i modC(i)=i 2 (2W )2 i modC(j) The new community assignment for vertex i will be determined as follows. For j 2 (i) [ i: C(i) = arg max(j) Qi!C(j)
C
In [
In [
In the parallel algorithm, if at any given iteration the vertex i which is in a community by itself (C(i) = i, singlet
community [
Phases: Execute phases one at a time. Within each phase, multiple iterations are running and each iteration performs a parallel evaluation of the vertices without any locking mechanism using only the community information from the previous iteration. This is going on until the modularity gain between the iterations is not below the threshold.
Graph rebuilding: After a successive phase the new community assignment is used to construct a new input graph for the next phase. This is done by introducing the communities in the new graph as vertices and the edges are added based on their connection to these communities. 17: 18: 19: Qprev 20: end if 21: end while 22: end procedure
Qcurr Compute modularity for new assignments if j QcurQrpreQvprev j < then, being a user speci ed threshold
break else
The cycle in line 4 represents a parallel evaluation of all nodes in the input graph. The possible modularity
gain is calculated for all nodes in parallel with the resulting new collaboration assignment.
The ForceAtlas [
ForceAtlas has two main features, that makes it stand out from other force-directed algorithms: The nal layout highly depends on the given graph's energy model, which represents how the repulsion and attraction is handled.
In a force-directed algorithm, the layout is applied iteratively to the graph. These steps are simulating the movements that will make the system reach the balance. In every step the forces are recomputed and the nodes are moved from their original position according to the results. 5.1
The force-directed algorithms relies on a certain formula to calculate the repulsion and another one to get the attraction. As described above, force-directed algorithms are simulating a physical system, that involves repulsion and attraction. As in any physical system, such forces are proportional to the distance between the interacting nodes. The nodes that are closer to each other has a higher repulsion force, but lesser attraction and vice versa. The proportionality can be linear, exponential or logarithmic. 5.2
ForceAtlas was designed to work well with di erent web graphs and social networks. Commonly these networks have many leaves. This is because of the power-law distribution of degrees that describes many real-world data. The forest of leaves surrounding the highly connected nodes is one of the most signi cant sources of visual cluttering.
To solve this, the idea is to bring less strongly connected nodes closer to highly connected ones. In this algorithm the repulsion force is calculated (Equation 6) in such way so the poorly connected nodes and strongly connected nodes repulse less. As a result they will get closer to each other in the balanced state. The repulsion force Fr is proportional to the degrees plus one of the two nodes. The coe cient kr is provided by the user settings.
Fr(n1; n2) = kr (deg(n1) + 1)(deg(n2) + 1) d(n1; n2)
In this formula the +1 ensures that even nodes with a degree of zero still have some repulsion force. 5.3
The attraction force (Equation 7) Fa between two connected nodes n1 and n2 depends linearly on the distance d(n1; n2).
Fa(n1; n2) = d(n1; n2) 6
As our tool needs to process very big graphs with even tens of thousands of nodes and hundreds of thousand of edges it is important to increase the performance of the ForceAtlas computation too. To optimize the algorithm in the current implementation we worked on the repulsion (Subsection 5.2) and attraction (Subsection 5.3) part of process. The original algorithm was designed with user interaction in mind, which means the user could see some animation as the iterations were progressing. This is a nice feature considering the calculations were running on the client side. Because we would like to focus on performance and thus would push the calculations to the server side, we left this feature out. 6.1
For this part rst we use the Barnes-Hut algorithm [
After this we use the regions as nodes and repulse them from each other. In those cases where the region contains multiple nodes, they will repulse together with the region. Naturally those regions where only one node is present will repulse the node itself.
user provided threshold and coe cient prede ned value, algorithm 2 shows
Using the created regions, a how the repulsion is calculated.
6.2
Here we would like to calculate how the links between the nodes will a ect the repulsion of them. The nodes connected by edges will be attracted to each other, keeping them closer to other connected nodes. All the edges are processed in parallel and because multiple edges can connect to the same node to change the distance of the e ected elements, we use atomic operations to accumulate all the modi cations. Because the distance values are stored as oating point numbers and the generic C++ oating point types do not have atomic addition operations de ned, we use the compare-exchange functions to de ne the summation.
The user can control through the ForceAtlas settings how much the edge weights should in uence the attraction. Di erent graphs possibly will react di erently to a speci c set of settings, resulting in a di erent layout in the end. Users are encouraged to experiment with the di erent values to see how will they yield the best layout that suits best their use cases.
Algorithm 3, using the coe cient prede ned value shows how the attraction is done.
The cycle in line 2 represents the parallel evaluation of the attraction applying on each node of the input graph. 7
For testing purposes we took 4 graphs from the Collaboration Spotting's database, that is based on data, coming from the Web of Knowledge. For the test set the searches were run to gather the papers currently in the database related to 3D, CT, Database and Silicon. The produced graphs are containing all the organizations collaborating on that speci c technology. The reason why we choose these graphs is that they can e ectively demonstrate the use of community detection and layout generation. We will take a look at the details of the graphs as we evaluate the di erent runtimes. The evaluation is strictly done on the described algorithms, the database processing and retrieval time is not under discussion in this paper.
The optimized version is implemented in C++, so for a fair comparison between the two, we prepared the implementation of the standard versions of the Louvain and ForceAtlas algorithms also in the same environment. The tests of both versions were running on the following (Table 1) system:
The optimized version was running on 8 threads in both algorithms. We are interested in examining the performance of the whole compuation, so we measure the runtime on the Louvain community detection algorithm (Section 3) in its entirety, running its original and optimized version on all test graphs and then we do same with the ForceAtlas (Section 5) calculation. These runtimes are compared to each other, showing the performance gain of our modi ed algorithms, while also showing the ratio how these computations are dividing the whole process among them.
For the testing rst we use the graph that contains the collaborators on all the papers that are related to 3D technology. This graph has 35763 nodes and 192336 edges. The runtime of the algorithms on this input can be seen on Figure 1.
These results are showing us that the overall computation time of the original implementation is toriginal = 127; 4s and the optimized version is just toptimized = 21; 8s. For the "3D" graph the original Louvain algorithm took tlouvainoriginal = 92; 2s, the optimized code took tlouvainoptimized = 10; 8s to nish the whole community detection. The original ForceAtlas took tforceatlasoriginal = 35; 2s to nish and the parallel version took only tforceatlasoptimized = 11s to generate the nal balanced layout.
Overall, the full process was able to nish with everything t = 5; 8 times faster on the optimized algorithms. 7.1.2
The next graph contains the collaborators working on papers referring to the CT technology. This graph has 53039 nodes and 325490 edges. The runtime of the processing can be seen on Figure 2.
The results are showing that the overall computation time of the original implementation is toriginal = 243; 82s and the optimized version is handling the same processing in just toptimized = 35; 707s. For the "CT" graph the original Louvain algorithm took tlouvainoriginal = 179; 1s, the optimized took tlouvainoptimized = 18; 1s to fully generate the communities. The original ForceAtlas took tforceatlasoriginal = 64; 72s and the optimized took only tforceatlasoptimized = 17; 6s to return with the nished layout.
For the overall computation of both the community detection and layout generation, the runtime was t = 6; 8 times faster on the optimized algorithms. 7.1.3
The next graph contains the network of collaborators connected to Database technologies. The whole graph consists of 17832 organizations and 113622 corresponding edges among them. The full processes runtime values can be seen on Figure 3.
This shows us that the overall computation time of the original implementation is toriginal = 36; 45s and the optimized version is just toptimized = 7; 44s. For the "Database" graph the original Louvain algorithm took tlouvainoriginal = 20; 5s to nish, while the optimized took only tlouvainoptimized = 2; 6s to return the communities. The original ForceAtlas took tforceatlasoriginal = 15; 95s to generate the layout, while the optimized could nish in tforceatlasoptimized = 4; 84s.
For the overall computation the runtime was t = 4; 89 times faster on the optimized algorithms. 7.1.4
The last graph contains the network connected to technologies working with silicon. This graph has 24923 nodes and 185594 edges. The nal runtime can be seen on Figure 4.
The overall computation time of the original implementation is toriginal = 53; 6s and the optimized version is only toptimized = 11; 67s. For the "Silicon" graph the original Louvain algorithm took tlouvainoriginal = 28; 3s to nish its computations and the optimized took tlouvainoptimized = 3:51s on the same dataset. The original ForceAtlas took tforceatlasoriginal = 25; 3s to process the graph and the optimized was able to conclude in only tforceatlasoptimized = 8; 16s.
For the whole computation on the tested algorithms the overall runtime was t = 4; 6 times faster on the optimized algorithms. 7.2 From the detailed runtimes we can see, that the Louvain computation takes more time to nish from the two algorithms, also it is where the biggest speedup can be achieved. The optimized Louvain algorithm is in average t(louvain) = 9; 1 times faster than the sequential implementation, while the ForceAtlas gains in average a t(forceatlas) = 3; 4 speedup. This happens because of two things: rst the ForceAtlas runs on the quad-tree generated by the Barnes-Hut algorithm to calculate the repulsions (Subsection 6.1) leading to smaller number of nodes than what we have in the original input graphs, requiring less operations to nish the process. On the other hand the Louvain has to check every possible neighbor for the nodes to decide which community will yield the best possible modularity gain (Subsection 3), thus leading to more computation.
The speed up of the Louvain algorithm is in line with the increase of the computing resources, using 8 threads instead of just 1. The higher performance increase can be explained with the usage of the parallel heuristics (Section 4). It reduces the number of operations in the swapping scenarios, where no modularity gain check is required, as the nodes are always simply moved towards the community with a bigger label. Overall the clustering scales well with the available resources.
These can help the Louvain to perform better, than ForceAtlas. Furthermore While the quadratic tree decreases the required amount of computation, it introduces an additional bottleneck in the form of irregular memory accesses. In this case the algorithm cannot e ectively utilize the CPU's caching system, thus reducing the scalability in the current implementation.
While the Louvain algorithm is inherently sequential with the heuristics we can drastically increase the performance of the computation, tlouvainoptimized << tlouvainoriginal . It may be that the ForceAtlas algorithm did not receive such boost in performance, but the gained runtimes from the optimization are still signi cantly better, tforceatlasoptimized < tforceatlasoriginal . 8
As we stand now our work is tested on a single machine, with a single CPU using 8 threads (Section 7). Naturally there is a limit at how much can be processed on such systems and as we are starting a service based on these graph calculations it is given that the system will run on multiple machines utilizing multiple CPUs and much more resources than what was given for the analysis. We have to further explore the possibilities about how much this system can scale on a bigger environment and how much performance boost it can provide using the described techniques. 9
By applying the heuristics described in Section 4 for the Louvain algorithm and by using an optimized version of the ForceAtlas (Section 5) we were able on our biggest test graph about "CT" technology (Subsection 7.1.2) to achieve a t = 6; 8 times overall speedup (Subsection 7.1) compared to the original CPU based implementation. Based on what we see in the detailed analysis (Section 7.2) we can expect the system to scale well on distributed systems when the graph that it's used on does not only have a high volume of edges, but also a larger amount of nodes. In all test cases the community detection enjoyed a signi cantly higher speedup than the ForceAtlas algorithm, thanks to the introduced heuristics (Section 4): tlouvainoptimized << tforceatlasoptimized . Even though the ForceAtlas computation was also more e cient using the parallel solutions (Section 6): tforceatlasoptimized < tforceatlasoriginal . This leads us to the conclusion, the parallel Louvain modularity (Table 1) can greatly improve the overall performance of the computations thanks to the introduced heuristics and the parallel ForceAtlas (Tables 0, 0) also increases the overall experience of the tools usage. Also, this makes the Collaboration Spotting tool capable of handling very large graphs without compromising the users work.
graphs,
Rep. 486 (35) (2010) 75174,