SNAP Library 2.4, Developer Reference  2015-05-11 19:40:56
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 double GetFarnessCentr(const PUNGraph& Graph, const int& NId);
42 double GetClosenessCentr(const PUNGraph& Graph, const int& NId);
45 template <class PGraph> int GetNodeEcc(const PGraph& Graph, const int& NId, const bool& IsDir=false);
46 
50 void GetBetweennessCentr(const PUNGraph& Graph, TIntFltH& NIdBtwH, const double& NodeFrac=1.0);
54 void GetBetweennessCentr(const PUNGraph& Graph, TIntPrFltH& EdgeBtwH, const double& NodeFrac=1.0);
59 void GetBetweennessCentr(const PUNGraph& Graph, TIntFltH& NIdBtwH, TIntPrFltH& EdgeBtwH, const double& NodeFrac=1.0);
65 void GetBetweennessCentr(const PUNGraph& Graph, const TIntV& BtwNIdV, TIntFltH& NodeBtwH, const bool& DoNodeCent, TIntPrFltH& EdgeBtwH, const bool& DoEdgeCent);
66 
69 void GetEigenVectorCentr(const PUNGraph& Graph, TIntFltH& NIdEigenH, const double& Eps=1e-4, const int& MaxIter=100);
70 
73 template<class PGraph> void GetPageRank(const PGraph& Graph, TIntFltH& PRankH, const double& C=0.85, const double& Eps=1e-4, const int& MaxIter=100);
76 template<class PGraph> void GetHits(const PGraph& Graph, TIntFltH& NIdHubH, TIntFltH& NIdAuthH, const int& MaxIter=20);
77 
79 // Implementation
80 template <class PGraph>
81 int GetNodeEcc(const PGraph& Graph, const int& NId, const bool& IsDir) {
82  int NodeEcc;
83  int Dist;
84  TBreathFS<PGraph> BFS(Graph);
85  // get shortest paths to all the nodes
86  BFS.DoBfs(NId, true, ! IsDir, -1, TInt::Mx);
87 
88  NodeEcc = 0;
89  // find the largest value
90  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
91  Dist = BFS.NIdDistH[i];
92  if (Dist > NodeEcc) {
93  NodeEcc = Dist;
94  }
95  }
96  return NodeEcc;
97 }
98 
99 // Page Rank -- there are two different implementations (uncomment the desired 2 lines):
100 // Berkhin -- (the correct way) see Algorithm 1 of P. Berkhin, A Survey on PageRank Computing, Internet Mathematics, 2005
101 // iGraph -- iGraph implementation(which treats leaked PageRank in a funny way)
102 template<class PGraph>
103 void GetPageRank(const PGraph& Graph, TIntFltH& PRankH, const double& C, const double& Eps, const int& MaxIter) {
104  const int NNodes = Graph->GetNodes();
105  //const double OneOver = 1.0/double(NNodes);
106  PRankH.Gen(NNodes);
107  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
108  PRankH.AddDat(NI.GetId(), 1.0/NNodes);
109  //IAssert(NI.GetId() == PRankH.GetKey(PRankH.Len()-1));
110  }
111  TFltV TmpV(NNodes);
112  for (int iter = 0; iter < MaxIter; iter++) {
113  int j = 0;
114  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++, j++) {
115  TmpV[j] = 0;
116  for (int e = 0; e < NI.GetInDeg(); e++) {
117  const int InNId = NI.GetInNId(e);
118  const int OutDeg = Graph->GetNI(InNId).GetOutDeg();
119  if (OutDeg > 0) {
120  TmpV[j] += PRankH.GetDat(InNId) / OutDeg; }
121  }
122  TmpV[j] = C*TmpV[j]; // Berkhin (the correct way of doing it)
123  //TmpV[j] = C*TmpV[j] + (1.0-C)*OneOver; // iGraph
124  }
125  double diff=0, sum=0, NewVal;
126  for (int i = 0; i < TmpV.Len(); i++) { sum += TmpV[i]; }
127  const double Leaked = (1.0-sum) / double(NNodes);
128  for (int i = 0; i < PRankH.Len(); i++) { // re-instert leaked PageRank
129  NewVal = TmpV[i] + Leaked; // Berkhin
130  //NewVal = TmpV[i] / sum; // iGraph
131  diff += fabs(NewVal-PRankH[i]);
132  PRankH[i] = NewVal;
133  }
134  if (diff < Eps) { break; }
135  }
136 }
137 
138 template<class PGraph>
139 void GetHits(const PGraph& Graph, TIntFltH& NIdHubH, TIntFltH& NIdAuthH, const int& MaxIter) {
140  const int NNodes = Graph->GetNodes();
141  NIdHubH.Gen(NNodes);
142  NIdAuthH.Gen(NNodes);
143  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
144  NIdHubH.AddDat(NI.GetId(), 1.0);
145  NIdAuthH.AddDat(NI.GetId(), 1.0);
146  }
147  double Norm=0;
148  for (int iter = 0; iter < MaxIter; iter++) {
149  // update authority scores
150  Norm = 0;
151  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
152  double& Auth = NIdAuthH.GetDat(NI.GetId()).Val;
153  Auth = 0;
154  for (int e = 0; e < NI.GetInDeg(); e++) {
155  Auth += NIdHubH.GetDat(NI.GetInNId(e)); }
156  Norm += Auth*Auth;
157  }
158  Norm = sqrt(Norm);
159  for (int i = 0; i < NIdAuthH.Len(); i++) { NIdAuthH[i] /= Norm; }
160  // update hub scores
161  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
162  double& Hub = NIdHubH.GetDat(NI.GetId()).Val;
163  Hub = 0;
164  for (int e = 0; e < NI.GetOutDeg(); e++) {
165  Hub += NIdAuthH.GetDat(NI.GetOutNId(e)); }
166  Norm += Hub*Hub;
167  }
168  Norm = sqrt(Norm);
169  for (int i = 0; i < NIdHubH.Len(); i++) { NIdHubH[i] /= Norm; }
170  }
171  // make sure Hub and Authority scores normalize to L2 norm 1
172  Norm = 0.0;
173  for (int i = 0; i < NIdHubH.Len(); i++) { Norm += TMath::Sqr(NIdHubH[i]); }
174  Norm = sqrt(Norm);
175  for (int i = 0; i < NIdHubH.Len(); i++) { NIdHubH[i] /= Norm; }
176  Norm = 0.0;
177  for (int i = 0; i < NIdAuthH.Len(); i++) { Norm += TMath::Sqr(NIdAuthH[i]); }
178  Norm = sqrt(Norm);
179  for (int i = 0; i < NIdAuthH.Len(); i++) { NIdAuthH[i] /= Norm; }
180 }
181 
182 }; // namespace TSnap
double GetGroupDegreeCentr(const PUNGraph &Graph, const PUNGraph &Group)
Definition: centr.cpp:183
double GetDegreeCentr(const PUNGraph &Graph, const int &NId)
Definition: centr.cpp:5
int Intersect(TUNGraph::TNodeI Node, TIntH NNodes)
Intersect.
Definition: centr.cpp:577
static const int Mx
Definition: dt.h:1047
void GetPageRank(const PGraph &Graph, TIntFltH &PRankH, const double &C=0.85, const double &Eps=1e-4, const int &MaxIter=100)
Definition: centr.h:103
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:108
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
void GetBetweennessCentr(const PUNGraph &Graph, const TIntV &BtwNIdV, TIntFltH &NodeBtwH, const bool &DoNodeCent, TIntPrFltH &EdgeBtwH, const bool &DoEdgeCent)
Definition: centr.cpp:28
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:63
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TIntFltH EventImportance(const PNGraph &Graph, const int k)
Event importance.
Definition: centr.cpp:520
static double Sqr(const double &x)
Definition: xmath.h:12
void Gen(const int &ExpectVals)
Definition: hash.h:180
TIntH MaxCPGreedyBetter(const PUNGraph &Graph, const int k)
Returns centrality Maximum k group.
Definition: centr.cpp:299
double GetGroupClosenessCentr(const PUNGraph &Graph, const TIntH &GroupNodes)
Definition: centr.cpp:293
double GetClosenessCentr(const PUNGraph &Graph, const int &NId)
Definition: centr.cpp:22
int GetNodeEcc(const PGraph &Graph, const int &NId, const bool &IsDir=false)
Definition: centr.h:81
void GetHits(const PGraph &Graph, TIntFltH &NIdHubH, TIntFltH &NIdAuthH, const int &MaxIter=20)
Definition: centr.h:139
TIntH MaxCPGreedyBetter1(const PUNGraph &Graph, const int k)
Returns centrality Maximum k group.
Definition: centr.cpp:347
int Intersect1(TUNGraph::TNodeI Node, TStr NNodes)
Definition: centr.cpp:643
Definition: dt.h:412
TIntH MaxCPGreedyBetter2(const PUNGraph &Graph, const int k)
Returns centrality Maximum k group.
Definition: centr.cpp:392
double GetFarnessCentr(const PUNGraph &Graph, const int &NId)
Definition: centr.cpp:11
Definition: bd.h:196
TIntH LoadNodeList(TStr InFNmNodes)
Definition: centr.cpp:664
TIntH NIdDistH
Definition: bfsdfs.h:79
int Len() const
Definition: hash.h:186
void GetEigenVectorCentr(const PUNGraph &Graph, TIntFltH &NIdEigenH, const double &Eps, const int &MaxIter)
Definition: centr.cpp:135
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
TIntH MaxCPGreedyBetter3(const PUNGraph &Graph, const int k)
Returns centrality Maximum k group.
Definition: centr.cpp:446