Mercurial > repos > petrn > repeatexplorer

comparison louvain/community.h @ 8:3bc73f5dc785 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Uploaded
author petrn
date Fri, 20 Dec 2019 14:17:59 +0000
parents f6ebec6e235e
children
comparison
equal deleted inserted replaced
7:c56807be3b72 8:3bc73f5dc785
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