SNAP Library 3.0, User Reference  2016-07-20 17:56:49
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& IsDir, const bool& Normalized = true);
40 
41 template <class PGraph> double GetFarnessCentrMP(const PGraph& Graph, const int& NId, const bool& IsDir, const bool& Normalized = true);
42 
45 double GetWeightedFarnessCentr(const PNEANet Graph, const int& NId, const bool& IsDir, const TFltV& Attr, const bool& Normalized = true);
46 
49 template <class PGraph> double GetClosenessCentr(const PGraph& Graph, const int& NId, const bool& IsDir, const bool& Normalized = true);
50 template <class PGraph> double GetClosenessCentrMP(const PGraph& Graph, const int& NId, const bool& IsDir, const bool& Normalized = true);
53 double GetWeightedClosenessCentr(const PNEANet Graph, const int& NId, const bool& IsDir, const TFltV& Attr, const bool& Normalized = true);
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 bool& IsDir=false, const double& NodeFrac=1.0);
65 void GetWeightedBetweennessCentr(const PNEANet Graph, TIntFltH& NIdBtwH, const TFltV& Attr, const bool& IsDir=false, const double& NodeFrac=1.0);
69 template<class PGraph> void GetBetweennessCentr(const PGraph& Graph, TIntPrFltH& EdgeBtwH, const bool& IsDir=false, const double& NodeFrac=1.0);
73 void GetWeightedBetweennessCentr(const PNEANet Graph, TIntPrFltH& EdgeBtwH, const TFltV& Attr, const bool& IsDir=false, const double& NodeFrac=1.0);
78 template<class PGraph> void GetBetweennessCentr(const PGraph& Graph, TIntFltH& NIdBtwH, TIntPrFltH& EdgeBtwH, const bool& IsDir=false, const double& NodeFrac=1.0);
83 void GetWeightedBetweennessCentr(const PNEANet Graph, TIntFltH& NIdBtwH, TIntPrFltH& EdgeBtwH, const TFltV& Attr, const bool& IsDir=false, const double& NodeFrac=1.0);
89 template<class PGraph> void GetBetweennessCentr(const PGraph& Graph, const TIntV& BtwNIdV, TIntFltH& NodeBtwH, const bool& IsDir, const bool& DoNodeCent, TIntPrFltH& EdgeBtwH, const bool& DoEdgeCent);
91 void GetWeightedBetweennessCentr(const PNEANet Graph, const TIntV& BtwNIdV, TIntFltH& NodeBtwH, const bool& IsDir, const bool& DoNodeCent, TIntPrFltH& EdgeBtwH, const bool& DoEdgeCent, const TFltV& Attr);
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& IsDir, const bool& Normalized) {
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& IsDir, const bool& Normalized) {
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& IsDir, const bool& Normalized) {
162  const double Farness = GetFarnessCentr<PGraph> (Graph, NId, IsDir, Normalized);
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& IsDir, const bool& Normalized) {
170  const double Farness = GetFarnessCentrMP<PGraph> (Graph, NId, IsDir, Normalized);
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& IsDir, const bool& DoNodeCent, TIntPrFltH& EdgeBtwH, const bool& DoEdgeCent) {
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 (NI.GetId() < NI.GetOutNId(e)) {
390  EdgeBtwH.AddDat(TIntPr(NI.GetId(), NI.GetOutNId(e)), 0);
391  }
392  }
393  }
394  sigma.AddDat(NI.GetId(), 0);
395  d.AddDat(NI.GetId(), -1);
396  P.AddDat(NI.GetId(), TIntV());
397  delta.AddDat(NI.GetId(), 0);
398  }
399  // calc betweeness
400  for (int k=0; k < BtwNIdV.Len(); k++) {
401  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(BtwNIdV[k]);
402  // reset
403  for (int i = 0; i < sigma.Len(); i++) {
404  sigma[i]=0; d[i]=-1; delta[i]=0; P[i].Clr(false);
405  }
406  S.Clr(false);
407  Q.Clr(false);
408  sigma.AddDat(NI.GetId(), 1);
409  d.AddDat(NI.GetId(), 0);
410  Q.Push(NI.GetId());
411  while (! Q.Empty()) {
412  const int v = Q.Top(); Q.Pop();
413  const typename PGraph::TObj::TNodeI NI2 = Graph->GetNI(v);
414  S.Push(v);
415  const int VDat = d.GetDat(v);
416  for (int e = 0; e < NI2.GetOutDeg(); e++) {
417  const int w = NI2.GetOutNId(e);
418  if (d.GetDat(w) < 0) { // find w for the first time
419  Q.Push(w);
420  d.AddDat(w, VDat+1);
421  }
422  //shortest path to w via v ?
423  if (d.GetDat(w) == VDat+1) {
424  sigma.AddDat(w) += sigma.GetDat(v);
425  P.GetDat(w).Add(v);
426  }
427  }
428  }
429  while (! S.Empty()) {
430  const int w = S.Top();
431  const double SigmaW = sigma.GetDat(w);
432  const double DeltaW = delta.GetDat(w);
433  const TIntV NIdV = P.GetDat(w);
434  S.Pop();
435  for (int i = 0; i < NIdV.Len(); i++) {
436  const int NId = NIdV[i];
437  const double c = (sigma.GetDat(NId)*1.0/SigmaW) * (1+DeltaW);
438  delta.AddDat(NId) += c;
439  if (DoEdgeCent) {
440  EdgeBtwH.AddDat(TIntPr(TMath::Mn(NId, w), TMath::Mx(NId, w))) += c; }
441  }
442  double factor = (IsDir) ? 1.0 : 2.0;
443  if (DoNodeCent && w != NI.GetId()) {
444  NodeBtwH.AddDat(w) += delta.GetDat(w)/factor; }
445  }
446  }
447 }
448 
449 template<class PGraph>
450 void GetBetweennessCentr(const PGraph& Graph, TIntFltH& NodeBtwH, const bool& IsDir, const double& NodeFrac) {
451  TIntPrFltH EdgeBtwH;
452  TIntV NIdV; Graph->GetNIdV(NIdV);
453  if (NodeFrac < 1.0) { // calculate beetweenness centrality for a subset of nodes
454  NIdV.Shuffle(TInt::Rnd);
455  for (int i = int((1.0-NodeFrac)*NIdV.Len()); i > 0; i--) {
456  NIdV.DelLast(); }
457  }
458  GetBetweennessCentr<PGraph> (Graph, NIdV, NodeBtwH, IsDir, true, EdgeBtwH, false);
459 }
460 
461 template<class PGraph>
462 void GetBetweennessCentr(const PGraph& Graph, TIntPrFltH& EdgeBtwH, const bool& IsDir, const double& NodeFrac) {
463  TIntFltH NodeBtwH;
464  TIntV NIdV; Graph->GetNIdV(NIdV);
465  if (NodeFrac < 1.0) { // calculate beetweenness centrality for a subset of nodes
466  NIdV.Shuffle(TInt::Rnd);
467  for (int i = int((1.0-NodeFrac)*NIdV.Len()); i > 0; i--) {
468  NIdV.DelLast(); }
469  }
470  GetBetweennessCentr<PGraph> (Graph, NIdV, NodeBtwH, IsDir, false, EdgeBtwH, true);
471 }
472 
473 template<class PGraph>
474 void GetBetweennessCentr(const PGraph& Graph, TIntFltH& NodeBtwH, TIntPrFltH& EdgeBtwH, const bool& IsDir, const double& NodeFrac) {
475  TIntV NIdV; Graph->GetNIdV(NIdV);
476  if (NodeFrac < 1.0) { // calculate beetweenness centrality for a subset of nodes
477  NIdV.Shuffle(TInt::Rnd);
478  for (int i = int((1.0-NodeFrac)*NIdV.Len()); i > 0; i--) {
479  NIdV.DelLast(); }
480  }
481  GetBetweennessCentr<PGraph> (Graph, NIdV, NodeBtwH, IsDir, true, EdgeBtwH, true);
482 }
483 
484 template<class PGraph>
485 void GetHits(const PGraph& Graph, TIntFltH& NIdHubH, TIntFltH& NIdAuthH, const int& MaxIter) {
486  const int NNodes = Graph->GetNodes();
487  NIdHubH.Gen(NNodes);
488  NIdAuthH.Gen(NNodes);
489  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
490  NIdHubH.AddDat(NI.GetId(), 1.0);
491  NIdAuthH.AddDat(NI.GetId(), 1.0);
492  }
493  double Norm=0;
494  for (int iter = 0; iter < MaxIter; iter++) {
495  // update authority scores
496  Norm = 0;
497  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
498  double& Auth = NIdAuthH.GetDat(NI.GetId()).Val;
499  Auth = 0;
500  for (int e = 0; e < NI.GetInDeg(); e++) {
501  Auth += NIdHubH.GetDat(NI.GetInNId(e)); }
502  Norm += Auth*Auth;
503  }
504  Norm = sqrt(Norm);
505  for (int i = 0; i < NIdAuthH.Len(); i++) { NIdAuthH[i] /= Norm; }
506  // update hub scores
507  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
508  double& Hub = NIdHubH.GetDat(NI.GetId()).Val;
509  Hub = 0;
510  for (int e = 0; e < NI.GetOutDeg(); e++) {
511  Hub += NIdAuthH.GetDat(NI.GetOutNId(e)); }
512  Norm += Hub*Hub;
513  }
514  Norm = sqrt(Norm);
515  for (int i = 0; i < NIdHubH.Len(); i++) { NIdHubH[i] /= Norm; }
516  }
517  // make sure Hub and Authority scores normalize to L2 norm 1
518  Norm = 0.0;
519  for (int i = 0; i < NIdHubH.Len(); i++) { Norm += TMath::Sqr(NIdHubH[i]); }
520  Norm = sqrt(Norm);
521  for (int i = 0; i < NIdHubH.Len(); i++) { NIdHubH[i] /= Norm; }
522  Norm = 0.0;
523  for (int i = 0; i < NIdAuthH.Len(); i++) { Norm += TMath::Sqr(NIdAuthH[i]); }
524  Norm = sqrt(Norm);
525  for (int i = 0; i < NIdAuthH.Len(); i++) { NIdAuthH[i] /= Norm; }
526 }
527 
528 #ifdef USE_OPENMP
529 template<class PGraph>
530 void GetHitsMP(const PGraph& Graph, TIntFltH& NIdHubH, TIntFltH& NIdAuthH, const int& MaxIter) {
531  const int NNodes = Graph->GetNodes();
532  TIntV NV;
533  NIdHubH.Gen(NNodes);
534  NIdAuthH.Gen(NNodes);
535  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
536  NV.Add(NI.GetId());
537  NIdHubH.AddDat(NI.GetId(), 1.0);
538  NIdAuthH.AddDat(NI.GetId(), 1.0);
539  }
540  double Norm=0;
541  for (int iter = 0; iter < MaxIter; iter++) {
542  // update authority scores
543  Norm = 0;
544  #pragma omp parallel for reduction(+:Norm) schedule(dynamic,1000)
545  for (int i = 0; i < NNodes; i++) {
546  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NV[i]);
547  double& Auth = NIdAuthH.GetDat(NI.GetId()).Val;
548  Auth = 0;
549  for (int e = 0; e < NI.GetInDeg(); e++) {
550  Auth += NIdHubH.GetDat(NI.GetInNId(e)); }
551  Norm = Norm + Auth*Auth;
552  }
553  Norm = sqrt(Norm);
554  for (int i = 0; i < NIdAuthH.Len(); i++) { NIdAuthH[i] /= Norm; }
555  // update hub scores
556  #pragma omp parallel for reduction(+:Norm) schedule(dynamic,1000)
557  for (int i = 0; i < NNodes; i++) {
558  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NV[i]);
559  double& Hub = NIdHubH.GetDat(NI.GetId()).Val;
560  Hub = 0;
561  for (int e = 0; e < NI.GetOutDeg(); e++) {
562  Hub += NIdAuthH.GetDat(NI.GetOutNId(e)); }
563  Norm = Norm + Hub*Hub;
564  }
565  Norm = sqrt(Norm);
566  for (int i = 0; i < NIdHubH.Len(); i++) { NIdHubH[i] /= Norm; }
567  }
568  // make sure Hub and Authority scores normalize to L2 norm 1
569  Norm = 0.0;
570  for (int i = 0; i < NIdHubH.Len(); i++) { Norm += TMath::Sqr(NIdHubH[i]); }
571  Norm = sqrt(Norm);
572  for (int i = 0; i < NIdHubH.Len(); i++) { NIdHubH[i] /= Norm; }
573  Norm = 0.0;
574  for (int i = 0; i < NIdAuthH.Len(); i++) { Norm += TMath::Sqr(NIdAuthH[i]); }
575  Norm = sqrt(Norm);
576  for (int i = 0; i < NIdAuthH.Len(); i++) { NIdAuthH[i] /= Norm; }
577 }
578 #endif
579 
580 }; // namespace TSnap
581 
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:2525
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:2580
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::GetFarnessCentr
double GetFarnessCentr(const PGraph &Graph, const int &NId, const bool &IsDir, const bool &Normalized=true)
Definition: centr.h:123
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:2529
TInt::Mx
static const int Mx
Definition: dt.h:1049
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:547
TSnap::GetWeightedBetweennessCentr
void GetWeightedBetweennessCentr(const PNEANet Graph, const TIntV &BtwNIdV, TIntFltH &NodeBtwH, const bool &IsDir, const bool &DoNodeCent, TIntPrFltH &EdgeBtwH, const bool &DoEdgeCent, const TFltV &Attr)
Computes (approximate) weighted Beetweenness Centrality of all nodes and all edges of the network...
Definition: centr.cpp:752
TSnap::GetWeightedClosenessCentr
double GetWeightedClosenessCentr(const PNEANet Graph, const int &NId, const bool &IsDir, const TFltV &Attr, const bool &Normalized)
Definition: centr.cpp:745
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:64
TSnap::GetFarnessCentrMP
double GetFarnessCentrMP(const PGraph &Graph, const int &NId, const bool &IsDir, const bool &Normalized=true)
Definition: centr.h:142
TSnap::GetHitsMP
void GetHitsMP(const PGraph &Graph, TIntFltH &NIdHubH, TIntFltH &NIdAuthH, const int &MaxIter=20)
Definition: centr.h:530
TSnap::GetBetweennessCentr
void GetBetweennessCentr(const PGraph &Graph, TIntFltH &NIdBtwH, const bool &IsDir=false, const double &NodeFrac=1.0)
Definition: centr.h:450
TSStack::Clr
void Clr(const bool &DoDel=false)
Definition: ds.h:2526
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TSnap::EventImportance
TIntFltH EventImportance(const PNGraph &Graph, const int k)
Event importance.
Definition: centr.cpp:527
TMath::Sqr
static double Sqr(const double &x)
Definition: xmath.h:12
TInt::Rnd
static TRnd Rnd
Definition: dt.h:1053
TFlt
Definition: dt.h:1293
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
TQQueue::Pop
void Pop()
Definition: ds.h:2584
THash::Gen
void Gen(const int &ExpectVals)
Definition: hash.h:180
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
TQQueue::Top
const TVal & Top() const
Definition: ds.h:2582
TSnap::GetHits
void GetHits(const PGraph &Graph, TIntFltH &NIdHubH, TIntFltH &NIdAuthH, const int &MaxIter=20)
Definition: centr.h:485
TSnap::MaxCPGreedyBetter1
TIntH MaxCPGreedyBetter1(const PUNGraph &Graph, const int k)
Returns centrality Maximum k group.
Definition: centr.cpp:223
TSnap::Intersect1
int Intersect1(TUNGraph::TNodeI Node, TStr NNodes)
Definition: centr.cpp:650
TSStack::Push
void Push()
Definition: ds.h:2531
TSStack::Pop
void Pop()
Definition: ds.h:2533
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
TSnap::GetWeightedFarnessCentr
double GetWeightedFarnessCentr(const PNEANet Graph, const int &NId, const bool &IsDir, const TFltV &Attr, const bool &Normalized)
Definition: centr.cpp:726
TSnap::GetClosenessCentrMP
double GetClosenessCentrMP(const PGraph &Graph, const int &NId, const bool &IsDir, const bool &Normalized=true)
Definition: centr.h:169
TVec::Shuffle
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1271
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:1529
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:319
TQQueue::Push
void Push(const TVal &Val)
Definition: ds.h:2587
TSnap::LoadNodeList
TIntH LoadNodeList(TStr InFNmNodes)
Definition: centr.cpp:671
TQQueue::Clr
void Clr(const bool &DoDel=true)
Definition: ds.h:2569
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TBreathFS::NIdDistH
TIntH NIdDistH
Definition: bfsdfs.h:79
TVec::DelLast
void DelLast()
Removes the last element of the vector.
Definition: ds.h:635
THash::Len
int Len() const
Definition: hash.h:186
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:196
TSnap::MaxCPGreedyBetter3
TIntH MaxCPGreedyBetter3(const PUNGraph &Graph, const int k)
Returns centrality Maximum k group.
Definition: centr.cpp:322
TSnap::GetClosenessCentr
double GetClosenessCentr(const PGraph &Graph, const int &NId, const bool &IsDir, const bool &Normalized=true)
Definition: centr.h:161
THashKeyDatI::EndI
THKeyDat * EndI
Definition: hash.h:45