SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
coreper.cpp
Go to the documentation of this file.
1 // Community detection algorithms
3 namespace TSnap {
4 
5 
6  namespace TSnapDetail {
7 
8  } // namespace TSnapDetail
9 
10 
11 
12  int FastCorePeriphery(PUNGraph& Graph, TIntIntH& out){
13 
14  TIntIntH nodes;
15  double Z=0;
16 
17  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++){ // Calculate and store the degrees of each node.
18  int deg = NI.GetDeg();
19  int id = NI.GetId();
20  Z += deg;
21  nodes.AddDat(id,deg);
22  }
23 
24  Z = Z/2;
25 
26  nodes.SortByDat(false); // Then sort the nodes in descending order of degree, to get a list of nodes {v1, v2, . . . , vn}.
27 
28  double Zbest = 99999900000000000;
29  int kbest = 0;
30 
31  int br=0;
32  for (int k=0; k<nodes.Len(); k++){
33  br++;
34  Z = Z + br - 1 - nodes[k];
35  if (Z < Zbest){ // or <=
36  Zbest = Z;
37  kbest = br;
38  }
39  }
40 
41  int cp = 0;
42  br = 0;
43  for (THashKeyDatI<TInt, TInt> it = nodes.BegI(); !it.IsEnd(); it++) {
44  if (br < kbest)
45  cp = 1;
46  else
47  cp = 0;
48  out.AddDat(it.GetKey(), cp);
49  br++;
50  }
51 
52  return kbest;
53  }
54 
55 
57  TIntH GroupNodes; // buildup cpntainer of group nodes
58  int *NNodes = new int[Graph->GetNodes()]; // container of neighbouring nodes
59  int NNodes_br = 0;
60 
61  TIntIntH nodes;
62  TIntIntH nodesIds;
63  double Z=0;
64 
65  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++){ // Calculate and store the degrees of each node.
66  int deg = NI.GetDeg();
67  int id = NI.GetId();
68  Z += deg;
69  nodes.AddDat(id,deg);
70 
71  }
72 
73  Z = Z/2;
74 
75  nodes.SortByDat(false); // Then sort the nodes in descending order of degree, to get a list of nodes {v1, v2, . . . , vn}.
76 
77  int br1=0;
78  for (THashKeyDatI<TInt,TInt> NI = nodes.BegI(); NI < nodes.EndI(); NI++){
79  nodesIds.AddDat(NI.GetKey(),NI.GetKey());
80  br1++;
81  }
82 
83  double Zbest = 99999900000000000;
84  //int kbest;
85  //int olddeg;
86  int br=0;
87  for (int k=0; k<nodes.Len(); k++){
88  if (k<nodes.Len()-1){
89  if (nodes[k]==nodes[k+1]){ // go into same deg mode
90  int kmin=-2; int knew=-1;
91  while (kmin < 999999 && kmin !=-1 ){
92  int kind=-1;
93  knew=k;
94  kmin=999999;
95  while(nodes[k]==nodes[knew] && knew < nodes.Len()-1){
96  int inter = Intersect(Graph->GetNI(nodesIds[knew]),NNodes,NNodes_br);
97  int deg = nodes[knew];
98  //if (((((nodes.Len()-NNodes_br)*(nodes.Len()-NNodes_br)))-(nodes.Len()-NNodes_br))/2<(((br*br)-br)/2))
99  if ((deg-inter)<kmin && !GroupNodes.IsKey(nodesIds[knew]))
100  {
101  kmin = deg-inter; kind = knew;
102  }
103 
104  knew++;
105  }
106 
107  if (kind!=-1){
108  br++;
109  Z = Z + br - 1 - nodes[kind];
110  if (Z < (Zbest)){ // or <=
111  //if (olddeg>nodes[kind])
112 
113  //olddeg = nodes[kind];
114  Zbest = Z;
115  //kbest = br;
116  int w = nodes[kind];
117  int id = nodesIds[kind];
118  GroupNodes.AddDat(id,w);
119  NNodes[NNodes_br] = id;
120  NNodes_br++;
121  }
122  else{
123 
124  break;
125  }
126  }
127  }
128  k=knew-1;
129  }
130  else{
131  br++;
132  Z = Z + br - 1 - nodes[k];
133  if (Z < (Zbest)){ // or <=
134  //if (olddeg>nodes[k])
135 
136  //olddeg = nodes[k];
137  Zbest = Z;
138  //kbest = br;
139  int w = nodes[k];
140  int id = nodesIds[k];
141  GroupNodes.AddDat(id,w);
142  NNodes[NNodes_br] = id;
143  NNodes_br++;
144  }
145  }
146  }
147 
148  else{
149  br++;
150  Z = Z + br - 1 - nodes[k];
151  if (Z < Zbest){ // or <=
152  //if (olddeg>nodes[k])
153 
154  //olddeg = nodes[k];
155  Zbest = Z;
156  //kbest = br;
157  int w = nodes[k];
158  int id = nodesIds[k];
159  GroupNodes.AddDat(id,w);
160  NNodes[NNodes_br] = id;
161  NNodes_br++;
162  }
163  }
164  }
165 
166  int cp = 0;
167  br = 0;
168  for (THashKeyDatI<TInt, TInt> it = nodes.BegI(); !it.IsEnd(); it++) {
169  if (GroupNodes.IsKey(it.GetKey()))
170  cp = 1;
171  else
172  cp = 0;
173  out.AddDat(it.GetKey(), cp);
174  br++;
175  }
176 
177  /*for (THashKeyDatI<TInt, TInt> it = GroupNodes.BegI(); it < GroupNodes.EndI(); it++) {
178  out.AddDat(it.GetKey(), 1);
179  br++;
180  }*/
181 
182  //return kbest;
183  return GroupNodes.Len();
184  }
185 
186  double BorgattiEverettMeasure(PUNGraph& Graph, TIntIntH& out, double coresize, int type){
187 
188  double sum = 0.0;
189  for (TUNGraph::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++){ // Calculate and store the degrees of each node.
190  int i = EI.GetSrcNId();
191  int j = EI.GetDstNId();
192  if (type == 1) {
193  if (out.GetDat(i) == 1 || out.GetDat(j) == 1)
194  sum += 1;
195  }
196  else {
197  if (out.GetDat(i) == 1 && out.GetDat(j) == 1)
198  sum += 1;
199  }
200  }
201 
202  return sum/(((coresize*coresize)-coresize)/2);
203  }
204 
205  double PearsonCorrelation(PUNGraph& Graph, TIntIntH& out, int coresize){
206  int br_core1=0,br_periphery1=0,br_core_per1=0;
207  for (TUNGraph::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++){ // Calculate and store the degrees of each node.
208  int i = EI.GetSrcNId();
209  int j = EI.GetDstNId();
210 
211  if (out.GetDat(i)==1&&out.GetDat(j)==1 && i!=j)
212  br_core1++;
213  else if (out.GetDat(i)==0&&out.GetDat(j)==0 && i!=j)
214  br_periphery1++;
215  else
216  br_core_per1++;
217  }
218 
219  double core_quality = (double)br_core1/((((double)coresize*(double)coresize)-(double)coresize)/2);
220  int per_size = Graph->GetNodes()-coresize;
221  double periphery_quality = (((((double)per_size*(double)per_size)-(double)per_size)/2) - (double)br_periphery1)/((((double)per_size*(double)per_size)-(double)per_size)/2);
222 
223  return (double)(core_quality+periphery_quality);
224  }
225 
226 }; //namespace TSnap
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:121
Main namespace for all the Snap global entities.
Definition: alg.h:1
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:280
int Intersect(TUNGraph::TNodeI Node, TIntH NNodes)
Intersect.
Definition: centr.cpp:584
TIter BegI() const
Definition: hash.h:213
int FastCorePeripheryGC(PUNGraph &Graph, TIntIntH &out)
Definition: coreper.cpp:56
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
double BorgattiEverettMeasure(PUNGraph &Graph, TIntIntH &out, double coresize, int type)
Definition: coreper.cpp:186
int FastCorePeriphery(PUNGraph &Graph, TIntIntH &out)
Definition: coreper.cpp:12
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TIter EndI() const
Definition: hash.h:218
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:192
bool IsEnd() const
Tests whether the iterator is pointing to the past-end element.
Definition: hash.h:78
double PearsonCorrelation(PUNGraph &Graph, TIntIntH &out, int coresize)
Definition: coreper.cpp:205
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:241
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:278
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:237
int Len() const
Definition: hash.h:228
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
void SortByDat(const bool &Asc=true)
Definition: hash.h:292