SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
centr.cpp
Go to the documentation of this file.
1 namespace TSnap {
2 
4 // Node centrality measures
5 double GetDegreeCentr(const PUNGraph& Graph, const int& NId) {
6  if (Graph->GetNodes() > 1) {
7  return double(Graph->GetNI(NId).GetDeg())/double(Graph->GetNodes()-1); }
8  else { return 0.0; }
9 }
10 
11 void GetEigenVectorCentr(const PUNGraph& Graph, TIntFltH& NIdEigenH, const double& Eps, const int& MaxIter) {
12  const int NNodes = Graph->GetNodes();
13  NIdEigenH.Gen(NNodes);
14  // initialize vector values
15  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
16  NIdEigenH.AddDat(NI.GetId(), 1.0/NNodes);
17  IAssert(NI.GetId() == NIdEigenH.GetKey(NIdEigenH.Len()-1));
18  }
19  TFltV TmpV(NNodes);
20  for (int iter = 0; iter < MaxIter; iter++) {
21  int j = 0;
22  // add neighbor values
23  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++, j++) {
24  TmpV[j] = 0;
25  for (int e = 0; e < NI.GetOutDeg(); e++) {
26  TmpV[j] += NIdEigenH.GetDat(NI.GetOutNId(e)); }
27  }
28 
29  // normalize
30  double sum = 0;
31  for (int i = 0; i < TmpV.Len(); i++) {
32  sum += (TmpV[i]*TmpV[i]);
33  }
34  sum = sqrt(sum);
35  for (int i = 0; i < TmpV.Len(); i++) {
36  TmpV[i] /= sum;
37  }
38 
39  // compute difference
40  double diff = 0.0;
41  j = 0;
42  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++, j++) {
43  diff += fabs(NIdEigenH.GetDat(NI.GetId())-TmpV[j]);
44  }
45 
46  // set new values
47  j = 0;
48  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++, j++) {
49  NIdEigenH.AddDat(NI.GetId(), TmpV[j]);
50  }
51 
52  if (diff < Eps) {
53  break;
54  }
55  }
56 }
57 
58 // Group centrality measures
59 double GetGroupDegreeCentr(const PUNGraph& Graph, const PUNGraph& Group) {
60  int deg;
61  TIntH NN;
62  for (TUNGraph::TNodeI NI = Group->BegNI(); NI < Group->EndNI(); NI++) {
63  deg = Graph->GetNI(NI.GetId()).GetDeg();
64  for (int i=0; i<deg; i++) {
65  if (Group->IsNode(Graph->GetNI(NI.GetId()).GetNbrNId(i))==0)
66  NN.AddDat(Graph->GetNI(NI.GetId()).GetNbrNId(i),NI.GetId());
67  }
68  }
69  return (double)NN.Len();
70 }
71 
72 double GetGroupDegreeCentr0(const PUNGraph& Graph, const TIntH& GroupNodes) {
73  int deg;
74  TIntH NN;
75  for (int i = 0; i<GroupNodes.Len(); i++) {
76  deg = Graph->GetNI(GroupNodes.GetDat(i)).GetDeg();
77  for (int j = 0; j < deg; j++) {
78  if (GroupNodes.IsKey(Graph->GetNI(GroupNodes.GetDat(i)).GetNbrNId(j))==0)
79  NN.AddDat(Graph->GetNI(GroupNodes.GetDat(i)).GetNbrNId(j),GroupNodes.GetDat(i));
80  }
81  }
82  return (double)NN.Len();
83 }
84 
85 double GetGroupDegreeCentr(const PUNGraph& Graph, const TIntH& GroupNodes) {
86  int deg;
87  TIntH NN;
88  TIntH GroupNodes1;
89 
90  for (THashKeyDatI<TInt,TInt> NI = GroupNodes.BegI(); NI < GroupNodes.EndI(); NI++)
91  GroupNodes1.AddDat(NI.GetDat(),NI.GetDat());
92 
93  for (THashKeyDatI<TInt,TInt> NI = GroupNodes1.BegI(); NI < GroupNodes1.EndI(); NI++){
94  TUNGraph::TNodeI node = Graph->GetNI(NI.GetKey());
95  deg = node.GetDeg();
96  for (int j = 0; j < deg; j++){
97  if (GroupNodes1.IsKey(node.GetNbrNId(j))==0 && NN.IsKey(node.GetNbrNId(j))==0)
98  NN.AddDat(node.GetNbrNId(j),NI.GetKey());
99  }
100  }
101 
102  return (double)NN.Len();
103 }
104 
105 double GetGroupFarnessCentr(const PUNGraph& Graph, const TIntH& GroupNodes) {
106  TIntH* NDistH = new TIntH[GroupNodes.Len()];
107 
108  for (int i=0; i<GroupNodes.Len(); i++){
109  NDistH[i](Graph->GetNodes());
110  TSnap::GetShortPath<PUNGraph>(Graph, GroupNodes.GetDat(i), NDistH[i], true, TInt::Mx);
111  }
112 
113  int min, dist, sum=0, len=0;
114  for (PUNGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++){
115  if(NDistH[0].IsKey(NI.GetId()))
116  min = NDistH[0].GetDat(NI.GetId());
117  else
118  min = -1;
119  for (int j=1; j<GroupNodes.Len(); j++){
120  if (NDistH[j].IsKey(NI.GetId()))
121  dist = NDistH[j].GetDat(NI.GetId());
122  else
123  dist = -1;
124  if ((dist < min && dist != -1) || (dist > min && min == -1))
125  min = dist;
126  }
127  if (min>0){
128  sum += min;
129  len++;
130  }
131 
132  }
133 
134  if (len > 0) { return sum/double(len); }
135  else { return 0.0; }
136 }
137 
139  PUNGraph* g = new PUNGraph[(((n*n)-n)/2)+1];
140  PUNGraph g0;
141  for(int i=0; i<n; i++)
142  g0->AddNode(i);
143 
144  g[0] = g0;
145  int br=1;
146 
147  for(int i=0; i<n; i++)
148  for(int j=i; j<n; j++){
149  g0->AddEdge(i,j);
150  g[br] = g0;
151  br++;
152  }
153 
154  return g;
155 }
156 
157 TIntH *AllCombinationsMN(int m, int n){
158  float N = 1;
159  for(int i=n; i>0; i--){
160  N *= (float)m/(float)n;
161  m--;
162  n--;
163  }
164 
165  TIntH* C = new TIntH[(int)N];
166  return C;
167 }
168 
169 double GetGroupClosenessCentr(const PUNGraph& Graph, const TIntH& GroupNodes) {
170  const double Farness = GetGroupFarnessCentr(Graph, GroupNodes);
171  if (Farness != 0.0) { return 1.0/Farness; }
172  else { return 0.0; }
173 }
174 
175 TIntH MaxCPGreedyBetter(const PUNGraph& Graph, const int k) {
176  TIntH GroupNodes; // buildup cpntainer of group nodes
177  TIntH NNodes; // container of neighbouring nodes
178  TIntH Nodes; // nodes sorted by vd
179  double gc = 0, gc0 = 0;
180  int addId = 0, addIdPrev = 0;
181 
182  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
183  Nodes.AddDat(NI.GetId(),NI.GetDeg());
184  }
185 
186  Nodes.SortByDat(false);
187 
188  int br = 0;
189  while (br < k) {
190  for (THashKeyDatI<TInt,TInt> NI = Nodes.BegI(); NI < Nodes.EndI(); NI++) {
191  if ((NI.GetDat() <= (int)gc0))
192  break;
193  gc = NI.GetDat()-Intersect(Graph->GetNI(NI.GetKey()),NNodes);
194  if (gc>gc0) {
195  gc0 = gc;
196  addId = NI.GetKey();
197  }
198  }
199 
200  if (addId != addIdPrev){
201 
202  GroupNodes.AddDat(br,addId);
203  br++;
204  gc0=0;
205 
206  NNodes.AddDat(addId,0);
207  for (int i=0; i<Graph->GetNI(addId).GetDeg(); i++) {
208  NNodes.AddDat(Graph->GetNI(addId).GetNbrNId(i),0);
209  }
210  addIdPrev = addId;
211  Nodes.DelKey(addId);
212  } else {
213  br = k;
214  }
215  printf("%i,",br);
216  }
217 
218  // gcFinal = GetGroupDegreeCentr(Graph, GroupNodes);
219  return GroupNodes;
220 }
221 
222 // this is the variation of the first version that doesent stop after finding the optimal K
223 TIntH MaxCPGreedyBetter1(const PUNGraph& Graph, const int k) {
224  TIntH GroupNodes;
225  TIntH NNodes;
226  TIntH Nodes;
227  double gc = 0, gc0 = 0;
228  int addId = 0, addIdPrev = 0;
229 
230  // put nodes in the container and sort them by vertex degree
231  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++){
232  Nodes.AddDat(NI.GetId(),NI.GetDeg());
233  }
234  Nodes.SortByDat(false);
235 
236  int br = 0;
237  while (br < k) {
238  for (THashKeyDatI<TInt,TInt> NI = Nodes.BegI(); NI < Nodes.EndI(); NI++){
239  if((NI.GetDat() < (int)gc0))
240  break;
241  gc = NI.GetDat()-Intersect(Graph->GetNI(NI.GetKey()),NNodes);
242  if (gc>gc0) {
243  gc0 = gc;
244  addId = NI.GetKey();
245  }
246  }
247 
248  if (addId != addIdPrev){
249 
250  GroupNodes.AddDat(br,addId);
251  br++;
252  gc0=-10000000;
253 
254  NNodes.AddDat(addId,0);
255  for (int i=0; i<Graph->GetNI(addId).GetDeg(); i++) {
256  NNodes.AddDat(Graph->GetNI(addId).GetNbrNId(i),0);
257  }
258  addIdPrev = addId;
259  Nodes.DelKey(addId);
260  }
261  }
262 
263  // gcFinal = GetGroupDegreeCentr(Graph, GroupNodes);
264  return GroupNodes;
265 }
266 
267 // version with string type of container of group nodes - Fail (it is slower)
268 TIntH MaxCPGreedyBetter2(const PUNGraph& Graph, const int k) {
269  TIntH GroupNodes; // buildup cpntainer of group nodes
270  TStr NNodes; // container of neighbouring nodes
271  TIntH Nodes; // nodes sorted by vd
272  double gc = 0, gc0 = 0;
273  int addId = 0, addIdPrev=0;
274 
275  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++){
276  Nodes.AddDat(NI.GetId(),NI.GetDeg());
277  }
278 
279  Nodes.SortByDat(false);
280 
281  int br=0;
282  while (br < k) {
283  for (THashKeyDatI<TInt,TInt> NI = Nodes.BegI(); NI < Nodes.EndI(); NI++){
284  if((NI.GetDat() <= (int)gc0))
285  break;
286  gc = NI.GetDat()-Intersect(Graph->GetNI(NI.GetKey()),NNodes);
287  if (gc>gc0) {
288  gc0 = gc;
289  addId = NI.GetKey();
290  }
291  }
292 
293  if (addId != addIdPrev) {
294 
295  GroupNodes.AddDat(br,addId);
296  br++;
297  gc0=0;
298 
299  TInt digi = addId;
300  TStr buf = digi.GetStr();
301 
302  NNodes += " "+buf;
303 
304  for (int i=0; i<Graph->GetNI(addId).GetDeg(); i++) {
305  TInt digi = Graph->GetNI(addId).GetNbrNId(i);
306  TStr buf = digi.GetStr();
307  NNodes += " "+buf;
308  }
309  addIdPrev = addId;
310  Nodes.DelKey(addId);
311  } else {
312  br = k;
313  }
314  printf("%i,",br);
315  }
316 
317  // gcFinal = GetGroupDegreeCentr(Graph, GroupNodes);
318  return GroupNodes;
319 }
320 
321 // version with int array - the fastest
322 TIntH MaxCPGreedyBetter3(const PUNGraph& Graph, const int k) {
323  TIntH GroupNodes; // buildup cpntainer of group nodes
324  const int n = Graph->GetNodes();
325  int *NNodes = new int[n]; // container of neighbouring nodes
326  int NNodes_br = 0;
327  TIntH Nodes; // nodes sorted by vd
328  double gc = 0, gc0 = 0;
329  int addId = 0, addIdPrev = 0;
330 
331  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++){
332  Nodes.AddDat(NI.GetId(),NI.GetDeg());
333  }
334 
335  Nodes.SortByDat(false);
336 
337  int br = 0;
338  while (br < k) {
339  for (THashKeyDatI<TInt,TInt> NI = Nodes.BegI(); NI < Nodes.EndI(); NI++){
340  if((NI.GetDat() <= (int)gc0))
341  break;
342  gc = NI.GetDat()-Intersect(Graph->GetNI(NI.GetKey()),NNodes,NNodes_br);
343  if (gc>gc0){
344  gc0 = gc;
345  addId = NI.GetKey();
346  }
347  }
348 
349  if (addId != addIdPrev) {
350 
351  GroupNodes.AddDat(br,addId);
352  br++;
353  gc0=0;
354 
355  int nn = addId;
356  bool nnnew = true;
357  for (int j=0; j<NNodes_br; j++)
358  if (NNodes[j] == nn){
359  nnnew = false;
360  j = NNodes_br;
361  }
362 
363  if (nnnew){
364  NNodes[NNodes_br] = nn;
365  NNodes_br++;
366  }
367 
368  for (int i=0; i<Graph->GetNI(addId).GetDeg(); i++) {
369  int nn = Graph->GetNI(addId).GetNbrNId(i);
370  bool nnnew = true;
371  for (int j=0; j<NNodes_br; j++) {
372  if (NNodes[j] == nn){
373  nnnew = false;
374  j = NNodes_br;
375  }
376  }
377  if (nnnew){
378  NNodes[NNodes_br] = nn;
379  NNodes_br++;
380  }
381  }
382  addIdPrev = addId;
383  Nodes.DelKey(addId);
384  } else {
385  br = k;
386  }
387  printf("%i,",br);
388  }
389 
390  delete NNodes;
391  // gcFinal = GetGroupDegreeCentr(Graph, GroupNodes);
392  return GroupNodes;
393 }
394 
395 //Weighted PageRank
396 int GetWeightedPageRank(const PNEANet Graph, TIntFltH& PRankH, const TStr& Attr, const double& C, const double& Eps, const int& MaxIter) {
397  if (!Graph->IsFltAttrE(Attr)) return -1;
398 
399  TFltV Weights = Graph->GetFltAttrVecE(Attr);
400 
401  int mxid = Graph->GetMxNId();
402  TFltV OutWeights(mxid);
403  Graph->GetWeightOutEdgesV(OutWeights, Weights);
404 
405  const int NNodes = Graph->GetNodes();
406  //const double OneOver = 1.0/double(NNodes);
407  PRankH.Gen(NNodes);
408  for (TNEANet::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
409  PRankH.AddDat(NI.GetId(), 1.0/NNodes);
410  //IAssert(NI.GetId() == PRankH.GetKey(PRankH.Len()-1));
411  }
412  TFltV TmpV(NNodes);
413  for (int iter = 0; iter < MaxIter; iter++) {
414  int j = 0;
415  for (TNEANet::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++, j++) {
416  TmpV[j] = 0;
417  for (int e = 0; e < NI.GetInDeg(); e++) {
418  const int InNId = NI.GetInNId(e);
419  const TFlt OutWeight = OutWeights[InNId];
420  int EId = Graph->GetEId(InNId, NI.GetId());
421  const TFlt Weight = Weights[Graph->GetFltKeyIdE(EId)];
422  if (OutWeight > 0) {
423  TmpV[j] += PRankH.GetDat(InNId) * Weight / OutWeight; }
424  }
425  TmpV[j] = C*TmpV[j]; // Berkhin (the correct way of doing it)
426  //TmpV[j] = C*TmpV[j] + (1.0-C)*OneOver; // iGraph
427  }
428  double diff=0, sum=0, NewVal;
429  for (int i = 0; i < TmpV.Len(); i++) { sum += TmpV[i]; }
430  const double Leaked = (1.0-sum) / double(NNodes);
431  for (int i = 0; i < PRankH.Len(); i++) { // re-instert leaked PageRank
432  NewVal = TmpV[i] + Leaked; // Berkhin
433  //NewVal = TmpV[i] / sum; // iGraph
434  diff += fabs(NewVal-PRankH[i]);
435  PRankH[i] = NewVal;
436  }
437  if (diff < Eps) { break; }
438  }
439  return 0;
440 }
441 
442 #ifdef USE_OPENMP
443 int GetWeightedPageRankMP(const PNEANet Graph, TIntFltH& PRankH, const TStr& Attr, const double& C, const double& Eps, const int& MaxIter) {
444  if (!Graph->IsFltAttrE(Attr)) return -1;
445  const int NNodes = Graph->GetNodes();
447 
448  //const double OneOver = 1.0/double(NNodes);
449  PRankH.Gen(NNodes);
450  int MxId = 0;
451 
452  for (TNEANet::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
453  NV.Add(NI);
454  PRankH.AddDat(NI.GetId(), 1.0/NNodes);
455  int Id = NI.GetId();
456  if (Id > MxId) {
457  MxId = Id;
458  }
459  }
460 
461  TFltV PRankV(MxId+1);
462  TFltV OutWeights(MxId+1);
463 
464  TFltV Weights = Graph->GetFltAttrVecE(Attr);
465 
466  #pragma omp parallel for schedule(dynamic,10000)
467  for (int j = 0; j < NNodes; j++) {
468  TNEANet::TNodeI NI = NV[j];
469  int Id = NI.GetId();
470  OutWeights[Id] = Graph->GetWeightOutEdges(NI, Attr);
471  PRankV[Id] = 1/NNodes;
472  }
473 
474  TFltV TmpV(NNodes);
475  for (int iter = 0; iter < MaxIter; iter++) {
476 
477  #pragma omp parallel for schedule(dynamic,10000)
478  for (int j = 0; j < NNodes; j++) {
479  TNEANet::TNodeI NI = NV[j];
480  TFlt Tmp = 0;
481  for (int e = 0; e < NI.GetInDeg(); e++) {
482  const int InNId = NI.GetInNId(e);
483 
484  const TFlt OutWeight = OutWeights[InNId];
485 
486  int EId = Graph->GetEId(InNId, NI.GetId());
487  const TFlt Weight = Weights[Graph->GetFltKeyIdE(EId)];
488 
489  if (OutWeight > 0) {
490  Tmp += PRankH.GetDat(InNId) * Weight / OutWeight;
491  }
492  }
493  TmpV[j] = C*Tmp; // Berkhin (the correct way of doing it)
494  //TmpV[j] = C*TmpV[j] + (1.0-C)*OneOver; // iGraph
495  }
496 
497  double sum = 0;
498  #pragma omp parallel for reduction(+:sum) schedule(dynamic,10000)
499  for (int i = 0; i < TmpV.Len(); i++) { sum += TmpV[i]; }
500  const double Leaked = (1.0-sum) / double(NNodes);
501 
502  double diff = 0;
503  #pragma omp parallel for reduction(+:diff) schedule(dynamic,10000)
504  for (int i = 0; i < NNodes; i++) {
505  TNEANet::TNodeI NI = NV[i];
506  double NewVal = TmpV[i] + Leaked; // Berkhin
507  //NewVal = TmpV[i] / sum; // iGraph
508  int Id = NI.GetId();
509  diff += fabs(NewVal-PRankV[Id]);
510  PRankV[Id] = NewVal;
511  }
512  if (diff < Eps) { break; }
513  }
514 
515  #pragma omp parallel for schedule(dynamic,10000)
516  for (int i = 0; i < NNodes; i++) {
517  TNEANet::TNodeI NI = NV[i];
518  PRankH[i] = PRankV[NI.GetId()];
519  }
520 
521  return 0;
522 }
523 
524 #endif // USE_OPENMP
525 
526 //Event importance
527 TIntFltH EventImportance(const PNGraph& Graph, const int k) {
528  TIntFltH NodeList; // values for nodese
529 
530  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++){
531  NodeList.AddDat(NI.GetId(),NI.GetOutDeg());
532  }
533 
534 
535  for (THashKeyDatI<TInt,TFlt> NI = NodeList.BegI(); NI < NodeList.EndI(); NI++){
536  int outdeg = Graph->GetNI(NI.GetKey()).GetOutDeg();
537  int indeg = Graph->GetNI(NI.GetKey()).GetInDeg();
538 
539  if (outdeg>1 && indeg>0){
540  double val = (1-(1/(double)outdeg))/(double)indeg;
541  for(int i=0; i<(outdeg+indeg);i++){
542  int NId = Graph->GetNI(NI.GetKey()).GetNbrNId(i);
543  if (Graph->GetNI(NI.GetKey()).IsInNId(NId) == true){
544  NodeList.AddDat(NId,NodeList.GetDat(NId)+val);
545  }
546 
547  }
548  }
549 
550  }
551 
552  return NodeList;
553 }
554 
555 //Event importance 1
556 TIntFltH EventImportance1 (const PNGraph& Graph, const int k) {
557  TIntFltH NodeList; // values for nodese
558 
559  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++){
560  NodeList.AddDat(NI.GetId(),NI.GetOutDeg());
561  }
562 
563 
564  for (THashKeyDatI<TInt,TFlt> NI = NodeList.BegI(); NI < NodeList.EndI(); NI++){
565  int outdeg = Graph->GetNI(NI.GetKey()).GetOutDeg();
566  int indeg = Graph->GetNI(NI.GetKey()).GetInDeg();
567 
568  if (outdeg>1 && indeg>0){
569  double val = (1-(1/(double)outdeg))/(double)indeg;
570  for(int i=0; i<(outdeg+indeg);i++){
571  int NId = Graph->GetNI(NI.GetKey()).GetNbrNId(i);
572  if (Graph->GetNI(NI.GetKey()).IsInNId(NId) == true){
573  NodeList.AddDat(NId,NodeList.GetDat(NId)+val);
574  }
575 
576  }
577  }
578 
579  }
580 
581  return NodeList;
582 }
583 
584 int Intersect(TUNGraph::TNodeI Node, TIntH NNodes){
585  int br=0;
586  for (int i=0; i<Node.GetDeg(); i++)
587  {
588  if (NNodes.IsKey(Node.GetNbrNId(i)))
589  br++;
590  }
591  if (NNodes.IsKey(Node.GetId()))
592  br++;
593 
594  return br;
595 }
596 
597 int Intersect(TUNGraph::TNodeI Node, TStr NNodes){
598  int br=0;
599 
600  TInt digi = -1;
601  TStr buf = "";
602 
603  for (int i=0; i<Node.GetDeg(); i++)
604  {
605  digi = Node.GetNbrNId(i);
606  TStr buf = digi.GetStr();
607 
608  if (NNodes.IsStrIn(buf.CStr()))
609  br++;
610  }
611 
612  digi = Node.GetId();
613  buf = digi.GetStr();
614 
615  if (NNodes.IsStrIn(buf.CStr()))
616  br++;
617 
618  return br;
619 }
620 
621 int Intersect(TUNGraph::TNodeI Node, int *NNodes, int NNodes_br){
622  int br = 0;
623  int neig;
624  for (int i=0; i<Node.GetDeg(); i++)
625  {
626  neig = Node.GetNbrNId(i);
627  for (int j=0; j<NNodes_br; j++)
628  {
629  if (neig == NNodes[j])
630  {
631  br++;
632  j = NNodes_br;
633  }
634  }
635  }
636 
637  neig = Node.GetId();
638  for (int j=0; j<NNodes_br; j++)
639  {
640  if (neig == NNodes[j])
641  {
642  br++;
643  j = NNodes_br;
644  }
645  }
646 
647  return br;
648 }
649 
650 int Intersect1(TUNGraph::TNodeI Node, TStr NNodes){
651  int br=0;
652  for (int i=0; i<Node.GetDeg(); i++)
653  {
654  TInt digi = Node.GetNbrNId(i);
655  TStr buf = "";
656  buf = digi.GetStr();
657 
658  if (NNodes.SearchStr(buf.CStr())!=-1)
659  br++;
660  }
661 
662  TInt digi = Node.GetId();
663  TStr buf = digi.GetStr();
664 
665  if (NNodes.SearchStr(buf.CStr())!=-1)
666  br++;
667 
668  return br;
669 }
670 
671 TIntH LoadNodeList(TStr InFNmNodes){
672  TSsParser Ss(InFNmNodes, ssfWhiteSep, true, true, true);
673  TIntIntH Nodes;
674  int br = 0, NId;
675  while (Ss.Next()) {
676  if (Ss.GetInt(0, NId)) {
677  Nodes.AddDat(br,NId);
678  br++;
679  }
680  }
681  return Nodes;
682 }
683 
684 
685 int findMinimum(TIntV& Frontier, TIntFltH& NIdDistH) {
686  TFlt minimum = TInt::Mx;
687  int min_index = 0;
688  for (int i = 0; i < Frontier.Len(); i++) {
689  int NId = Frontier.GetVal(i);
690  if (NIdDistH.GetDat(NId) < minimum) {
691  minimum = NIdDistH.GetDat(NId);
692  min_index = i;
693  }
694  }
695  const int NId = Frontier.GetVal(min_index);
696  Frontier.Del(min_index);
697  return NId;
698 }
699 
701 const PNEANet Graph, const int& SrcNId, TIntFltH& NIdDistH, const TFltV& Attr) {
702  TIntV frontier;
703 
704  NIdDistH.Clr(false); NIdDistH.AddDat(SrcNId, 0);
705  frontier.Add(SrcNId);
706  while (! frontier.Empty()) {
707  const int NId = findMinimum(frontier, NIdDistH);
708  const PNEANet::TObj::TNodeI NodeI = Graph->GetNI(NId);
709  for (int v = 0; v < NodeI.GetOutDeg(); v++) {
710  int DstNId = NodeI.GetOutNId(v);
711  int EId = NodeI.GetOutEId(v);
712 
713  if (! NIdDistH.IsKey(DstNId)) {
714  NIdDistH.AddDat(DstNId, NIdDistH.GetDat(NId) + Attr[EId]);
715  frontier.Add(DstNId);
716  } else {
717  if (NIdDistH.GetDat(DstNId) > NIdDistH.GetDat(NId) + Attr[EId]) {
718  NIdDistH.GetDat(DstNId) = NIdDistH.GetDat(NId) + Attr[EId];
719  }
720  }
721  }
722  }
723  return 0;
724 }
725 
726 double GetWeightedFarnessCentr(const PNEANet Graph, const int& NId, const TFltV& Attr, const bool& Normalized, const bool& IsDir) {
727  TIntFltH NDistH(Graph->GetNodes());
728 
729  GetWeightedShortestPath(Graph, NId, NDistH, Attr);
730 
731  double sum = 0;
732  for (TIntFltH::TIter I = NDistH.BegI(); I < NDistH.EndI(); I++) {
733  sum += I->Dat();
734  }
735  if (NDistH.Len() > 1) {
736  double centr = sum/double(NDistH.Len()-1);
737  if (Normalized) {
738  centr *= (Graph->GetNodes() - 1)/double(NDistH.Len()-1);
739  }
740  return centr;
741  }
742  else { return 0.0; }
743 }
744 
745 double GetWeightedClosenessCentr(const PNEANet Graph, const int& NId, const TFltV& Attr, const bool& Normalized, const bool& IsDir) {
746  const double Farness = GetWeightedFarnessCentr(Graph, NId, Attr, Normalized, IsDir);
747  if (Farness != 0.0) { return 1.0/Farness; }
748  else { return 0.0; }
749  return 0.0;
750 }
751 
752 void GetWeightedBetweennessCentr(const PNEANet Graph, const TIntV& BtwNIdV, TIntFltH& NodeBtwH, const bool& DoNodeCent, TIntPrFltH& EdgeBtwH, const bool& DoEdgeCent, const TFltV& Attr, const bool& IsDir) {
753  if (DoNodeCent) { NodeBtwH.Clr(); }
754  if (DoEdgeCent) { EdgeBtwH.Clr(); }
755  const int nodes = Graph->GetNodes();
756  TIntS S(nodes);
757  TIntQ Q(nodes);
758  TIntIntVH P(nodes); // one vector for every node
759  TIntFltH delta(nodes);
760  TIntFltH sigma(nodes), d(nodes);
761  // init
762  for (PNEANet::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
763  if (DoNodeCent) {
764  NodeBtwH.AddDat(NI.GetId(), 0); }
765  if (DoEdgeCent) {
766  for (int e = 0; e < NI.GetOutDeg(); e++) {
767  if (Graph->HasFlag(gfDirected) && IsDir) {
768  // add all outgoing edges for directed graphs
769  EdgeBtwH.AddDat(TIntPr(NI.GetId(), NI.GetOutNId(e)), 0);
770  } else {
771  // add each edge only once in undirected graphs
772  if (NI.GetId() < NI.GetOutNId(e)) {
773  EdgeBtwH.AddDat(TIntPr(NI.GetId(), NI.GetOutNId(e)), 0);
774  }
775  }
776  }
777  // add incoming edges in directed graphs that were not added yet
778  if (Graph->HasFlag(gfDirected) && !IsDir) {
779  for (int e = 0; e < NI.GetInDeg(); e++) {
780  if (NI.GetId() < NI.GetInNId(e) &&
781  !Graph->IsEdge(NI.GetId(), NI.GetInNId(e))) {
782  EdgeBtwH.AddDat(TIntPr(NI.GetId(), NI.GetInNId(e)), 0);
783  }
784  }
785  }
786  }
787  sigma.AddDat(NI.GetId(), 0);
788  d.AddDat(NI.GetId(), -1);
789  P.AddDat(NI.GetId(), TIntV());
790  delta.AddDat(NI.GetId(), 0);
791  }
792  // calc betweeness
793  for (int k=0; k < BtwNIdV.Len(); k++) {
794  const PNEANet::TObj::TNodeI NI = Graph->GetNI(BtwNIdV[k]);
795  // reset
796  for (int i = 0; i < sigma.Len(); i++) {
797  sigma[i]=0; d[i]=-1; delta[i]=0; P[i].Clr(false);
798  }
799  S.Clr(false);
800  Q.Clr(false);
801  sigma.AddDat(NI.GetId(), 1);
802  d.AddDat(NI.GetId(), 0);
803  Q.Push(NI.GetId());
804  while (! Q.Empty()) {
805  const int v = Q.Top(); Q.Pop();
806  const PNEANet::TObj::TNodeI NI2 = Graph->GetNI(v);
807  S.Push(v);
808  const double VDat = d.GetDat(v);
809  // iterate over all outgoing edges
810  for (int e = 0; e < NI2.GetOutDeg(); e++) {
811  const int w = NI2.GetOutNId(e);
812  const int eid = NI2.GetOutEId(e);
813 
814  if (d.GetDat(w) < 0) { // find w for the first time
815  Q.Push(w);
816  d.AddDat(w, VDat+Attr[eid]);
817  }
818  //shortest path to w via v ?
819  if (d.GetDat(w) == VDat+Attr[eid]) {
820  sigma.AddDat(w) += sigma.GetDat(v);
821  P.GetDat(w).Add(v);
822  }
823  }
824  // if ignoring direction in directed networks, iterate over incoming edges
825  if (Graph->HasFlag(gfDirected) && !IsDir) {
826  for (int e = 0; e < NI2.GetInDeg(); e++) {
827  const int w = NI2.GetInNId(e);
828  // skip neighbors that are also outgoing
829  if (Graph->IsEdge(NI2.GetId(), w)) {
830  continue;
831  }
832  const int eid = NI2.GetInEId(e);
833 
834  if (d.GetDat(w) < 0) { // find w for the first time
835  Q.Push(w);
836  d.AddDat(w, VDat+Attr[eid]);
837  }
838  //shortest path to w via v ?
839  if (d.GetDat(w) == VDat+Attr[eid]) {
840  sigma.AddDat(w) += sigma.GetDat(v);
841  P.GetDat(w).Add(v);
842  }
843  }
844  }
845  }
846 
847  while (! S.Empty()) {
848  const int w = S.Top();
849  const double SigmaW = sigma.GetDat(w);
850  const double DeltaW = delta.GetDat(w);
851  const TIntV NIdV = P.GetDat(w);
852  S.Pop();
853  for (int i = 0; i < NIdV.Len(); i++) {
854  const int NId = NIdV[i];
855  const double c = (sigma.GetDat(NId)*1.0/SigmaW) * (1+DeltaW);
856  delta.AddDat(NId) += c;
857  if (DoEdgeCent) {
858  if (Graph->HasFlag(gfDirected) && IsDir) {
859  EdgeBtwH.AddDat(TIntPr(NId, w)) += c;
860  } else {
861  EdgeBtwH.AddDat(TIntPr(TMath::Mn(NId, w), TMath::Mx(NId, w))) += c;
862  }
863  }
864  }
865  if (DoNodeCent && w != NI.GetId()) {
866  NodeBtwH.AddDat(w) += delta.GetDat(w)/2.0; }
867  }
868  }
869 }
870 
871 void GetWeightedBetweennessCentr(const PNEANet Graph, TIntFltH& NodeBtwH, TIntPrFltH& EdgeBtwH, const TFltV& Attr, const double& NodeFrac, const bool& IsDir) {
872  TIntV NIdV; Graph->GetNIdV(NIdV);
873  if (NodeFrac < 1.0) { // calculate beetweenness centrality for a subset of nodes
874  NIdV.Shuffle(TInt::Rnd);
875  for (int i = int((1.0-NodeFrac)*NIdV.Len()); i > 0; i--) {
876  NIdV.DelLast(); }
877  }
878  GetWeightedBetweennessCentr(Graph, NIdV, NodeBtwH, true, EdgeBtwH, true,
879  Attr, IsDir);
880 }
881 
882 void GetWeightedBetweennessCentr(const PNEANet Graph, TIntFltH& NodeBtwH, const TFltV& Attr, const double& NodeFrac, const bool& IsDir) {
883  TIntPrFltH EdgeBtwH;
884  TIntV NIdV; Graph->GetNIdV(NIdV);
885  if (NodeFrac < 1.0) { // calculate beetweenness centrality for a subset of nodes
886  NIdV.Shuffle(TInt::Rnd);
887  for (int i = int((1.0-NodeFrac)*NIdV.Len()); i > 0; i--) {
888  NIdV.DelLast(); }
889  }
890  GetWeightedBetweennessCentr(Graph, NIdV, NodeBtwH, true, EdgeBtwH, false,
891  Attr, IsDir);
892 }
893 
894 void GetWeightedBetweennessCentr(const PNEANet Graph, TIntPrFltH& EdgeBtwH, const TFltV& Attr, const double& NodeFrac, const bool& IsDir) {
895  TIntFltH NodeBtwH;
896  TIntV NIdV; Graph->GetNIdV(NIdV);
897  if (NodeFrac < 1.0) { // calculate beetweenness centrality for a subset of nodes
898  NIdV.Shuffle(TInt::Rnd);
899  for (int i = int((1.0-NodeFrac)*NIdV.Len()); i > 0; i--) {
900  NIdV.DelLast(); }
901  }
902  GetWeightedBetweennessCentr(Graph, NIdV, NodeBtwH, false, EdgeBtwH, true,
903  Attr, IsDir);
904 }
905 
908  const TVec<PNEANet>& GraphSeq,
909  TTableContext* Context,
910  const double& C = 0.85, const double& Eps = 1e-4, const int& MaxIter = 100) {
911  TVec<PTable> TableSeq(GraphSeq.Len());
912  TSnap::MapPageRank(GraphSeq, TableSeq, Context, C, Eps, MaxIter);
913  return TTableIterator(TableSeq);
914 }
915 
918  const TVec<PNEANet>& GraphSeq,
919  TTableContext* Context,
920  const int& MaxIter = 20) {
921  TVec<PTable> TableSeq(GraphSeq.Len());
922  TSnap::MapHits(GraphSeq, TableSeq, Context, MaxIter);
923  return TTableIterator(TableSeq);
924 }
925 
926 }; // namespace TSnap
double GetGroupDegreeCentr(const PUNGraph &Graph, const PUNGraph &Group)
Definition: centr.cpp:59
#define IAssert(Cond)
Definition: bd.h:262
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
Main namespace for all the Snap global entities.
Definition: alg.h:1
bool Empty()
Definition: ds.h:2591
TStr GetStr() const
Definition: dt.h:1200
double GetDegreeCentr(const PUNGraph &Graph, const int &NId)
Definition: centr.cpp:5
TIntH * AllCombinationsMN(int m, int n)
Definition: centr.cpp:157
int Intersect(TUNGraph::TNodeI Node, TIntH NNodes)
Intersect.
Definition: centr.cpp:584
bool Empty() const
Definition: ds.h:2646
int GetWeightedPageRank(const PNEANet Graph, TIntFltH &PRankH, const TStr &Attr, const double &C, const double &Eps, const int &MaxIter)
Weighted PageRank (TODO: Use template)
Definition: centr.cpp:396
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
int GetWeightedShortestPath(const PNEANet Graph, const int &SrcNId, TIntFltH &NIdDistH, const TFltV &Attr)
Definition: centr.cpp:700
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
int GetWeightedPageRankMP(const PNEANet Graph, TIntFltH &PRankH, const TStr &Attr, const double &C, const double &Eps, const int &MaxIter)
Definition: centr.cpp:443
TVal & Top()
Definition: ds.h:2595
static const int Mx
Definition: dt.h:1142
int GetInNId(const int &EdgeN) const
Returns ID of EdgeN-th in-node (the node pointing to the current node).
Definition: network.h:1817
TIter BegI() const
Definition: hash.h:213
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
int findMinimum(TIntV &Frontier, TIntFltH &NIdDistH)
Definition: centr.cpp:685
Definition: ss.h:72
Iterator over a vector of tables.
Definition: table.h:423
bool GetInt(const int &FldN, int &Val) const
If the field FldN is an integer its value is returned in Val and the function returns true...
Definition: ss.cpp:447
void Clr(const bool &DoDel=false)
Definition: ds.h:2592
Execution context.
Definition: table.h:180
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
Node iterator. Only forward iteration (operator++) is supported.
Definition: network.h:1792
TIntFltH EventImportance(const PNGraph &Graph, const int k)
Event importance.
Definition: centr.cpp:527
TIter EndI() const
Definition: hash.h:218
static TRnd Rnd
Definition: dt.h:1146
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:192
Definition: dt.h:1386
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
void MapHits(const TVec< PGraph > &GraphSeq, TVec< PTable > &TableSeq, TTableContext *Context, const int &MaxIter)
Gets sequence of Hits tables from given GraphSeq into TableSeq.
Definition: centr.h:636
int GetDeg() const
Returns degree of the current node.
Definition: graph.h:90
void Pop()
Definition: ds.h:2650
void DelKey(const TKey &Key)
Definition: hash.h:404
int GetId() const
Returns ID of the current node.
Definition: network.h:1807
TTableIterator GetMapPageRank(const TVec< PNEANet > &GraphSeq, TTableContext *Context, const double &C=0.85, const double &Eps=1e-4, const int &MaxIter=100)
Gets sequence of PageRank tables from given GraphSeq.
Definition: centr.cpp:907
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
TTableIterator GetMapHitsIterator(const TVec< PNEANet > &GraphSeq, TTableContext *Context, const int &MaxIter=20)
Gets sequence of Hits tables from given GraphSeq.
Definition: centr.cpp:917
void Gen(const int &ExpectVals)
Definition: hash.h:222
void GetWeightedBetweennessCentr(const PNEANet Graph, const TIntV &BtwNIdV, TIntFltH &NodeBtwH, const bool &DoNodeCent, TIntPrFltH &EdgeBtwH, const bool &DoEdgeCent, const TFltV &Attr, const bool &IsDir)
Computes (approximate) weighted Beetweenness Centrality of all nodes and all edges of the network...
Definition: centr.cpp:752
TIntH MaxCPGreedyBetter(const PUNGraph &Graph, const int k)
Returns centrality Maximum k group.
Definition: centr.cpp:175
int SearchStr(const TStr &Str, const int &BChN=0) const
Definition: dt.cpp:1065
double GetGroupFarnessCentr(const PUNGraph &Graph, const TIntH &GroupNodes)
Definition: centr.cpp:105
Whitespace (space or tab) separated.
Definition: ss.h:11
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:241
double GetGroupClosenessCentr(const PUNGraph &Graph, const TIntH &GroupNodes)
Definition: centr.cpp:169
int GetInDeg() const
Returns in-degree of the current node.
Definition: network.h:1811
double GetGroupDegreeCentr0(const PUNGraph &Graph, const TIntH &GroupNodes)
Definition: centr.cpp:72
double GetWeightedFarnessCentr(const PNEANet Graph, const int &NId, const TFltV &Attr, const bool &Normalized, const bool &IsDir)
Definition: centr.cpp:726
const TVal & Top() const
Definition: ds.h:2648
double GetWeightedClosenessCentr(const PNEANet Graph, const int &NId, const TFltV &Attr, const bool &Normalized, const bool &IsDir)
Definition: centr.cpp:745
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
TIntH MaxCPGreedyBetter1(const PUNGraph &Graph, const int k)
Returns centrality Maximum k group.
Definition: centr.cpp:223
Definition: dt.h:1137
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
int Intersect1(TUNGraph::TNodeI Node, TStr NNodes)
Definition: centr.cpp:650
void Push()
Definition: ds.h:2597
void MapPageRank(const TVec< PGraph > &GraphSeq, TVec< PTable > &TableSeq, TTableContext *Context, const double &C, const double &Eps, const int &MaxIter)
Gets sequence of PageRank tables from given GraphSeq into TableSeq.
Definition: centr.h:621
void Pop()
Definition: ds.h:2599
Definition: dt.h:412
TIntFltH EventImportance1(const PNGraph &Graph, const int k)
Definition: centr.cpp:556
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1335
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
TIntH MaxCPGreedyBetter2(const PUNGraph &Graph, const int k)
Returns centrality Maximum k group.
Definition: centr.cpp:268
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:111
TVec< TInt > TIntV
Definition: ds.h:1594
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
bool Next()
Loads next line from the input file.
Definition: ss.cpp:412
void Push(const TVal &Val)
Definition: ds.h:2653
TIntH LoadNodeList(TStr InFNmNodes)
Definition: centr.cpp:671
void Clr(const bool &DoDel=true)
Definition: ds.h:2635
char * CStr()
Definition: dt.h:479
int GetId() const
Returns ID of the current node.
Definition: graph.h:88
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:237
bool IsStrIn(const TStr &Str) const
Definition: dt.h:557
void DelLast()
Removes the last element of the vector.
Definition: ds.h:665
int Len() const
Definition: hash.h:228
void GetEigenVectorCentr(const PUNGraph &Graph, TIntFltH &NIdEigenH, const double &Eps, const int &MaxIter)
Definition: centr.cpp:11
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
TIntH MaxCPGreedyBetter3(const PUNGraph &Graph, const int k)
Returns centrality Maximum k group.
Definition: centr.cpp:322
THKeyDat * EndI
Definition: hash.h:54
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
PUNGraph * AllGraphsWithNNodes(int n)
Definition: centr.cpp:138
void SortByDat(const bool &Asc=true)
Definition: hash.h:292