|
0
|
1 // File: community.h
|
|
|
2 // -- community detection header file
|
|
|
3 //-----------------------------------------------------------------------------
|
|
|
4 // Community detection
|
|
|
5 // Based on the article "Fast unfolding of community hierarchies in large networks"
|
|
|
6 // Copyright (C) 2008 V. Blondel, J.-L. Guillaume, R. Lambiotte, E. Lefebvre
|
|
|
7 //
|
|
|
8 // This program must not be distributed without agreement of the above mentionned authors.
|
|
|
9 //-----------------------------------------------------------------------------
|
|
|
10 // Author : E. Lefebvre, adapted by J.-L. Guillaume
|
|
|
11 // Email : jean-loup.guillaume@lip6.fr
|
|
|
12 // Location : Paris, France
|
|
|
13 // Time : February 2008
|
|
|
14 //-----------------------------------------------------------------------------
|
|
|
15 // see readme.txt for more details
|
|
|
16
|
|
|
17 #ifndef COMMUNITY_H
|
|
|
18 #define COMMUNITY_H
|
|
|
19
|
|
|
20 #include <stdlib.h>
|
|
|
21 #include <stdio.h>
|
|
|
22 #include <iostream>
|
|
|
23 #include <iomanip>
|
|
|
24 #include <fstream>
|
|
|
25 #include <vector>
|
|
|
26 #include <map>
|
|
|
27
|
|
|
28 #include "graph_binary.h"
|
|
|
29
|
|
|
30 using namespace std;
|
|
|
31
|
|
|
32 class Community {
|
|
|
33 public:
|
|
|
34 vector<double> neigh_weight;
|
|
|
35 vector<unsigned int> neigh_pos;
|
|
|
36 unsigned int neigh_last;
|
|
|
37
|
|
|
38 Graph g; // network to compute communities for
|
|
|
39 int size; // nummber of nodes in the network and size of all vectors
|
|
|
40 vector<int> n2c; // community to which each node belongs
|
|
|
41 vector<double> in,tot; // used to compute the modularity participation of each community
|
|
|
42
|
|
|
43 // number of pass for one level computation
|
|
|
44 // if -1, compute as many pass as needed to increase modularity
|
|
|
45 int nb_pass;
|
|
|
46
|
|
|
47 // a new pass is computed if the last one has generated an increase
|
|
|
48 // greater than min_modularity
|
|
|
49 // if 0. even a minor increase is enough to go for one more pass
|
|
|
50 double min_modularity;
|
|
|
51
|
|
|
52 // constructors:
|
|
|
53 // reads graph from file using graph constructor
|
|
|
54 // type defined the weighted/unweighted status of the graph file
|
|
|
55 Community (char *filename, char *filename_w, int type, int nb_pass, double min_modularity);
|
|
|
56 // copy graph
|
|
|
57 Community (Graph g, int nb_pass, double min_modularity);
|
|
|
58
|
|
|
59 // initiliazes the partition with something else than all nodes alone
|
|
|
60 void init_partition(char *filename_part);
|
|
|
61
|
|
|
62 // display the community of each node
|
|
|
63 void display();
|
|
|
64
|
|
|
65 // remove the node from its current community with which it has dnodecomm links
|
|
|
66 inline void remove(int node, int comm, double dnodecomm);
|
|
|
67
|
|
|
68 // insert the node in comm with which it shares dnodecomm links
|
|
|
69 inline void insert(int node, int comm, double dnodecomm);
|
|
|
70
|
|
|
71 // compute the gain of modularity if node where inserted in comm
|
|
|
72 // given that node has dnodecomm links to comm. The formula is:
|
|
|
73 // [(In(comm)+2d(node,comm))/2m - ((tot(comm)+deg(node))/2m)^2]-
|
|
|
74 // [In(comm)/2m - (tot(comm)/2m)^2 - (deg(node)/2m)^2]
|
|
|
75 // where In(comm) = number of half-links strictly inside comm
|
|
|
76 // Tot(comm) = number of half-links inside or outside comm (sum(degrees))
|
|
|
77 // d(node,com) = number of links from node to comm
|
|
|
78 // deg(node) = node degree
|
|
|
79 // m = number of links
|
|
|
80 inline double modularity_gain(int node, int comm, double dnodecomm, double w_degree);
|
|
|
81
|
|
|
82 // compute the set of neighboring communities of node
|
|
|
83 // for each community, gives the number of links from node to comm
|
|
|
84 void neigh_comm(unsigned int node);
|
|
|
85
|
|
|
86 // compute the modularity of the current partition
|
|
|
87 double modularity();
|
|
|
88
|
|
|
89 // displays the graph of communities as computed by one_level
|
|
|
90 void partition2graph();
|
|
|
91 // displays the current partition (with communities renumbered from 0 to k-1)
|
|
|
92 void display_partition();
|
|
|
93
|
|
|
94 // generates the binary graph of communities as computed by one_level
|
|
|
95 Graph partition2graph_binary();
|
|
|
96
|
|
|
97 // compute communities of the graph for one level
|
|
|
98 // return true if some nodes have been moved
|
|
|
99 bool one_level();
|
|
|
100 };
|
|
|
101
|
|
|
102 inline void
|
|
|
103 Community::remove(int node, int comm, double dnodecomm) {
|
|
|
104 assert(node>=0 && node<size);
|
|
|
105
|
|
|
106 tot[comm] -= g.weighted_degree(node);
|
|
|
107 in[comm] -= 2*dnodecomm + g.nb_selfloops(node);
|
|
|
108 n2c[node] = -1;
|
|
|
109 }
|
|
|
110
|
|
|
111 inline void
|
|
|
112 Community::insert(int node, int comm, double dnodecomm) {
|
|
|
113 assert(node>=0 && node<size);
|
|
|
114
|
|
|
115 tot[comm] += g.weighted_degree(node);
|
|
|
116 in[comm] += 2*dnodecomm + g.nb_selfloops(node);
|
|
|
117 n2c[node]=comm;
|
|
|
118 }
|
|
|
119
|
|
|
120 inline double
|
|
|
121 Community::modularity_gain(int node, int comm, double dnodecomm, double w_degree) {
|
|
|
122 assert(node>=0 && node<size);
|
|
|
123
|
|
|
124 double totc = (double)tot[comm];
|
|
|
125 double degc = (double)w_degree;
|
|
|
126 double m2 = (double)g.total_weight;
|
|
|
127 double dnc = (double)dnodecomm;
|
|
|
128
|
|
|
129 return (dnc - totc*degc/m2);
|
|
|
130 }
|
|
|
131
|
|
|
132
|
|
|
133 #endif // COMMUNITY_H
|
