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.h
Go to the documentation of this file.
1 namespace TSnap {
2 
4 // Node centrality measures (See: http://en.wikipedia.org/wiki/Centrality)
5 
8 double GetDegreeCentr(const PUNGraph& Graph, const int& NId);
11 //double GetGroupDegreeCentr(const PUNGraph& Graph, const PUNGraph& Group);
12 double GetGroupDegreeCentr(const PUNGraph& Graph, const TIntH& GroupNodes);
15 //double GetGroupDegreeCentr(const PUNGraph& Graph, const PUNGraph& Group);
16 double GetGroupClosenessCentr(const PUNGraph& Graph, const TIntH& GroupNodes);
18 TIntH MaxCPGreedyBetter(const PUNGraph& Graph, const int k);
20 TIntH MaxCPGreedyBetter1(const PUNGraph& Graph, const int k);
22 TIntH MaxCPGreedyBetter2(const PUNGraph& Graph, const int k);
24 TIntH MaxCPGreedyBetter3(const PUNGraph& Graph, const int k);
26 TIntFltH EventImportance(const PNGraph& Graph, const int k);
28 int Intersect(TUNGraph::TNodeI Node, TIntH NNodes);
30 int Intersect(TUNGraph::TNodeI Node, TStr NNodes);
32 int Intersect(TUNGraph::TNodeI Node, int *NNodes, int NNodes_br);
33 //Load nodes list
34 int Intersect1(TUNGraph::TNodeI Node, TStr NNodes);
35 //Load nodes list
36 TIntH LoadNodeList(TStr InFNmNodes);
39 template <class PGraph> double GetFarnessCentr(const PGraph& Graph, const int& NId, const bool& Normalized=true, const bool& IsDir=false);
40 
41 template <class PGraph> double GetFarnessCentrMP(const PGraph& Graph, const int& NId, const bool& Normalized=true, const bool& IsDir=false);
42 
45 double GetWeightedFarnessCentr(const PNEANet Graph, const int& NId, const TFltV& Attr, const bool& Normalized=true, const bool& IsDir=false);
46 
49 template <class PGraph> double GetClosenessCentr(const PGraph& Graph, const int& NId, const bool& Normalized=true, const bool& IsDir=false);
50 template <class PGraph> double GetClosenessCentrMP(const PGraph& Graph, const int& NId, const bool& Normalized=true, const bool& IsDir=false);
53 double GetWeightedClosenessCentr(const PNEANet Graph, const int& NId, const TFltV& Attr, const bool& Normalized=true, const bool& IsDir=false);
56 template <class PGraph> int GetNodeEcc(const PGraph& Graph, const int& NId, const bool& IsDir=false);
57 
61 template<class PGraph> void GetBetweennessCentr(const PGraph& Graph, TIntFltH& NIdBtwH, const double& NodeFrac=1.0, const bool& IsDir=false);
65 void GetWeightedBetweennessCentr(const PNEANet Graph, TIntFltH& NIdBtwH, const TFltV& Attr, const double& NodeFrac=1.0, const bool& IsDir=false);
69 template<class PGraph> void GetBetweennessCentr(const PGraph& Graph, TIntPrFltH& EdgeBtwH, const double& NodeFrac=1.0, const bool& IsDir=false);
73 void GetWeightedBetweennessCentr(const PNEANet Graph, TIntPrFltH& EdgeBtwH, const TFltV& Attr, const double& NodeFrac=1.0, const bool& IsDir=false);
78 template<class PGraph> void GetBetweennessCentr(const PGraph& Graph, TIntFltH& NIdBtwH, TIntPrFltH& EdgeBtwH, const double& NodeFrac=1.0, const bool& IsDir=false);
83 void GetWeightedBetweennessCentr(const PNEANet Graph, TIntFltH& NIdBtwH, TIntPrFltH& EdgeBtwH, const TFltV& Attr, const double& NodeFrac=1.0, const bool& IsDir=false);
89 template<class PGraph> void GetBetweennessCentr(const PGraph& Graph, const TIntV& BtwNIdV, TIntFltH& NodeBtwH, const bool& DoNodeCent, TIntPrFltH& EdgeBtwH, const bool& DoEdgeCent, const bool& IsDir);
91 void GetWeightedBetweennessCentr(const PNEANet Graph, const TIntV& BtwNIdV, TIntFltH& NodeBtwH, const bool& DoNodeCent, TIntPrFltH& EdgeBtwH, const bool& DoEdgeCent, const TFltV& Attr, const bool& IsDir);
94 void GetEigenVectorCentr(const PUNGraph& Graph, TIntFltH& NIdEigenH, const double& Eps=1e-4, const int& MaxIter=100);
95 
98 template<class PGraph> void GetPageRank(const PGraph& Graph, TIntFltH& PRankH, const double& C=0.85, const double& Eps=1e-4, const int& MaxIter=100);
99 template<class PGraph> void GetPageRank_v1(const PGraph& Graph, TIntFltH& PRankH, const double& C=0.85, const double& Eps=1e-4, const int& MaxIter=100);
100 #ifdef USE_OPENMP
101 template<class PGraph> void GetPageRankMP(const PGraph& Graph, TIntFltH& PRankH, const double& C=0.85, const double& Eps=1e-4, const int& MaxIter=100);
102 #endif
103 
105 int GetWeightedPageRank(const PNEANet Graph, TIntFltH& PRankH, const TStr& Attr, const double& C=0.85, const double& Eps=1e-4, const int& MaxIter=100);
106 #ifdef USE_OPENMP
107 int GetWeightedPageRankMP(const PNEANet Graph, TIntFltH& PRankH, const TStr& Attr, const double& C=0.85, const double& Eps=1e-4, const int& MaxIter=100);
108 #endif
109 
112 template<class PGraph> void GetHits(const PGraph& Graph, TIntFltH& NIdHubH, TIntFltH& NIdAuthH, const int& MaxIter=20);
113 #ifdef USE_OPENMP
114 template<class PGraph> void GetHitsMP(const PGraph& Graph, TIntFltH& NIdHubH, TIntFltH& NIdAuthH, const int& MaxIter=20);
115 #endif
116 
119 int GetWeightedShortestPath(const PNEANet Graph, const int& SrcNId, TIntFltH& NIdDistH, const TFltV& Attr);
121 // Implementation
122 template <class PGraph>
123 double GetFarnessCentr(const PGraph& Graph, const int& NId, const bool& Normalized, const bool& IsDir) {
124  TIntH NDistH(Graph->GetNodes());
125  TSnap::GetShortPath<PGraph>(Graph, NId, NDistH, IsDir, TInt::Mx);
126 
127  double sum = 0;
128  for (TIntH::TIter I = NDistH.BegI(); I < NDistH.EndI(); I++) {
129  sum += I->Dat();
130  }
131  if (NDistH.Len() > 1) {
132  double centr = sum/double(NDistH.Len()-1);
133  if (Normalized) {
134  centr *= (Graph->GetNodes() - 1)/double(NDistH.Len()-1);
135  }
136  return centr;
137  }
138  else { return 0.0; }
139 }
140 
141 template <class PGraph>
142 double GetFarnessCentrMP(const PGraph& Graph, const int& NId, const bool& Normalized, const bool& IsDir) {
143  TIntH NDistH(Graph->GetNodes());
144  TSnap::GetShortPath<PGraph>(Graph, NId, NDistH, IsDir, TInt::Mx);
145 
146  double sum = 0;
147  for (TIntH::TIter I = NDistH.BegI(); I < NDistH.EndI(); I++) {
148  sum += I->Dat();
149  }
150  if (NDistH.Len() > 1) {
151  double centr = sum/double(NDistH.Len()-1);
152  if (Normalized) {
153  centr *= (Graph->GetNodes() - 1)/double(NDistH.Len()-1);
154  }
155  return centr;
156  }
157  else { return 0.0; }
158 }
159 
160 template <class PGraph>
161 double GetClosenessCentr(const PGraph& Graph, const int& NId, const bool& Normalized, const bool& IsDir) {
162  const double Farness = GetFarnessCentr<PGraph> (Graph, NId, Normalized, IsDir);
163  if (Farness != 0.0) { return 1.0/Farness; }
164  else { return 0.0; }
165  return 0.0;
166 }
167 
168 template <class PGraph>
169 double GetClosenessCentrMP(const PGraph& Graph, const int& NId, const bool& Normalized, const bool& IsDir) {
170  const double Farness = GetFarnessCentrMP<PGraph> (Graph, NId, Normalized, IsDir);
171  if (Farness != 0.0) { return 1.0/Farness; }
172  else { return 0.0; }
173  return 0.0;
174 }
175 
176 template <class PGraph>
177 int GetNodeEcc(const PGraph& Graph, const int& NId, const bool& IsDir) {
178  int NodeEcc;
179  int Dist;
180  TBreathFS<PGraph> BFS(Graph);
181  // get shortest paths to all the nodes
182  BFS.DoBfs(NId, true, ! IsDir, -1, TInt::Mx);
183 
184  NodeEcc = 0;
185  // find the largest value
186  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
187  Dist = BFS.NIdDistH[i];
188  if (Dist > NodeEcc) {
189  NodeEcc = Dist;
190  }
191  }
192  return NodeEcc;
193 }
194 
195 // Page Rank -- there are two different implementations (uncomment the desired 2 lines):
196 // Berkhin -- (the correct way) see Algorithm 1 of P. Berkhin, A Survey on PageRank Computing, Internet Mathematics, 2005
197 // iGraph -- iGraph implementation(which treats leaked PageRank in a funny way)
198 // This implementation is an unoptimized version, it accesses nodes via a hash table.
199 template<class PGraph>
200 void GetPageRank_v1(const PGraph& Graph, TIntFltH& PRankH, const double& C, const double& Eps, const int& MaxIter) {
201  const int NNodes = Graph->GetNodes();
202  //const double OneOver = 1.0/double(NNodes);
203  PRankH.Gen(NNodes);
204  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
205  PRankH.AddDat(NI.GetId(), 1.0/NNodes);
206  //IAssert(NI.GetId() == PRankH.GetKey(PRankH.Len()-1));
207  }
208  TFltV TmpV(NNodes);
209  for (int iter = 0; iter < MaxIter; iter++) {
210  int j = 0;
211  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++, j++) {
212  TmpV[j] = 0;
213  for (int e = 0; e < NI.GetInDeg(); e++) {
214  const int InNId = NI.GetInNId(e);
215  const int OutDeg = Graph->GetNI(InNId).GetOutDeg();
216  if (OutDeg > 0) {
217  TmpV[j] += PRankH.GetDat(InNId) / OutDeg; }
218  }
219  TmpV[j] = C*TmpV[j]; // Berkhin (the correct way of doing it)
220  //TmpV[j] = C*TmpV[j] + (1.0-C)*OneOver; // iGraph
221  }
222  double diff=0, sum=0, NewVal;
223  for (int i = 0; i < TmpV.Len(); i++) { sum += TmpV[i]; }
224  const double Leaked = (1.0-sum) / double(NNodes);
225  for (int i = 0; i < PRankH.Len(); i++) { // re-instert leaked PageRank
226  NewVal = TmpV[i] + Leaked; // Berkhin
227  //NewVal = TmpV[i] / sum; // iGraph
228  diff += fabs(NewVal-PRankH[i]);
229  PRankH[i] = NewVal;
230  }
231  if (diff < Eps) { break; }
232  }
233 }
234 
235 // Page Rank -- there are two different implementations (uncomment the desired 2 lines):
236 // Berkhin -- (the correct way) see Algorithm 1 of P. Berkhin, A Survey on PageRank Computing, Internet Mathematics, 2005
237 // iGraph -- iGraph implementation(which treats leaked PageRank in a funny way)
238 // This implementation is an optimized version, it builds a vector and accesses nodes via the vector.
239 template<class PGraph>
240 void GetPageRank(const PGraph& Graph, TIntFltH& PRankH, const double& C, const double& Eps, const int& MaxIter) {
241  const int NNodes = Graph->GetNodes();
242  TVec<typename PGraph::TObj::TNodeI> NV;
243  PRankH.Gen(NNodes);
244  int MxId = -1;
245  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
246  NV.Add(NI);
247  PRankH.AddDat(NI.GetId(), 1.0/NNodes);
248  int Id = NI.GetId();
249  if (Id > MxId) {
250  MxId = Id;
251  }
252  }
253 
254  TFltV PRankV(MxId+1);
255  TIntV OutDegV(MxId+1);
256 
257  for (int j = 0; j < NNodes; j++) {
258  typename PGraph::TObj::TNodeI NI = NV[j];
259  int Id = NI.GetId();
260  PRankV[Id] = 1.0/NNodes;
261  OutDegV[Id] = NI.GetOutDeg();
262  }
263 
264  TFltV TmpV(NNodes);
265 
266  for (int iter = 0; iter < MaxIter; iter++) {
267  for (int j = 0; j < NNodes; j++) {
268  typename PGraph::TObj::TNodeI NI = NV[j];
269  TFlt Tmp = 0;
270  for (int e = 0; e < NI.GetInDeg(); e++) {
271  const int InNId = NI.GetInNId(e);
272  const int OutDeg = OutDegV[InNId];
273  if (OutDeg > 0) {
274  Tmp += PRankV[InNId] / OutDeg;
275  }
276  }
277  TmpV[j] = C*Tmp; // Berkhin (the correct way of doing it)
278  }
279  double sum = 0;
280  for (int i = 0; i < TmpV.Len(); i++) { sum += TmpV[i]; }
281  const double Leaked = (1.0-sum) / double(NNodes);
282 
283  double diff = 0;
284  for (int i = 0; i < NNodes; i++) {
285  typename PGraph::TObj::TNodeI NI = NV[i];
286  double NewVal = TmpV[i] + Leaked; // Berkhin
287  int Id = NI.GetId();
288  diff += fabs(NewVal-PRankV[Id]);
289  PRankV[Id] = NewVal;
290  }
291  if (diff < Eps) { break; }
292  }
293 
294  for (int i = 0; i < NNodes; i++) {
295  typename PGraph::TObj::TNodeI NI = NV[i];
296  PRankH[i] = PRankV[NI.GetId()];
297  }
298 }
299 
300 #ifdef USE_OPENMP
301 // Page Rank -- there are two different implementations (uncomment the desired 2 lines):
302 // Berkhin -- (the correct way) see Algorithm 1 of P. Berkhin, A Survey on PageRank Computing, Internet Mathematics, 2005
303 // iGraph -- iGraph implementation(which treats leaked PageRank in a funny way)
304 // This is a parallel, optimized version.
305 template<class PGraph>
306 void GetPageRankMP(const PGraph& Graph, TIntFltH& PRankH, const double& C, const double& Eps, const int& MaxIter) {
307  const int NNodes = Graph->GetNodes();
308  TVec<typename PGraph::TObj::TNodeI> NV;
309  PRankH.Gen(NNodes);
310 
311  int MxId = -1;
312  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
313  NV.Add(NI);
314  PRankH.AddDat(NI.GetId(), 1.0/NNodes);
315  int Id = NI.GetId();
316  if (Id > MxId) {
317  MxId = Id;
318  }
319  }
320 
321  TFltV PRankV(MxId+1);
322  TIntV OutDegV(MxId+1);
323 
324  #pragma omp parallel for schedule(dynamic,10000)
325  for (int j = 0; j < NNodes; j++) {
326  typename PGraph::TObj::TNodeI NI = NV[j];
327  int Id = NI.GetId();
328  PRankV[Id] = 1.0/NNodes;
329  OutDegV[Id] = NI.GetOutDeg();
330  }
331 
332  TFltV TmpV(NNodes);
333  for (int iter = 0; iter < MaxIter; iter++) {
334  #pragma omp parallel for schedule(dynamic,10000)
335  for (int j = 0; j < NNodes; j++) {
336  typename PGraph::TObj::TNodeI NI = NV[j];
337  TFlt Tmp = 0;
338  for (int e = 0; e < NI.GetInDeg(); e++) {
339  const int InNId = NI.GetInNId(e);
340  const int OutDeg = OutDegV[InNId];
341  if (OutDeg > 0) {
342  Tmp += PRankV[InNId] / OutDeg;
343  }
344  }
345  TmpV[j] = C*Tmp; // Berkhin (the correct way of doing it)
346  }
347 
348  double sum = 0;
349  #pragma omp parallel for reduction(+:sum) schedule(dynamic,10000)
350  for (int i = 0; i < TmpV.Len(); i++) { sum += TmpV[i]; }
351  const double Leaked = (1.0-sum) / double(NNodes);
352 
353  double diff = 0;
354  #pragma omp parallel for reduction(+:diff) schedule(dynamic,10000)
355  for (int i = 0; i < NNodes; i++) {
356  double NewVal = TmpV[i] + Leaked; // Berkhin
357  int Id = NV[i].GetId();
358  diff += fabs(NewVal-PRankV[Id]);
359  PRankV[Id] = NewVal;
360  }
361  if (diff < Eps) { break; }
362  }
363 
364  #pragma omp parallel for schedule(dynamic,10000)
365  for (int i = 0; i < NNodes; i++) {
366  typename PGraph::TObj::TNodeI NI = NV[i];
367  PRankH[i] = PRankV[NI.GetId()];
368  }
369 }
370 #endif // USE_OPENMP
371 
372 // Betweenness Centrality
373 template<class PGraph>
374 void GetBetweennessCentr(const PGraph& Graph, const TIntV& BtwNIdV, TIntFltH& NodeBtwH, const bool& DoNodeCent, TIntPrFltH& EdgeBtwH, const bool& DoEdgeCent, const bool& IsDir) {
375  if (DoNodeCent) { NodeBtwH.Clr(); }
376  if (DoEdgeCent) { EdgeBtwH.Clr(); }
377  const int nodes = Graph->GetNodes();
378  TIntS S(nodes);
379  TIntQ Q(nodes);
380  TIntIntVH P(nodes); // one vector for every node
381  TIntFltH delta(nodes);
382  TIntH sigma(nodes), d(nodes);
383  // init
384  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
385  if (DoNodeCent) {
386  NodeBtwH.AddDat(NI.GetId(), 0); }
387  if (DoEdgeCent) {
388  for (int e = 0; e < NI.GetOutDeg(); e++) {
389  if (Graph->HasFlag(gfDirected) && IsDir) {
390  // add all outgoing edges for directed graphs
391  EdgeBtwH.AddDat(TIntPr(NI.GetId(), NI.GetOutNId(e)), 0);
392  } else {
393  // add each edge only once in undirected graphs
394  if (NI.GetId() < NI.GetOutNId(e)) {
395  EdgeBtwH.AddDat(TIntPr(NI.GetId(), NI.GetOutNId(e)), 0);
396  }
397  }
398  }
399  // add incoming edges in directed graphs that were not added yet
400  if (Graph->HasFlag(gfDirected) && !IsDir) {
401  for (int e = 0; e < NI.GetInDeg(); e++) {
402  if (NI.GetId() < NI.GetInNId(e) &&
403  !Graph->IsEdge(NI.GetId(), NI.GetInNId(e))) {
404  EdgeBtwH.AddDat(TIntPr(NI.GetId(), NI.GetInNId(e)), 0);
405  }
406  }
407  }
408  }
409  sigma.AddDat(NI.GetId(), 0);
410  d.AddDat(NI.GetId(), -1);
411  P.AddDat(NI.GetId(), TIntV());
412  delta.AddDat(NI.GetId(), 0);
413  }
414  // calc betweeness
415  for (int k=0; k < BtwNIdV.Len(); k++) {
416  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(BtwNIdV[k]);
417  // reset
418  for (int i = 0; i < sigma.Len(); i++) {
419  sigma[i]=0; d[i]=-1; delta[i]=0; P[i].Clr(false);
420  }
421  S.Clr(false);
422  Q.Clr(false);
423  sigma.AddDat(NI.GetId(), 1);
424  d.AddDat(NI.GetId(), 0);
425  Q.Push(NI.GetId());
426  while (! Q.Empty()) {
427  const int v = Q.Top(); Q.Pop();
428  const typename PGraph::TObj::TNodeI NI2 = Graph->GetNI(v);
429  S.Push(v);
430  const int VDat = d.GetDat(v);
431  // iterate over all outgoing edges
432  for (int e = 0; e < NI2.GetOutDeg(); e++) {
433  const int w = NI2.GetOutNId(e);
434  if (d.GetDat(w) < 0) { // find w for the first time
435  Q.Push(w);
436  d.AddDat(w, VDat+1);
437  }
438  //shortest path to w via v ?
439  if (d.GetDat(w) == VDat+1) {
440  sigma.AddDat(w) += sigma.GetDat(v);
441  P.GetDat(w).Add(v);
442  }
443  }
444  // if ignoring direction in directed networks, iterate over incoming edges
445  if (Graph->HasFlag(gfDirected) && !IsDir) {
446  for (int e = 0; e < NI2.GetInDeg(); e++) {
447  const int w = NI2.GetInNId(e);
448  // skip neighbors that are also outgoing
449  if (Graph->IsEdge(NI2.GetId(), w)) {
450  continue;
451  }
452  if (d.GetDat(w) < 0) { // find w for the first time
453  Q.Push(w);
454  d.AddDat(w, VDat+1);
455  }
456  //shortest path to w via v ?
457  if (d.GetDat(w) == VDat+1) {
458  sigma.AddDat(w) += sigma.GetDat(v);
459  P.GetDat(w).Add(v);
460  }
461  }
462  }
463  }
464  while (! S.Empty()) {
465  const int w = S.Top();
466  const double SigmaW = sigma.GetDat(w);
467  const double DeltaW = delta.GetDat(w);
468  const TIntV NIdV = P.GetDat(w);
469  S.Pop();
470  for (int i = 0; i < NIdV.Len(); i++) {
471  const int NId = NIdV[i];
472  const double c = (sigma.GetDat(NId)*1.0/SigmaW) * (1+DeltaW);
473  delta.AddDat(NId) += c;
474  if (DoEdgeCent) {
475  if (Graph->HasFlag(gfDirected) && IsDir) {
476  EdgeBtwH.AddDat(TIntPr(NId, w)) += c;
477  } else {
478  EdgeBtwH.AddDat(TIntPr(TMath::Mn(NId, w), TMath::Mx(NId, w))) += c;
479  }
480  }
481  }
482  if (DoNodeCent && w != NI.GetId()) {
483  NodeBtwH.AddDat(w) += delta.GetDat(w)/2.0; }
484  }
485  }
486 }
487 
488 template<class PGraph>
489 void GetBetweennessCentr(const PGraph& Graph, TIntFltH& NodeBtwH, const double& NodeFrac, const bool& IsDir) {
490  TIntPrFltH EdgeBtwH;
491  TIntV NIdV; Graph->GetNIdV(NIdV);
492  if (NodeFrac < 1.0) { // calculate beetweenness centrality for a subset of nodes
493  NIdV.Shuffle(TInt::Rnd);
494  for (int i = int((1.0-NodeFrac)*NIdV.Len()); i > 0; i--) {
495  NIdV.DelLast(); }
496  }
497  GetBetweennessCentr<PGraph> (Graph, NIdV, NodeBtwH, true, EdgeBtwH, false, IsDir);
498 }
499 
500 template<class PGraph>
501 void GetBetweennessCentr(const PGraph& Graph, TIntPrFltH& EdgeBtwH, const double& NodeFrac, const bool& IsDir) {
502  TIntFltH NodeBtwH;
503  TIntV NIdV; Graph->GetNIdV(NIdV);
504  if (NodeFrac < 1.0) { // calculate beetweenness centrality for a subset of nodes
505  NIdV.Shuffle(TInt::Rnd);
506  for (int i = int((1.0-NodeFrac)*NIdV.Len()); i > 0; i--) {
507  NIdV.DelLast(); }
508  }
509  GetBetweennessCentr<PGraph> (Graph, NIdV, NodeBtwH, false, EdgeBtwH, true, IsDir);
510 }
511 
512 template<class PGraph>
513 void GetBetweennessCentr(const PGraph& Graph, TIntFltH& NodeBtwH, TIntPrFltH& EdgeBtwH, const double& NodeFrac, const bool& IsDir) {
514  TIntV NIdV; Graph->GetNIdV(NIdV);
515  if (NodeFrac < 1.0) { // calculate beetweenness centrality for a subset of nodes
516  NIdV.Shuffle(TInt::Rnd);
517  for (int i = int((1.0-NodeFrac)*NIdV.Len()); i > 0; i--) {
518  NIdV.DelLast(); }
519  }
520  GetBetweennessCentr<PGraph> (Graph, NIdV, NodeBtwH, true, EdgeBtwH, true, IsDir);
521 }
522 
523 template<class PGraph>
524 void GetHits(const PGraph& Graph, TIntFltH& NIdHubH, TIntFltH& NIdAuthH, const int& MaxIter) {
525  const int NNodes = Graph->GetNodes();
526  NIdHubH.Gen(NNodes);
527  NIdAuthH.Gen(NNodes);
528  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
529  NIdHubH.AddDat(NI.GetId(), 1.0);
530  NIdAuthH.AddDat(NI.GetId(), 1.0);
531  }
532  double Norm=0;
533  for (int iter = 0; iter < MaxIter; iter++) {
534  // update authority scores
535  Norm = 0;
536  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
537  double& Auth = NIdAuthH.GetDat(NI.GetId()).Val;
538  Auth = 0;
539  for (int e = 0; e < NI.GetInDeg(); e++) {
540  Auth += NIdHubH.GetDat(NI.GetInNId(e)); }
541  Norm += Auth*Auth;
542  }
543  Norm = sqrt(Norm);
544  for (int i = 0; i < NIdAuthH.Len(); i++) { NIdAuthH[i] /= Norm; }
545  // update hub scores
546  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
547  double& Hub = NIdHubH.GetDat(NI.GetId()).Val;
548  Hub = 0;
549  for (int e = 0; e < NI.GetOutDeg(); e++) {
550  Hub += NIdAuthH.GetDat(NI.GetOutNId(e)); }
551  Norm += Hub*Hub;
552  }
553  Norm = sqrt(Norm);
554  for (int i = 0; i < NIdHubH.Len(); i++) { NIdHubH[i] /= Norm; }
555  }
556  // make sure Hub and Authority scores normalize to L2 norm 1
557  Norm = 0.0;
558  for (int i = 0; i < NIdHubH.Len(); i++) { Norm += TMath::Sqr(NIdHubH[i]); }
559  Norm = sqrt(Norm);
560  for (int i = 0; i < NIdHubH.Len(); i++) { NIdHubH[i] /= Norm; }
561  Norm = 0.0;
562  for (int i = 0; i < NIdAuthH.Len(); i++) { Norm += TMath::Sqr(NIdAuthH[i]); }
563  Norm = sqrt(Norm);
564  for (int i = 0; i < NIdAuthH.Len(); i++) { NIdAuthH[i] /= Norm; }
565 }
566 
567 #ifdef USE_OPENMP
568 template<class PGraph>
569 void GetHitsMP(const PGraph& Graph, TIntFltH& NIdHubH, TIntFltH& NIdAuthH, const int& MaxIter) {
570  const int NNodes = Graph->GetNodes();
571  TIntV NV;
572  NIdHubH.Gen(NNodes);
573  NIdAuthH.Gen(NNodes);
574  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
575  NV.Add(NI.GetId());
576  NIdHubH.AddDat(NI.GetId(), 1.0);
577  NIdAuthH.AddDat(NI.GetId(), 1.0);
578  }
579  double Norm=0;
580  for (int iter = 0; iter < MaxIter; iter++) {
581  // update authority scores
582  Norm = 0;
583  #pragma omp parallel for reduction(+:Norm) schedule(dynamic,1000)
584  for (int i = 0; i < NNodes; i++) {
585  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NV[i]);
586  double& Auth = NIdAuthH.GetDat(NI.GetId()).Val;
587  Auth = 0;
588  for (int e = 0; e < NI.GetInDeg(); e++) {
589  Auth += NIdHubH.GetDat(NI.GetInNId(e)); }
590  Norm = Norm + Auth*Auth;
591  }
592  Norm = sqrt(Norm);
593  for (int i = 0; i < NIdAuthH.Len(); i++) { NIdAuthH[i] /= Norm; }
594  // update hub scores
595  #pragma omp parallel for reduction(+:Norm) schedule(dynamic,1000)
596  for (int i = 0; i < NNodes; i++) {
597  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NV[i]);
598  double& Hub = NIdHubH.GetDat(NI.GetId()).Val;
599  Hub = 0;
600  for (int e = 0; e < NI.GetOutDeg(); e++) {
601  Hub += NIdAuthH.GetDat(NI.GetOutNId(e)); }
602  Norm = Norm + Hub*Hub;
603  }
604  Norm = sqrt(Norm);
605  for (int i = 0; i < NIdHubH.Len(); i++) { NIdHubH[i] /= Norm; }
606  }
607  // make sure Hub and Authority scores normalize to L2 norm 1
608  Norm = 0.0;
609  for (int i = 0; i < NIdHubH.Len(); i++) { Norm += TMath::Sqr(NIdHubH[i]); }
610  Norm = sqrt(Norm);
611  for (int i = 0; i < NIdHubH.Len(); i++) { NIdHubH[i] /= Norm; }
612  Norm = 0.0;
613  for (int i = 0; i < NIdAuthH.Len(); i++) { Norm += TMath::Sqr(NIdAuthH[i]); }
614  Norm = sqrt(Norm);
615  for (int i = 0; i < NIdAuthH.Len(); i++) { NIdAuthH[i] /= Norm; }
616 }
617 #endif
618 
620 template <class PGraph>
621 void MapPageRank(const TVec<PGraph>& GraphSeq, TVec<PTable>& TableSeq,
622  TTableContext* Context,
623  const double& C, const double& Eps, const int& MaxIter) {
624  int NumGraphs = GraphSeq.Len();
625  TableSeq.Reserve(NumGraphs, NumGraphs);
626  // This loop is parallelizable.
627  for (TInt i = 0; i < NumGraphs; i++) {
628  TIntFltH PRankH;
629  GetPageRank(GraphSeq[i], PRankH, C, Eps, MaxIter);
630  TableSeq[i] = TTable::TableFromHashMap(PRankH, "NodeId", "PageRank", Context, false);
631  }
632 }
633 
635 template <class PGraph>
636 void MapHits(const TVec<PGraph>& GraphSeq, TVec<PTable>& TableSeq,
637  TTableContext* Context,
638  const int& MaxIter) {
639  int NumGraphs = GraphSeq.Len();
640  TableSeq.Reserve(NumGraphs, NumGraphs);
641  // This loop is parallelizable.
642  for (TInt i = 0; i < NumGraphs; i++) {
643  TIntFltH HubH;
644  TIntFltH AuthH;
645  GetHits(GraphSeq[i], HubH, AuthH, MaxIter);
646  PTable HubT = TTable::TableFromHashMap(HubH, "NodeId", "Hub", Context, false);
647  PTable AuthT = TTable::TableFromHashMap(AuthH, "NodeId", "Authority", Context, false);
648  PTable HitsT = HubT->Join("NodeId", AuthT, "NodeId");
649  HitsT->Rename("1.NodeId", "NodeId");
650  HitsT->Rename("1.Hub", "Hub");
651  HitsT->Rename("2.Authority", "Authority");
652  TStrV V = TStrV(3, 0);
653  V.Add("NodeId");
654  V.Add("Hub");
655  V.Add("Authority");
656  HitsT->ProjectInPlace(V);
657  TableSeq[i] = HitsT;
658  }
659 }
660 
661 }; // namespace TSnap
662 
TSnap::GetGroupDegreeCentr
double GetGroupDegreeCentr(const PUNGraph &Graph, const PUNGraph &Group)
Definition: centr.cpp:59
TMath::Mn
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TIntPr
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TSnap
Main namespace for all the Snap global entities.
Definition: alg.h:1
TSStack::Empty
bool Empty()
Definition: ds.h:2591
TSnap::GetDegreeCentr
double GetDegreeCentr(const PUNGraph &Graph, const int &NId)
Definition: centr.cpp:5
TSnap::Intersect
int Intersect(TUNGraph::TNodeI Node, TIntH NNodes)
Intersect.
Definition: centr.cpp:584
TQQueue::Empty
bool Empty() const
Definition: ds.h:2646
TSnap::GetWeightedPageRank
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
TSnap::GetWeightedShortestPath
int GetWeightedShortestPath(const PNEANet Graph, const int &SrcNId, TIntFltH &NIdDistH, const TFltV &Attr)
Definition: centr.cpp:700
TMath::Mx
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TSnap::GetFarnessCentrMP
double GetFarnessCentrMP(const PGraph &Graph, const int &NId, const bool &Normalized=true, const bool &IsDir=false)
Definition: centr.h:142
TSnap::GetWeightedPageRankMP
int GetWeightedPageRankMP(const PNEANet Graph, TIntFltH &PRankH, const TStr &Attr, const double &C, const double &Eps, const int &MaxIter)
Definition: centr.cpp:443
TSStack::Top
TVal & Top()
Definition: ds.h:2595
TInt::Mx
static const int Mx
Definition: dt.h:1142
TSnap::GetPageRank
void GetPageRank(const PGraph &Graph, TIntFltH &PRankH, const double &C=0.85, const double &Eps=1e-4, const int &MaxIter=100)
Definition: centr.h:240
TBreathFS::DoBfs
int DoBfs(const int &StartNode, const bool &FollowOut, const bool &FollowIn, const int &TargetNId=-1, const int &MxDist=TInt::Mx)
Performs BFS from node id StartNode for at maps MxDist steps by only following in-links (parameter Fo...
Definition: bfsdfs.h:128
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
TSnap::GetBetweennessCentr
void GetBetweennessCentr(const PGraph &Graph, TIntFltH &NIdBtwH, const double &NodeFrac=1.0, const bool &IsDir=false)
Definition: centr.h:489
TSnap::GetHitsMP
void GetHitsMP(const PGraph &Graph, TIntFltH &NIdHubH, TIntFltH &NIdAuthH, const int &MaxIter=20)
Definition: centr.h:569
TSStack::Clr
void Clr(const bool &DoDel=false)
Definition: ds.h:2592
TTableContext
Execution context.
Definition: table.h:180
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TSnap::EventImportance
TIntFltH EventImportance(const PNGraph &Graph, const int k)
Event importance.
Definition: centr.cpp:527
TTable::TableFromHashMap
static PTable TableFromHashMap(const THash< TInt, TInt > &H, const TStr &Col1, const TStr &Col2, TTableContext *Context, const TBool IsStrKeys=false)
Builds table from hash table of int->int.
Definition: table.h:988
TMath::Sqr
static double Sqr(const double &x)
Definition: xmath.h:12
TInt::Rnd
static TRnd Rnd
Definition: dt.h:1146
TSnap::GetFarnessCentr
double GetFarnessCentr(const PGraph &Graph, const int &NId, const bool &Normalized=true, const bool &IsDir=false)
Definition: centr.h:123
TFlt
Definition: dt.h:1386
TSnap::MapHits
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
TSnap::GetPageRankMP
void GetPageRankMP(const PGraph &Graph, TIntFltH &PRankH, const double &C=0.85, const double &Eps=1e-4, const int &MaxIter=100)
Definition: centr.h:306
TSnap::GetClosenessCentrMP
double GetClosenessCentrMP(const PGraph &Graph, const int &NId, const bool &Normalized=true, const bool &IsDir=false)
Definition: centr.h:169
TQQueue::Pop
void Pop()
Definition: ds.h:2650
THash::Gen
void Gen(const int &ExpectVals)
Definition: hash.h:222
TSnap::GetWeightedBetweennessCentr
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
TSnap::MaxCPGreedyBetter
TIntH MaxCPGreedyBetter(const PUNGraph &Graph, const int k)
Returns centrality Maximum k group.
Definition: centr.cpp:175
TSnap::GetGroupClosenessCentr
double GetGroupClosenessCentr(const PUNGraph &Graph, const TIntH &GroupNodes)
Definition: centr.cpp:169
TSnap::GetNodeEcc
int GetNodeEcc(const PGraph &Graph, const int &NId, const bool &IsDir=false)
Definition: centr.h:177
TSnap::GetWeightedFarnessCentr
double GetWeightedFarnessCentr(const PNEANet Graph, const int &NId, const TFltV &Attr, const bool &Normalized, const bool &IsDir)
Definition: centr.cpp:726
TQQueue::Top
const TVal & Top() const
Definition: ds.h:2648
TSnap::GetWeightedClosenessCentr
double GetWeightedClosenessCentr(const PNEANet Graph, const int &NId, const TFltV &Attr, const bool &Normalized, const bool &IsDir)
Definition: centr.cpp:745
TSnap::GetHits
void GetHits(const PGraph &Graph, TIntFltH &NIdHubH, TIntFltH &NIdAuthH, const int &MaxIter=20)
Definition: centr.h:524
TSnap::MaxCPGreedyBetter1
TIntH MaxCPGreedyBetter1(const PUNGraph &Graph, const int k)
Returns centrality Maximum k group.
Definition: centr.cpp:223
TInt
Definition: dt.h:1137
gfDirected
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
TSnap::Intersect1
int Intersect1(TUNGraph::TNodeI Node, TStr NNodes)
Definition: centr.cpp:650
TStrV
TVec< TStr > TStrV
Definition: ds.h:1599
TSStack::Push
void Push()
Definition: ds.h:2597
TSnap::MapPageRank
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
TSStack::Pop
void Pop()
Definition: ds.h:2599
TStr
Definition: dt.h:412
TSnap::GetPageRank_v1
void GetPageRank_v1(const PGraph &Graph, TIntFltH &PRankH, const double &C=0.85, const double &Eps=1e-4, const int &MaxIter=100)
Definition: centr.h:200
TVec::Shuffle
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1335
TSnap::MaxCPGreedyBetter2
TIntH MaxCPGreedyBetter2(const PUNGraph &Graph, const int k)
Returns centrality Maximum k group.
Definition: centr.cpp:268
TIntV
TVec< TInt > TIntV
Definition: ds.h:1594
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
TPt
Definition: bd.h:196
TQQueue::Push
void Push(const TVal &Val)
Definition: ds.h:2653
TSnap::LoadNodeList
TIntH LoadNodeList(TStr InFNmNodes)
Definition: centr.cpp:671
TVec::Reserve
void Reserve(const TSizeTy &_MxVals)
Reserves enough memory for the vector to store _MxVals elements.
Definition: ds.h:543
TQQueue::Clr
void Clr(const bool &DoDel=true)
Definition: ds.h:2635
TSnap::GetClosenessCentr
double GetClosenessCentr(const PGraph &Graph, const int &NId, const bool &Normalized=true, const bool &IsDir=false)
Definition: centr.h:161
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TBreathFS::NIdDistH
TIntH NIdDistH
Definition: bfsdfs.h:88
TVec::DelLast
void DelLast()
Removes the last element of the vector.
Definition: ds.h:665
THash::Len
int Len() const
Definition: hash.h:228
TSnap::GetEigenVectorCentr
void GetEigenVectorCentr(const PUNGraph &Graph, TIntFltH &NIdEigenH, const double &Eps, const int &MaxIter)
Definition: centr.cpp:11
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
TSnap::MaxCPGreedyBetter3
TIntH MaxCPGreedyBetter3(const PUNGraph &Graph, const int k)
Returns centrality Maximum k group.
Definition: centr.cpp:322
THashKeyDatI::EndI
THKeyDat * EndI
Definition: hash.h:54