The Louvain method for community detection

叁歲伎倆 2022-06-02 11:38 179阅读 0赞

**The Louvainmethod for community detection**

Louvain method是一个非重叠社团发现的算法，该方法具有较快的执行效率。

对应的paper地址：[http://arxiv.org/abs/0803.0476][http_arxiv.org_abs_0803.0476]

Paper作者对算法的介绍网址：

[http://perso.uclouvain.be/vincent.blondel/research/louvain.html][http_perso.uclouvain.be_vincent.blondel_research_louvain.html]

算法代码下载地址(只有c++版本和matlab版本，没有java版本)：

[https://sites.google.com/site/findcommunities/][https_sites.google.com_site_findcommunities]

找到c++版本时，想改成java版本，无奈发现c++版本里的数据结构略显复杂，失去耐心，就打算自己写一个java版本出来，结果自己写的不仅时间多，而且模块度值与论文中的模块度值也有一定的差距。

于是google到一个别人已经实现的java版本的代码

[http://wiki.cns.iu.edu/display/CISHELL/Louvain+Community+Detection][http_wiki.cns.iu.edu_display_CISHELL_Louvain_Community_Detection]

除了实现Louvain方法之外，他还实现了一个slm算法，并将这几个算法实现打包成jar文件，源码可以在下面的网址中下载到

[http://www.ludowaltman.nl/slm/][http_www.ludowaltman.nl_slm]

算法的总体思想是：

1.刚开始时，每一个节点形成一个小的簇

2.通过模块度函数值优化，将每一个节点归到‘最好’的簇当中去。该步骤知道所有的节点所属的簇不再变化才停止

3.将网络图进行reduce，把一个簇内的所有节点抽象成一个节点，看抽象之后的网络图是否还有优化的可能性。如果有，对抽象之后的图，继续进行第2步。

经过我对其代码的精简，Louvain算法代码如下：

ModularityOptimizer.java

**\[java\]**  [view plain][]  [copy][view plain]

1.  /\*\* 
2.   \* ModularityOptimizer 
3.   \* 
4.   \* @author Ludo Waltman 
5.   \* @author Nees Jan van Eck 
6.   \* @version 1.2.0, 05/14/14 
7.   \*/  
8.    
9.  import java.io.BufferedReader;  
10. import java.io.BufferedWriter;  
11. import java.io.FileReader;  
12. import java.io.FileWriter;  
13. import java.io.IOException;  
14. import java.util.Arrays;  
15. import java.util.Random;  
16.   
17. public class ModularityOptimizer  
18. \{  
19.     public static void main(String\[\] args) throws IOException  
20.     \{  
21.         boolean  update;  
22.          
23.         double modularity, maxModularity, resolution, resolution2;  
24.         int algorithm, i, j, modularityFunction, nClusters, nIterations, nRandomStarts;  
25.         int\[\] cluster;  
26.         long beginTime, endTime;  
27.         Network network;  
28.         Random random;  
29.         String inputFileName, outputFileName;  
30.   
31.           
32.         inputFileName = "fb.txt";  
33.         outputFileName = "communities.txt";  
34.         modularityFunction = 1;  
35.         resolution = 1.0;  
36.         algorithm = 1;  
37.         nRandomStarts = 10;  
38.         nIterations = 3;  
39.                 
40.         System.out.println("Modularity Optimizer version 1.2.0 by Ludo Waltman and Nees Jan van Eck");  
41.         System.out.println();  
42.                               
43.         System.out.println("Reading input file...");  
44.         System.out.println();  
45.           
46.         network = readInputFile(inputFileName, modularityFunction);  
47.         
48.         System.out.format("Number of nodes: %d%n", network.getNNodes());  
49.         System.out.format("Number of edges: %d%n", network.getNEdges() / 2);  
50.         System.out.println();  
51.         System.out.println("Running " + ((algorithm == 1) ? "Louvain algorithm" : ((algorithm == 2) ? "Louvain algorithm with multilevel refinement" : "smart local moving algorithm")) + "...");  
52.         System.out.println();  
53.           
54.         resolution2 = ((modularityFunction == 1) ? (resolution / network.getTotalEdgeWeight()) : resolution);  
55.   
56.         beginTime = System.currentTimeMillis();  
57.         cluster = null;  
58.         nClusters = -1;  
59.         maxModularity = Double.NEGATIVE\_INFINITY;  
60.         random = new Random(100);  
61.         for (i = 0; i < nRandomStarts; i++)  
62.         \{  
63.             if (nRandomStarts > 1)  
64.                 System.out.format("Random start: %d%n", i + 1);  
65.   
66.             network.initSingletonClusters();       //网络初始化，每个节点一个簇  
67.   
68.             j = 0;  
69.             update = true;  
70.             do  
71.             \{  
72.                 if (nIterations > 1)  
73.                     System.out.format("Iteration: %d%n", j + 1);  
74.   
75.                 if (algorithm == 1)  
76.                     update = network.runLouvainAlgorithm(resolution2, random);  
77.            
78.                 j++;  
79.   
80.                 modularity = network.calcQualityFunction(resolution2);  
81.   
82.                 if (nIterations > 1)  
83.                     System.out.format("Modularity: %.4f%n", modularity);  
84.             \}  
85.             while ((j < nIterations) && update);  
86.   
87.             if (modularity > maxModularity)  
88.             \{  
89.              
90.                 cluster = network.getClusters();  
91.                 nClusters = network.getNClusters();  
92.                 maxModularity = modularity;  
93.             \}  
94.   
95.             if (nRandomStarts > 1)  
96.             \{  
97.                 if (nIterations == 1)  
98.                     System.out.format("Modularity: %.4f%n", modularity);  
99.                 System.out.println();  
100.             \}  
101.         \}  
102.         endTime = System.currentTimeMillis();  
103.   
104.           
105.         if (nRandomStarts == 1)  
106.         \{  
107.             if (nIterations > 1)  
108.                 System.out.println();  
109.             System.out.format("Modularity: %.4f%n", maxModularity);  
110.         \}  
111.         else  
112.             System.out.format("Maximum modularity in %d random starts: %.4f%n", nRandomStarts, maxModularity);  
113.         System.out.format("Number of communities: %d%n", nClusters);  
114.         System.out.format("Elapsed time: %d seconds%n", Math.round((endTime - beginTime) / 1000.0));  
115.         System.out.println();  
116.         System.out.println("Writing output file...");  
117.         System.out.println();  
118.          
119.   
120.         writeOutputFile(outputFileName, cluster);  
121.     \}  
122.   
123.     private static Network readInputFile(String fileName, int modularityFunction) throws IOException  
124.     \{  
125.         BufferedReader bufferedReader;  
126.         double\[\] edgeWeight1, edgeWeight2, nodeWeight;  
127.         int i, j, nEdges, nLines, nNodes;  
128.         int\[\] firstNeighborIndex, neighbor, nNeighbors, node1, node2;  
129.         Network network;  
130.         String\[\] splittedLine;  
131.   
132.         bufferedReader = new BufferedReader(new FileReader(fileName));  
133.   
134.         nLines = 0;  
135.         while (bufferedReader.readLine() != null)  
136.             nLines++;  
137.   
138.         bufferedReader.close();  
139.   
140.         bufferedReader = new BufferedReader(new FileReader(fileName));  
141.   
142.         node1 = new int\[nLines\];  
143.         node2 = new int\[nLines\];  
144.         edgeWeight1 = new double\[nLines\];  
145.         i = -1;  
146.         for (j = 0; j < nLines; j++)  
147.         \{  
148.             splittedLine = bufferedReader.readLine().split("\\t");  
149.             node1\[j\] = Integer.parseInt(splittedLine\[0\]);  
150.             if (node1\[j\] > i)  
151.                 i = node1\[j\];  
152.             node2\[j\] = Integer.parseInt(splittedLine\[1\]);  
153.             if (node2\[j\] > i)  
154.                 i = node2\[j\];  
155.             edgeWeight1\[j\] = (splittedLine.length > 2) ? Double.parseDouble(splittedLine\[2\]) : 1;  
156.         \}  
157.         nNodes = i + 1;  
158.   
159.         bufferedReader.close();  
160.   
161.         nNeighbors = new int\[nNodes\];  
162.         for (i = 0; i < nLines; i++)  
163.             if (node1\[i\] < node2\[i\])  
164.             \{  
165.                 nNeighbors\[node1\[i\]\]++;  
166.                 nNeighbors\[node2\[i\]\]++;  
167.             \}  
168.   
169.         firstNeighborIndex = new int\[nNodes + 1\];  
170.         nEdges = 0;  
171.         for (i = 0; i < nNodes; i++)  
172.         \{  
173.             firstNeighborIndex\[i\] = nEdges;  
174.             nEdges += nNeighbors\[i\];  
175.         \}  
176.         firstNeighborIndex\[nNodes\] = nEdges;  
177.   
178.         neighbor = new int\[nEdges\];  
179.         edgeWeight2 = new double\[nEdges\];  
180.         Arrays.fill(nNeighbors, 0);  
181.         for (i = 0; i < nLines; i++)  
182.             if (node1\[i\] < node2\[i\])  
183.             \{  
184.                 j = firstNeighborIndex\[node1\[i\]\] + nNeighbors\[node1\[i\]\];  
185.                 neighbor\[j\] = node2\[i\];  
186.                 edgeWeight2\[j\] = edgeWeight1\[i\];  
187.                 nNeighbors\[node1\[i\]\]++;  
188.                 j = firstNeighborIndex\[node2\[i\]\] + nNeighbors\[node2\[i\]\];  
189.                 neighbor\[j\] = node1\[i\];  
190.                 edgeWeight2\[j\] = edgeWeight1\[i\];  
191.                 nNeighbors\[node2\[i\]\]++;  
192.             \}  
193.   
194.      
195.         \{  
196.             nodeWeight = new double\[nNodes\];  
197.             for (i = 0; i < nEdges; i++)  
198.                 nodeWeight\[neighbor\[i\]\] += edgeWeight2\[i\];  
199.             network = new Network(nNodes, firstNeighborIndex, neighbor, edgeWeight2, nodeWeight);  
200.         \}  
201.         
202.   
203.         return network;  
204.     \}  
205.   
206.     private static void writeOutputFile(String fileName, int\[\] cluster) throws IOException  
207.     \{  
208.         BufferedWriter bufferedWriter;  
209.         int i;  
210.   
211.         bufferedWriter = new BufferedWriter(new FileWriter(fileName));  
212.   
213.         for (i = 0; i < cluster.length; i++)  
214.         \{  
215.             bufferedWriter.write(Integer.toString(cluster\[i\]));  
216.             bufferedWriter.newLine();  
217.         \}  
218.   
219.         bufferedWriter.close();  
220.     \}  
221. \}

Network.java

**\[java\]**  [view plain][]  [copy][view plain]

1.  /\*\* 
2.   \* Network 
3.   \* 
4.   \* @author LudoWaltman 
5.   \* @author Nees Janvan Eck 
6.   \* @version 1.2.0,05/14/14 
7.   \*/  
8.     
9.  import java.io.Serializable;  
10. import java.util.Random;  
11.    
12. public class Network implements Cloneable, Serializable  
13. \{  
14.     private staticfinal long serialVersionUID = 1;  
15.    
16.     private intnNodes;  
17.     private int\[\]firstNeighborIndex;  
18.     private int\[\]neighbor;  
19.     private double\[\]edgeWeight;  
20.    
21.     private double\[\]nodeWeight;  
22.     private intnClusters;  
23.     private int\[\]cluster;  
24.    
25.     private double\[\]clusterWeight;  
26.     private int\[\]nNodesPerCluster;  
27.     private int\[\]\[\]nodePerCluster;  
28.     private booleanclusteringStatsAvailable;  
29.    
30.     publicNetwork(int nNodes, int\[\] firstNeighborIndex, int\[\] neighbor, double\[\]edgeWeight, double\[\] nodeWeight)  
31.     \{  
32.         this(nNodes,firstNeighborIndex, neighbor, edgeWeight, nodeWeight, null);  
33.     \}  
34.    
35.     publicNetwork(int nNodes, int\[\] firstNeighborIndex, int\[\] neighbor, double\[\]edgeWeight, double\[\] nodeWeight, int\[\] cluster)  
36.     \{  
37.         int i,nEdges;  
38.    
39.         this.nNodes= nNodes;  
40.    
41.        this.firstNeighborIndex = firstNeighborIndex;  
42.        this.neighbor = neighbor;  
43.    
44.         if(edgeWeight == null)  
45.         \{  
46.             nEdges =neighbor.length;  
47.            this.edgeWeight = new double\[nEdges\];  
48.             for (i =0; i < nEdges; i++)  
49.                this.edgeWeight\[i\] = 1;  
50.         \}  
51.         else  
52.            this.edgeWeight = edgeWeight;  
53.    
54.         if(nodeWeight == null)  
55.         \{  
56.            this.nodeWeight = new double\[nNodes\];  
57.             for (i =0; i < nNodes; i++)  
58.                 this.nodeWeight\[i\] = 1;  
59.         \}  
60.         else  
61.            this.nodeWeight = nodeWeight;  
62.     
63.     \}  
64.    
65.    
66.     public intgetNNodes()  
67.     \{  
68.         returnnNodes;  
69.     \}  
70.    
71.     public intgetNEdges()  
72.     \{  
73.         returnneighbor.length;  
74.     \}  
75.    
76.      
77.     public doublegetTotalEdgeWeight()  
78.     \{  
79.         doubletotalEdgeWeight;  
80.         int i;  
81.    
82.        totalEdgeWeight = 0;  
83.         for (i = 0;i < neighbor.length; i++)  
84.            totalEdgeWeight += edgeWeight\[i\];  
85.    
86.         returntotalEdgeWeight;  
87.     \}  
88.    
89.     public double\[\] getEdgeWeights()  
90.     \{  
91.         returnedgeWeight;  
92.     \}  
93.    
94.      
95.    
96.     public double\[\]getNodeWeights()  
97.     \{  
98.         returnnodeWeight;  
99.     \}  
100.    
101.     public intgetNClusters()  
102.     \{  
103.         returnnClusters;  
104.     \}  
105.    
106.     public int\[\]getClusters()  
107.     \{  
108.         returncluster;  
109.     \}  
110.    
111.    
112.     public voidinitSingletonClusters()  
113.     \{  
114.         int i;  
115.    
116.         nClusters =nNodes;  
117.         cluster =new int\[nNodes\];  
118.         for (i = 0;i < nNodes; i++)  
119.            cluster\[i\] = i;  
120.    
121.        deleteClusteringStats();  
122.     \}  
123.    
124.     public voidmergeClusters(int\[\] newCluster)  
125.     \{  
126.         int i, j, k;  
127.    
128.         if (cluster== null)  
129.             return;  
130.    
131.         i = 0;  
132.         for (j = 0;j < nNodes; j++)  
133.         \{  
134.             k =newCluster\[cluster\[j\]\];  
135.             if (k> i)  
136.                 i =k;  
137.            cluster\[j\] = k;  
138.         \}  
139.         nClusters =i + 1;  
140.    
141.        deleteClusteringStats();  
142.     \}  
143.      
144.      
145.     public NetworkgetReducedNetwork()  
146.     \{  
147.         double\[\]reducedNetworkEdgeWeight1, reducedNetworkEdgeWeight2;  
148.         int i, j, k,l, m, reducedNetworkNEdges1, reducedNetworkNEdges2;  
149.         int\[\]reducedNetworkNeighbor1, reducedNetworkNeighbor2;  
150.         NetworkreducedNetwork;  
151.    
152.         if (cluster== null)  
153.             returnnull;  
154.    
155.         if(!clusteringStatsAvailable)  
156.            calcClusteringStats();  
157.    
158.        reducedNetwork = new Network();  
159.    
160.        reducedNetwork.nNodes = nClusters;  
161.        reducedNetwork.firstNeighborIndex = new int\[nClusters + 1\];  
162.        
163.        reducedNetwork.nodeWeight = new double\[nClusters\];  
164.    
165.        reducedNetworkNeighbor1 = new int\[neighbor.length\];  
166.        reducedNetworkEdgeWeight1 = new double\[edgeWeight.length\];  
167.    
168.        reducedNetworkNeighbor2 = new int\[nClusters - 1\];  
169.        reducedNetworkEdgeWeight2 = new double\[nClusters\];  
170.    
171.        reducedNetworkNEdges1 = 0;  
172.         for (i = 0;i < nClusters; i++)  
173.         \{  
174.            reducedNetworkNEdges2 = 0;  
175.             for (j = 0; j <nodePerCluster\[i\].length; j++)  
176.             \{  
177.                 k =nodePerCluster\[i\]\[j\];           //k是簇i中第j个节点的id  
178.    
179.                 for(l = firstNeighborIndex\[k\]; l < firstNeighborIndex\[k + 1\]; l++)  
180.                 \{  
181.                     m = cluster\[neighbor\[l\]\];       //m是k的在l位置的邻居节点所属的簇id  
182.                    if (m != i)  
183.                    \{  
184.                        if (reducedNetworkEdgeWeight2\[m\] == 0)  
185.                        \{  
186.                            reducedNetworkNeighbor2\[reducedNetworkNEdges2\] = m;  
187.                            reducedNetworkNEdges2++;  
188.                        \}  
189.                        reducedNetworkEdgeWeight2\[m\] += edgeWeight\[l\];  
190.                    \}  
191.                 
192.                 \}  
193.    
194.                reducedNetwork.nodeWeight\[i\] += nodeWeight\[k\];  
195.             \}  
196.    
197.             for (j =0; j < reducedNetworkNEdges2; j++)  
198.             \{  
199.                reducedNetworkNeighbor1\[reducedNetworkNEdges1 + j\] = reducedNetworkNeighbor2\[j\];  
200.                reducedNetworkEdgeWeight1\[reducedNetworkNEdges1 + j\] =reducedNetworkEdgeWeight2\[reducedNetworkNeighbor2\[j\]\];  
201.                reducedNetworkEdgeWeight2\[reducedNetworkNeighbor2\[j\]\] = 0;  
202.             \}  
203.            reducedNetworkNEdges1 += reducedNetworkNEdges2;  
204.    
205.            reducedNetwork.firstNeighborIndex\[i + 1\] = reducedNetworkNEdges1;  
206.         \}  
207.    
208.        reducedNetwork.neighbor = new int\[reducedNetworkNEdges1\];  
209.        reducedNetwork.edgeWeight = new double\[reducedNetworkNEdges1\];  
210.        System.arraycopy(reducedNetworkNeighbor1, 0, reducedNetwork.neighbor, 0,reducedNetworkNEdges1);  
211.        System.arraycopy(reducedNetworkEdgeWeight1, 0,reducedNetwork.edgeWeight, 0, reducedNetworkNEdges1);  
212.    
213.         returnreducedNetwork;  
214.     \}  
215.      
216.    
217.     public doublecalcQualityFunction(double resolution)  
218.     \{  
219.         doublequalityFunction, totalEdgeWeight;  
220.         int i, j, k;  
221.    
222.         if (cluster== null)  
223.             returnDouble.NaN;  
224.    
225.         if(!clusteringStatsAvailable)  
226.            calcClusteringStats();  
227.    
228.        qualityFunction = 0;  
229.                
230.        totalEdgeWeight = 0;  
231.         for (i = 0;i < nNodes; i++)  
232.         \{  
233.             j =cluster\[i\];  
234.             for (k =firstNeighborIndex\[i\]; k < firstNeighborIndex\[i + 1\]; k++)  
235.             \{  
236.                 if(cluster\[neighbor\[k\]\] == j)  
237.                    qualityFunction += edgeWeight\[k\];  
238.                totalEdgeWeight += edgeWeight\[k\];  
239.             \}  
240.         \}  
241.    
242.         for (i = 0;i < nClusters; i++)  
243.            qualityFunction -= clusterWeight\[i\] \* clusterWeight\[i\] \* resolution;  
244.    
245.        qualityFunction /= totalEdgeWeight;  
246.    
247.         returnqualityFunction;  
248.     \}  
249.    
250.      
251.     public booleanrunLocalMovingAlgorithm(double resolution)  
252.     \{  
253.         returnrunLocalMovingAlgorithm(resolution, new Random());  
254.     \}  
255.    
256.     public booleanrunLocalMovingAlgorithm(double resolution, Random random)  
257.     \{  
258.         booleanupdate;  
259.         doublemaxQualityFunction, qualityFunction;  
260.         double\[\]clusterWeight, edgeWeightPerCluster;  
261.         intbestCluster, i, j, k, l, nNeighboringClusters, nStableNodes, nUnusedClusters;  
262.         int\[\]neighboringCluster, newCluster, nNodesPerCluster, nodeOrder, unusedCluster;  
263.    
264.         if ((cluster== null) || (nNodes == 1))  
265.             returnfalse;  
266.    
267.         update =false;  
268.    
269.        clusterWeight = new double\[nNodes\];  
270.        nNodesPerCluster = new int\[nNodes\];  
271.         for (i = 0;i < nNodes; i++)  
272.         \{  
273.            clusterWeight\[cluster\[i\]\] += nodeWeight\[i\];  
274.            nNodesPerCluster\[cluster\[i\]\]++;  
275.         \}  
276.    
277.        nUnusedClusters = 0;  
278.        unusedCluster = new int\[nNodes\];  
279.         for (i = 0;i < nNodes; i++)  
280.             if(nNodesPerCluster\[i\] == 0)  
281.             \{  
282.                unusedCluster\[nUnusedClusters\] = i;  
283.                nUnusedClusters++;  
284.             \}  
285.    
286.         nodeOrder =new int\[nNodes\];  
287.         for (i = 0;i < nNodes; i++)  
288.            nodeOrder\[i\] = i;  
289.         for (i = 0;i < nNodes; i++)  
290.         \{  
291.             j = random.nextInt(nNodes);  
292.             k =nodeOrder\[i\];  
293.            nodeOrder\[i\] = nodeOrder\[j\];  
294.            nodeOrder\[j\] = k;  
295.         \}  
296.    
297.        edgeWeightPerCluster = new double\[nNodes\];  
298.        neighboringCluster = new int\[nNodes - 1\];  
299.    
300.         nStableNodes = 0;  
301.         i = 0;  
302.         do  
303.         \{  
304.             j =nodeOrder\[i\];  
305.    
306.            nNeighboringClusters = 0;  
307.             for (k =firstNeighborIndex\[j\]; k < firstNeighborIndex\[j + 1\]; k++)  
308.             \{  
309.                 l =cluster\[neighbor\[k\]\];  
310.                 if(edgeWeightPerCluster\[l\] == 0)  
311.                 \{  
312.                    neighboringCluster\[nNeighboringClusters\] = l;  
313.                    nNeighboringClusters++;  
314.                 \}  
315.                 edgeWeightPerCluster\[l\]+= edgeWeight\[k\];  
316.             \}  
317.    
318.            clusterWeight\[cluster\[j\]\] -= nodeWeight\[j\];  
319.            nNodesPerCluster\[cluster\[j\]\]--;  
320.             if(nNodesPerCluster\[cluster\[j\]\] == 0)  
321.             \{  
322.                unusedCluster\[nUnusedClusters\] = cluster\[j\];  
323.                nUnusedClusters++;  
324.             \}  
325.    
326.            bestCluster = -1;  
327.            maxQualityFunction = 0;  
328.             for (k =0; k < nNeighboringClusters; k++)  
329.             \{  
330.                 l =neighboringCluster\[k\];  
331.                qualityFunction = edgeWeightPerCluster\[l\] - nodeWeight\[j\] \*clusterWeight\[l\] \* resolution;  
332.                 if((qualityFunction > maxQualityFunction) || ((qualityFunction ==maxQualityFunction) && (l < bestCluster)))  
333.                 \{  
334.                     bestCluster = l;  
335.                    maxQualityFunction = qualityFunction;  
336.                 \}  
337.                edgeWeightPerCluster\[l\] = 0;  
338.             \}  
339.             if(maxQualityFunction == 0)  
340.             \{  
341.                bestCluster = unusedCluster\[nUnusedClusters - 1\];  
342.                nUnusedClusters--;  
343.             \}  
344.    
345.            clusterWeight\[bestCluster\] += nodeWeight\[j\];  
346.            nNodesPerCluster\[bestCluster\]++;  
347.             if(bestCluster == cluster\[j\])  
348.                nStableNodes++;  
349.             else  
350.             \{  
351.                cluster\[j\] = bestCluster;  
352.                nStableNodes = 1;  
353.                update = true;  
354.             \}  
355.    
356.             i = (i< nNodes - 1) ? (i + 1) : 0;  
357.         \}  
358.         while(nStableNodes < nNodes);             //优化步骤是直到所有的点都稳定下来才结束  
359.    
360.         newCluster =new int\[nNodes\];  
361.         nClusters =0;  
362.         for (i = 0;i < nNodes; i++)  
363.             if(nNodesPerCluster\[i\] > 0)  
364.             \{  
365.                newCluster\[i\] = nClusters;  
366.                nClusters++;  
367.             \}  
368.         for (i = 0;i < nNodes; i++)  
369.            cluster\[i\] = newCluster\[cluster\[i\]\];  
370.    
371.        deleteClusteringStats();  
372.    
373.         returnupdate;  
374.     \}  
375.      
376.      
377.    
378.     public booleanrunLouvainAlgorithm(double resolution)  
379.     \{  
380.         return runLouvainAlgorithm(resolution,new Random());  
381.     \}  
382.    
383.     public booleanrunLouvainAlgorithm(double resolution, Random random)  
384.     \{  
385.         booleanupdate, update2;  
386.         NetworkreducedNetwork;  
387.    
388.         if ((cluster== null) || (nNodes == 1))  
389.             returnfalse;  
390.    
391.         update =runLocalMovingAlgorithm(resolution, random);  
392.    
393.         if(nClusters < nNodes)  
394.         \{  
395.            reducedNetwork = getReducedNetwork();  
396.            reducedNetwork.initSingletonClusters();  
397.    
398.             update2= reducedNetwork.runLouvainAlgorithm(resolution, random);  
399.    
400.             if(update2)  
401.             \{  
402.                update = true;  
403.    
404.                mergeClusters(reducedNetwork.getClusters());  
405.             \}  
406.         \}  
407.    
408.        deleteClusteringStats();  
409.    
410.         return update;  
411.     \}  
412.    
413.    
414.     privateNetwork()  
415.     \{  
416.     \}  
417.     
418.    
419.     private voidcalcClusteringStats()  
420.     \{  
421.         int i, j;  
422.    
423.        clusterWeight = new double\[nClusters\];  
424.        nNodesPerCluster = new int\[nClusters\];  
425.        nodePerCluster = new int\[nClusters\]\[\];  
426.    
427.         for (i = 0;i < nNodes; i++)  
428.         \{  
429.            clusterWeight\[cluster\[i\]\] += nodeWeight\[i\];  
430.            nNodesPerCluster\[cluster\[i\]\]++;  
431.         \}  
432.    
433.         for (i = 0;i < nClusters; i++)  
434.         \{  
435.            nodePerCluster\[i\] = new int\[nNodesPerCluster\[i\]\];  
436.            nNodesPerCluster\[i\] = 0;  
437.         \}  
438.    
439.         for (i = 0;i < nNodes; i++)  
440.         \{  
441.             j =cluster\[i\];  
442.            nodePerCluster\[j\]\[nNodesPerCluster\[j\]\] = i;  
443.             nNodesPerCluster\[j\]++;  
444.         \}  
445.    
446.        clusteringStatsAvailable = true;  
447.     \}  
448.    
449.      
450.     private voiddeleteClusteringStats()  
451.     \{  
452.        clusterWeight = null;  
453.        nNodesPerCluster = null;  
454.        nodePerCluster = null;  
455.    
456.        clusteringStatsAvailable = false;  
457.     \}  
458. \}

算法的效果

对karate数据集

![Center][]

分簇结果

![Center 1][]

在facebook，4039个数据集上的结果

![Center 2][]

下载的java 版本代码不好理解，尤其是 firstneighborindex 等数组表示什么意思等，于是我借鉴它，实现了一个新的版本，这里面的代码容易理解一些，并且给里面的变量、函数以及关键步骤都加了一些注释

而且在代码中增加了输出分簇之后的网络图的功能，输出一个gml文件，输入节点的节点和边信息都保留了，初次之外，加上了分簇的结果，即每一个节点属于哪一个簇，在node中加了一个type字段来表示，这样就可以在gephi中直接依据type字段来查看分割好的社团。

与下载的不一致的是，我们的输入文件第一行需要给出网络中节点的数量

以下是程序的代码

DataSet.java

**\[java\]**  [view plain][]  [copy][view plain]

1.  packagecommunitydetection;  
2.     
3.  importjava.io.\*;  
4.  importjava.util.\*;  
5.     
6.  public classDataSet \{  
7.       
8.      double weight\[\]\[\];  
9.       
10.     LinkedList neighborlist\[\];  
11.      
12.     double totalEdgeWeights = 0;  
13.      
14.     int nodecount;  
15.      
16.     double nodeweight\[\];  
17.      
18.     DataSet(String filename) throws IOException  
19.     \{  
20.        BufferedReader reader = newBufferedReader(new FileReader(filename));  
21.         
22.        String line = reader.readLine();  
23.        nodecount = Integer.parseInt(line);    //读文件，文件第一行为节点的数量  
24.         
25.        weight = new double\[nodecount\]\[nodecount\];       
26.         
27.        neighborlist = new LinkedList\[nodecount\];  
28.        for(int i=0 ;i < nodecount;i++)  
29.            neighborlist\[i\] = newLinkedList<Integer>();  
30.         
31.        nodeweight = new double\[nodecount\];  
32.        for(int i=0;i<nodecount;i++)  
33.            nodeweight\[i\] = 0;  
34.         
35.        while((line = reader.readLine())!=null)  
36.        \{  
37.            String args\[\] =line.split("\\t");  
38.            int node1 =Integer.parseInt(args\[0\]);  
39.            int node2 = Integer.parseInt(args\[1\]);  
40.             
41.            if(node1 != node2)  
42.            \{  
43.               neighborlist\[node1\].add(node2);  
44.               neighborlist\[node2\].add(node1);  
45.            \}  
46.             
47.            if(args.length > 2)  
48.            \{  
49.               double we =Double.parseDouble(args\[2\]);  
50.               weight\[node1\]\[node2\] = we;  
51.               weight\[node2\]\[node1\] = we;              
52.               totalEdgeWeights += we;  
53.    
54.               nodeweight\[node1\] += we;  
55.               if(node2 != node1)  
56.                   nodeweight\[node2\] += we;  
57.                
58.            \}  
59.            else  
60.            \{  
61.               weight\[node1\]\[node2\] = 1;  
62.               weight\[node2\]\[node1\] = 1;  
63.               totalEdgeWeights += 1;  
64.                
65.               nodeweight\[node1\] += 1;  
66.               if(node2 != node1)  
67.                   nodeweight\[node2\] += 1;  
68.            \}  
69.                       
70.        \}  
71.         
72.                
73.        reader.close();  
74.     \}  
75.      
76.      
77.      
78. \}

NetWork.java

**\[java\]**  [view plain][]  [copy][view plain]

1.  package communitydetection;  
2.  import java.util.\*;  
3.  import java.io.\*;  
4.     
5.  public class NetWork \{  
6.     
7.         double weight\[\]\[\];                    //图中两节点的连接边的权重  
8.          
9.         LinkedListneighborlist\[\];            //每个节点的邻居节点有哪些  
10.                
11.        doublenodeweight\[\];                  //每个节点的权值  
12.                
13.        intnodecount;                        //图中节点的总数量  
14.         
15.        intcluster\[\];                        //记录每个节点属于哪一个簇  
16.         
17.        intclustercount;                     //簇的总数量  
18.         
19.        doubleclusterweight\[\];               //每一个簇的权重  
20.         
21.        booleanclusteringStatsAvailable ;    //当前的网络信息是否完全  
22.         
23.        intnodecountsPercluster\[\];           //每个簇有多少个节点  
24.        intnodePercluster\[\]\[\];               //nodePercluster\[i\]\[j\]表示簇i中第j个节点的id  
25.         
26.        NetWork(Stringfilename) throws IOException  
27.        \{  
28.               DataSetds = new DataSet(filename);         //ds是用来读取输入文件内容的  
29.               weight= ds.weight;  
30.               neighborlist= ds.neighborlist;  
31.         
32.               nodecount= ds.nodecount;             
33.               nodeweight= ds.nodeweight;  
34.                
35.               initSingletonClusters();             
36.                       
37.        \}  
38.         
39.        NetWork()  
40.        \{  
41.                
42.        \}  
43.         
44.        publicdouble getTotalEdgeWeight()            //获取网络图中所有的边的权值之和, 返回的结果实际上是2倍  
45.     \{                                                                             //因为每一条边被计算了2次  
46.         doubletotalEdgeWeight;  
47.         int i;  
48.    
49.        totalEdgeWeight = 0;  
50.    
51.         for (i= 0; i < nodecount; i++)  
52.         \{  
53.              for(intj=0;j<neighborlist\[i\].size();j++)  
54.              \{  
55.                     int neighborid =(Integer)neighborlist\[i\].get(j);  
56.                     totalEdgeWeight +=weight\[i\]\[neighborid\];  
57.              \}  
58.         \}  
59.    
60.         returntotalEdgeWeight;  
61.     \}  
62.    
63.           
64.     publicvoid initSingletonClusters()           //给每个节点指派一个簇  
65.     \{  
66.         int i;  
67.    
68.        clustercount = nodecount;  
69.        cluster = new int\[nodecount\];  
70.         for (i= 0; i < nodecount; i++)  
71.            cluster\[i\] = i;  
72.    
73.        deleteClusteringStats();                    
74.     \}  
75.         
76.                
77.     privatevoid calcClusteringStats()             //统计好每个簇有多少个节点，以及每个簇中的节点都有哪些  
78.     \{  
79.         int i,j;  
80.    
81.        clusterweight = new double\[clustercount\];  
82.        nodecountsPercluster = new int\[clustercount\];  
83.        nodePercluster = new int\[clustercount\]\[\];  
84.    
85.         for (i= 0; i < nodecount; i++)  
86.         \{    
87.              //计算每一个簇的权值，簇的权值是其中的节点的权值之和  
88.            clusterweight\[cluster\[i\]\] += nodeweight\[i\];  
89.            nodecountsPercluster\[cluster\[i\]\]++;  
90.         \}  
91.    
92.         for (i= 0; i < clustercount; i++)  
93.         \{  
94.            nodePercluster\[i\] = new int\[nodecountsPercluster\[i\]\];  
95.            nodecountsPercluster\[i\] = 0;  
96.         \}  
97.    
98.         for (i= 0; i < nodecount; i++)  
99.         \{  
100.             j= cluster\[i\];            //j是簇编号, 记录每一个簇中的第几个节点的id  
101.            nodePercluster\[j\]\[nodecountsPercluster\[j\]\] = i;  
102.           nodecountsPercluster\[j\]++;  
103.         \}  
104.    
105.        clusteringStatsAvailable = true;  
106.     \}  
107.      
108.       
109.         
110.     privatevoid deleteClusteringStats()  
111.     \{  
112.        clusterweight = null;  
113.        nodecountsPercluster = null;  
114.        nodePercluster = null;  
115.    
116.        clusteringStatsAvailable = false;  
117.     \}  
118.    
119.     publicint\[\] getClusters()  
120.     \{  
121.         returncluster;  
122.     \}  
123.      
124.      
125.     publicdouble calcQualityFunction(double resolution)       //计算模块度的值, 如果所有边的权重之和为m  
126.     \{                                                                                                  //那么resolution就是1/(2m)    
127.         doublequalityFunction, totalEdgeWeight;  
128.         int i,j, k;  
129.    
130.         if(cluster == null)  
131.            return Double.NaN;  
132.    
133.         if(!clusteringStatsAvailable)  
134.            calcClusteringStats();  
135.    
136.        qualityFunction = 0;  
137.          
138.        totalEdgeWeight = 0;  
139.      
140.         for (i= 0; i < nodecount; i++)  
141.         \{  
142.             j= cluster\[i\];  
143.              
144.            for( k=0;k<neighborlist\[i\].size();k++)  
145.             \{  
146.                 int neighborid =(Integer)neighborlist\[i\].get(k);  
147.                 if(cluster\[neighborid\] == j)  
148.                        qualityFunction += weight\[i\]\[neighborid\];  
149.                 totalEdgeWeight += weight\[i\]\[neighborid\];  
150.             \}                                                                                      //最终的totalEdgeWeight也是  
151.                                                                                                          //图中所有边权重之和的2倍  
152.         \}  
153.    
154.         for (i= 0; i < clustercount; i++)  
155.            qualityFunction -= clusterweight\[i\] \* clusterweight\[i\] \* resolution;  
156.    
157.        qualityFunction /= totalEdgeWeight;  
158.    
159.         returnqualityFunction;  
160.     \}  
161.    
162.     public intgetNClusters()  
163.     \{  
164.         returnclustercount;  
165.     \}  
166.      
167.     public voidmergeClusters(int\[\] newCluster) //newcluster是reduced之后的reducednetwork中的所属簇信息  
168.     \{                                                                           
169.         int i,j, k;                                                
170.    
171.         if(cluster == null)  
172.            return;  
173.    
174.         i = 0;  
175.         for (j= 0; j < nodecount; j++)  
176.         \{  
177.             k= newCluster\[cluster\[j\]\];      //reducednetwork中的newcluster的一个下标相当于        
178.             if(k > i)                                          //reduce之前的网络中的每一个簇  
179.                i = k;  
180.            cluster\[j\] = k;  
181.         \}  
182.        clustercount = i + 1;  
183.    
184.        deleteClusteringStats();  
185.     \}  
186.      
187.     publicNetWork getReducedNetwork()            //将整个网络进行reduce操作  
188.     \{  
189.        double\[\] reducedNetworkEdgeWeight2;  
190.         int i,j, k, l, m,reducedNetworkNEdges2;  
191.        int\[\]  reducedNetworkNeighbor2;  
192.        NetWork reducedNetwork;  
193.    
194.         if (cluster== null)  
195.            return null;  
196.    
197.         if(!clusteringStatsAvailable)  
198.            calcClusteringStats();  
199.    
200.        reducedNetwork = new NetWork();  
201.    
202.        reducedNetwork.nodecount = clustercount;    //reduce之后，原来的一个簇就是现在的一个节点  
203.     
204.        reducedNetwork.neighborlist = new LinkedList\[clustercount\];  
205.         for(i=0;i<clustercount;i++)  
206.              reducedNetwork.neighborlist\[i\] = newLinkedList();  
207.          
208.          
209.        reducedNetwork.nodeweight = new double\[clustercount\];  
210.          
211.        reducedNetwork.weight = new double\[clustercount\]\[clustercount\];  
212.          
213.          
214.        reducedNetworkNeighbor2 = new int\[clustercount -1\];  
215.        reducedNetworkEdgeWeight2 = new double\[clustercount\];  
216.    
217.    
218.         for (i= 0; i < clustercount; i++)  
219.         \{  
220.            reducedNetworkNEdges2 = 0;  
221.            for (j = 0; j < nodePercluster\[i\].length; j++)  
222.             \{  
223.                k = nodePercluster\[i\]\[j\];          //k是原来的簇i中第j个节点的id  
224.    
225.                for( l=0;l<neighborlist\[k\].size();l++)  
226.                 \{  
227.                   int nodeid =(Integer)neighborlist\[k\].get(l);  
228.                   m = cluster\[nodeid\];  
229.                    
230.                   if( m != i)    //reduce之前簇i与簇m相连，应为它们之间有边存在，edge(k,nodeid)  
231.                   \{  
232.                          if(reducedNetworkEdgeWeight2\[m\]== 0)  
233.                          \{  
234.                                 //以前的簇邻居变成了现在的节点邻居  
235.                                 reducedNetworkNeighbor2\[reducedNetworkNEdges2\]= m;  
236.                                 reducedNetworkNEdges2++;  
237.                                 //reducedNetworkEdges记录在新的图中新的节点i(原来的簇i)有多少个邻居  
238.                          \}  
239.                          reducedNetworkEdgeWeight2\[m\]+= weight\[k\]\[nodeid\];  
240.                          //新的节点i与新的邻居节点m的之间的边权重的更新  
241.                   \}  
242.                                                  
243.                \}  
244.                  
245.                reducedNetwork.nodeweight\[i\] += nodeweight\[k\];  
246.                //现在的节点i是以前的簇i, 以前的节点k在以前的簇i中，所以现在的节点i的权重包含以前节点k的权重  
247.             \}  
248.             
249.             
250.            for (j = 0; j < reducedNetworkNEdges2; j++)  
251.             \{  
252.                reducedNetwork.neighborlist\[i\].add(reducedNetworkNeighbor2\[j\]);  
253.                reducedNetwork.weight\[i\]\[reducedNetworkNeighbor2\[j\]\] =reducedNetworkEdgeWeight2\[reducedNetworkNeighbor2\[j\]\];  
254.                reducedNetworkEdgeWeight2\[reducedNetworkNeighbor2\[j\]\] = 0;                 
255.                // =0是为了数组复用，不然每次都要开辟新的数组存放与新的邻居节点之间的边的权值  
256.             \}  
257.              
258.         \}  
259.                     
260.         returnreducedNetwork;  
261.     \}  
262.      
263.     
264.     publicboolean runLocalMovingAlgorithm(double resolution)  
265.     \{  
266.         returnrunLocalMovingAlgorithm(resolution, new Random());  
267.     \}  
268.      
269.     //将每一个节点移入到'最好'的簇当中去  
270.     publicboolean runLocalMovingAlgorithm(double resolution, Random random)  
271.     \{  
272.        boolean update;  
273.         doublemaxQualityFunction, qualityFunction;  
274.        double\[\] clusterWeight, edgeWeightPerCluster;  
275.         intbestCluster, i, j, k, l, nNeighboringClusters, nStableNodes, nUnusedClusters;  
276.         int\[\]neighboringCluster, newCluster, nNodesPerCluster, nodeOrder, unusedCluster;  
277.    
278.         if((cluster == null) || (nodecount == 1))  
279.            return false;  
280.    
281.         update= false;  
282.    
283.        clusterWeight = new double\[nodecount\];  
284.        nNodesPerCluster = new int\[nodecount\];       //记录每一个簇中有多少个节点  
285.         for (i = 0; i < nodecount; i++)  
286.         \{  
287.            clusterWeight\[cluster\[i\]\] += nodeweight\[i\];  
288.            nNodesPerCluster\[cluster\[i\]\]++;  
289.         \}  
290.    
291.        nUnusedClusters = 0;  
292.        unusedCluster = new int\[nodecount\];        //统计在整个过程当中，哪些簇一个节点也没有  
293.         for (i= 0; i <nodecount; i++)             //这些簇在之后会被消除  
294.             if(nNodesPerCluster\[i\] == 0)  
295.             \{  
296.                unusedCluster\[nUnusedClusters\] = i;  
297.                nUnusedClusters++;  
298.             \}  
299.    
300.        nodeOrder = new int\[nodecount\];  
301.         for (i= 0; i < nodecount; i++)  
302.            nodeOrder\[i\] = i;  
303.         for (i= 0; i < nodecount; i++)    //nodeOrder将节点顺序打乱，防止由于顺序问题得不到最好的结果  
304.         \{  
305.             j= random.nextInt(nodecount);  
306.             k= nodeOrder\[i\];  
307.            nodeOrder\[i\] = nodeOrder\[j\];  
308.            nodeOrder\[j\] = k;  
309.         \}  
310.    
311.        edgeWeightPerCluster = new double\[nodecount\];  
312.        neighboringCluster = new int\[nodecount -1\];  
313.    
314.        nStableNodes = 0;  
315.         i = 0;  
316.         do  
317.         \{  
318.             j= nodeOrder\[i\];             //j是某一个节点的编号  
319.    
320.            nNeighboringClusters = 0;  
321.             
322.              
323.            for(k = 0; k<neighborlist\[j\].size();k++)  
324.             \{  
325.                 int nodeid =(Integer)neighborlist\[j\].get(k);  //nodeid是j的一个邻居节点的编号  
326.                 l = cluster\[nodeid\];                            //l是nodeid所属的簇编号  
327.              
328.                 if(edgeWeightPerCluster\[l\] == 0)           //统计与节点j相连的簇有哪些  
329.                 \{  
330.                         neighboringCluster\[nNeighboringClusters\] = l;  
331.                         nNeighboringClusters++;  
332.                 \}  
333.                  
334.                 edgeWeightPerCluster\[l\] +=weight\[j\]\[nodeid\];  
335.                 //edgeWeightperCluster\[l\]记录的是如果将节点j加入到簇l当中，簇l内部的边权值的增量大小  
336.             \}  
337.              
338.             //节点j之前所属的簇做相应的变更  
339.            clusterWeight\[cluster\[j\]\] -= nodeweight\[j\];  
340.            nNodesPerCluster\[cluster\[j\]\]--;  
341.              
342.             if(nNodesPerCluster\[cluster\[j\]\] == 0)  
343.             \{  
344.                unusedCluster\[nUnusedClusters\] = cluster\[j\];  
345.                nUnusedClusters++;  
346.             \}  
347.    
348.            bestCluster = -1;              //最好的加入的簇下标  
349.            maxQualityFunction = 0;  
350.            for (k = 0; k < nNeighboringClusters; k++)  
351.             \{  
352.                 l = neighboringCluster\[k\];  
353.                qualityFunction = edgeWeightPerCluster\[l\] - nodeweight\[j\] \*clusterWeight\[l\] \* resolution;  
354.                if ((qualityFunction > maxQualityFunction) || ((qualityFunction ==maxQualityFunction) && (l < bestCluster)))  
355.                \{  
356.                    bestCluster = l;  
357.                    maxQualityFunction = qualityFunction;  
358.                \}  
359.                edgeWeightPerCluster\[l\] = 0;  
360.                // =0是为了数组复用，  
361.             \}  
362.             if(maxQualityFunction == 0)   //无论到哪一簇都不会有提升  
363.             \{  
364.                bestCluster = unusedCluster\[nUnusedClusters - 1\];  
365.                nUnusedClusters--;  
366.             \}  
367.    
368.            clusterWeight\[bestCluster\] += nodeweight\[j\];  
369.             nNodesPerCluster\[bestCluster\]++;  //最佳簇的节点数量+1  
370.             if(bestCluster == cluster\[j\])   
371.                nStableNodes++;        //还在原来的簇当中，表示该节点是稳定的，稳定节点的数量+1  
372.            else  
373.             \{  
374.                cluster\[j\] = bestCluster;  
375.                nStableNodes = 1;  
376.                update = true;       //能移动到新的簇当中去，然后需要重新考虑每个节点是否稳定  
377.             \}  
378.    
379.             i= (i < nodecount - 1) ? (i + 1) : 0;  
380.         \}  
381.         while(nStableNodes < nodecount);            //优化步骤是直到所有的点都稳定下来才结束  
382.    
383.        newCluster = new int\[nodecount\];  
384.        clustercount = 0;  
385.         for (i= 0; i < nodecount; i++)  
386.             if(nNodesPerCluster\[i\] > 0)  
387.             \{                                                                 //统计以前的簇编号还有多少能用，然后从0开始重新对它们编号  
388.                newCluster\[i\] = clustercount;  
389.                clustercount++;  
390.             \}  
391.         for (i= 0; i < nodecount; i++)  
392.            cluster\[i\] = newCluster\[cluster\[i\]\];  
393.    
394.        deleteClusteringStats();  
395.    
396.         returnupdate;  
397.     \}  
398.      
399.      
400.      
401.     publicboolean runLouvainAlgorithm(double resolution)  
402.     \{  
403.         returnrunLouvainAlgorithm(resolution, new Random());  
404.     \}  
405.    
406.     publicboolean runLouvainAlgorithm(double resolution, Random random)  
407.     \{  
408.        boolean update, update2;  
409.        NetWork reducedNetwork;  
410.    
411.         if((cluster == null) || (nodecount == 1))  
412.            return false;  
413.    
414.         update= runLocalMovingAlgorithm(resolution, random);  
415.        //update表示是否有节点变动,即是否移动到了新的簇当中去  
416.                  
417.         if(clustercount < nodecount)   //簇的数量小于节点的数量，说明可以进行reduce操作，ruduce不会改变  
418.         \{                                                    //modularity的值  
419.            reducedNetwork = getReducedNetwork();  
420.            reducedNetwork.initSingletonClusters();  
421.    
422.            update2 = reducedNetwork.runLouvainAlgorithm(resolution, random);  
423.            //update2表示在reduce之后的网络中是否有节点移动到新的簇当中去  
424.              
425.             if(update2)  
426.             \{  
427.                update = true;  
428.    
429.                mergeClusters(reducedNetwork.getClusters());  
430.                //有变动的话，至少是簇的顺序变掉了，或者是簇的数量减少了  
431.                  
432.             \}  
433.         \}  
434.    
435.        deleteClusteringStats();  
436.    
437.         returnupdate;  
438.     \}  
439.    
440.      
441.     publicvoid generategml() throws IOException  
442.     \{  
443.            
444.           BufferedWriter writer = newBufferedWriter(new FileWriter("generated.gml"));  
445.            
446.           writer.append("graph\\n");  
447.           writer.append("\[\\n");  
448.           for(int i=0;i<nodecount;i++)  
449.           \{  
450.                  writer.append("  node\\n");  
451.                  writer.append("  \[\\n");  
452.                  writer.append("    id "\+i+"\\n");  
453.                  writer.append("    type "\+cluster\[i\]+"\\n");  
454.                  writer.append("  \]\\n");  
455.           \}  
456.            
457.           for(int i=0;i<nodecount;i++)  
458.                  for(int j=i+1;j<nodecount;j++)  
459.                  \{  
460.                         if(weight\[i\]\[j\] != 0)  
461.                         \{  
462.                                writer.append("  edge\\n");  
463.                            writer.append("  \[\\n");  
464.                            writer.append("    source "\+i+"\\n");  
465.                            writer.append("    target "\+j+"\\n");  
466.                            writer.append("  \]\\n");  
467.                                                           
468.                         \}  
469.                          
470.                          
471.                  \}  
472.            
473.           writer.append("\]\\n");  
474.            
475.            
476.           writer.close();  
477.     \}  
478.      
479.      
480.         
481. \}

Main.java

**\[java\]**  [view plain][]  [copy][view plain]

1.  package communitydetection;  
2.  import java.io.\*;  
3.  import java.util.\*;  
4.     
5.  public class Main \{  
6.                        
7.         staticvoid detect() throws IOException  
8.         \{  
9.                 NetWork network;  
10.                
11.                
12.               Stringfilename = "karate\_club\_network.txt";  
13.                
14.               doublemodularity, resolution, maxModularity;  
15.                
16.               doublebeginTime, endTime;  
17.           
18.               int\[\]cluster;  
19.                
20.               intnRandomStarts = 5;  
21.                
22.               intnIterations = 3;  
23.                
24.               network= new NetWork(filename);  
25.                
26.               resolution= 1.0/network.getTotalEdgeWeight();  
27.                
28.               beginTime= System.currentTimeMillis();  
29.        cluster = null;  
30.         int nClusters= -1;  
31.         inti,j;  
32.        maxModularity = Double.NEGATIVE\_INFINITY;  
33.         Randomrandom = new Random(100);  
34.         for (i= 0; i < nRandomStarts; i++)  
35.         \{  
36.             if( (nRandomStarts > 1))  
37.                System.out.format("Random start: %d%n", i + 1);  
38.    
39.            network.initSingletonClusters();      //网络初始化，每个节点一个簇  
40.    
41.             j= 0;  
42.            boolean update = true;         //update表示网络是否有节点移动  
43.             do  
44.             \{  
45.                if ( (nIterations > 1))  
46.                    System.out.format("Iteration: %d%n", j + 1);  
47.        
48.                update = network.runLouvainAlgorithm(resolution, random);  
49.           
50.                j++;  
51.    
52.                modularity = network.calcQualityFunction(resolution);  
53.    
54.                if ((nIterations > 1))  
55.                    System.out.format("Modularity: %.4f%n", modularity);  
56.             \}  
57.            while ((j < nIterations) && update);  
58.             
59.                  
60.             if(modularity > maxModularity)  
61.             \{  
62.            
63.                cluster = network.getClusters();  
64.                nClusters = network.getNClusters();  
65.                maxModularity = modularity;  
66.             \}  
67.    
68.             if((nRandomStarts > 1))  
69.             \{  
70.                if (nIterations == 1)  
71.                    System.out.format("Modularity: %.4f%n", modularity);  
72.                System.out.println();  
73.             \}  
74.         \}  
75.        endTime = System.currentTimeMillis();  
76.          
77.        network.generategml();  
78.          
79.         if(nRandomStarts == 1)  
80.         \{  
81.             if(nIterations > 1)  
82.                System.out.println();  
83.            System.out.format("Modularity: %.4f%n", maxModularity);  
84.         \}  
85.         else  
86.            System.out.format("Maximum modularity in %d random starts:%.4f%n", nRandomStarts, maxModularity);  
87.        System.out.format("Number of communities: %d%n", nClusters);  
88.        System.out.format("Elapsed time: %f seconds%n", (endTime -beginTime) / 1000.0);  
89.        System.out.println();  
90.         System.out.println("Writingoutput file...");  
91.        System.out.println();  
92.          
93.  //      writeOutputFile("communities.txt", cluster);  
94.                                            
95.        \}  
96.         
97.        //将每一个节点所属的簇的下标写到文件当中去  
98.     privatestatic void writeOutputFile(String fileName, int\[\] cluster) throws IOException  
99.     \{  
100.            
101.        BufferedWriter bufferedWriter;  
102.         int i;  
103.    
104.        bufferedWriter = new BufferedWriter(new FileWriter(fileName));  
105.    
106.         for (i= 0; i < cluster.length; i++)  
107.         \{  
108.            bufferedWriter.write(Integer.toString(cluster\[i\]));  
109.            bufferedWriter.newLine();  
110.         \}  
111.    
112.        bufferedWriter.close();  
113.         
114.            
115.            
116.     \}  
117.          
118.        publicstatic void main(String args\[\]) throws IOException  
119.        \{  
120.                
121.               detect();  
122.                
123.        \}  
124.    
125. \}

算法运行结果

Karate结果

![Center 3][]

分簇结果

![Center 4][]

生成的gml文件

![Center 5][]

导入到Gephi中，按照节点的type分割的结果

![Center 6][]

![Center 7][]

Facebook上4039个数据的结果

![Center 8][]

将生成的gml文件导入到Gephi中，并依据节点的type分割的结果

![Center 9][]

![Center 10][]

[http_arxiv.org_abs_0803.0476]: http://arxiv.org/abs/0803.0476
[http_perso.uclouvain.be_vincent.blondel_research_louvain.html]: http://perso.uclouvain.be/vincent.blondel/research/louvain.html
[https_sites.google.com_site_findcommunities]: https://sites.google.com/site/findcommunities/
[http_wiki.cns.iu.edu_display_CISHELL_Louvain_Community_Detection]: http://wiki.cns.iu.edu/display/CISHELL/Louvain+Community+Detection
[http_www.ludowaltman.nl_slm]: http://www.ludowaltman.nl/slm/
[view plain]: http://blog.csdn.net/u012441543/article/details/38356349#
[Center]: /images/20220602/40d964fedd174e3dac71606bfe6366fd.png
[Center 1]: /images/20220602/ca7069a06cf94222825d31b5d19f137a.png
[Center 2]: /images/20220602/7dcfb96fcb0b481ea8de96f23df9e0c5.png
[Center 3]: /images/20220602/3b718f17944045bd9a92d3af5b5f8130.png
[Center 4]: /images/20220602/7f0af6048a8c488eac91151aa4ef9916.png
[Center 5]: /images/20220602/5da03a2fd8ba4ec28e0de0fb73a3be89.png
[Center 6]: /images/20220602/75e85ad66b8e4b58b037940d6f9d7217.png
[Center 7]: /images/20220602/7288a49e83944f8ba857f74cb1cf6b42.png
[Center 8]: /images/20220602/390fe77f34ab444ab08fd1d34b2bb46f.png
[Center 9]: /images/20220602/41bf6797e68743a88f4b8617975e90af.png
[Center 10]: /images/20220602/8185c3d087a94ae38d02bfe570e2103f.png