SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
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
TSStack::Empty
bool Empty()
Definition: ds.h:2590
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:2645
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:2594
TInt::Mx
static const int Mx
Definition: dt.h:1139
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:119
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:2591
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:1143
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:1383
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:2649
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:2647
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:1134
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:2596
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:2598
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:2652
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:2634
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:79
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