SNAP Library , Developer Reference  2013-01-07 14:03:36
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
centr.h
Go to the documentation of this file.
00001 namespace TSnap {
00002 
00004 // Node centrality measures (See: http://en.wikipedia.org/wiki/Centrality)
00005 
00008 double GetDegreeCentr(const PUNGraph& Graph, const int& NId);
00011 double GetFarnessCentr(const PUNGraph& Graph, const int& NId);
00014 double GetClosenessCentr(const PUNGraph& Graph, const int& NId);
00017 template <class PGraph> int GetNodeEcc(const PGraph& Graph, const int& NId, const bool& IsDir=false);
00018 
00022 void GetBetweennessCentr(const PUNGraph& Graph, TIntFltH& NIdBtwH, const double& NodeFrac=1.0);
00026 void GetBetweennessCentr(const PUNGraph& Graph, TIntPrFltH& EdgeBtwH, const double& NodeFrac=1.0);
00031 void GetBetweennessCentr(const PUNGraph& Graph, TIntFltH& NIdBtwH, TIntPrFltH& EdgeBtwH, const double& NodeFrac=1.0);
00037 void GetBetweennessCentr(const PUNGraph& Graph, const TIntV& BtwNIdV, TIntFltH& NodeBtwH, const bool& DoNodeCent, TIntPrFltH& EdgeBtwH, const bool& DoEdgeCent);
00038 
00041 void GetEigenVectorCentr(const PUNGraph& Graph, TIntFltH& NIdEigenH, const double& Eps=1e-4, const int& MaxIter=100);
00042 
00045 template<class PGraph> void GetPageRank(const PGraph& Graph, TIntFltH& PRankH, const double& C=0.85, const double& Eps=1e-4, const int& MaxIter=100);
00048 template<class PGraph> void GetHits(const PGraph& Graph, TIntFltH& NIdHubH, TIntFltH& NIdAuthH, const int& MaxIter=20);
00049 
00051 // Implementation 
00052 template <class PGraph>
00053 int GetNodeEcc(const PGraph& Graph, const int& NId, const bool& IsDir) {
00054   int NodeEcc;
00055   int Dist;
00056   TBreathFS<PGraph> BFS(Graph);
00057   // get shortest paths to all the nodes
00058   BFS.DoBfs(NId, true, ! IsDir, -1, TInt::Mx);
00059 
00060   NodeEcc = 0;
00061   // find the largest value
00062   for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
00063     Dist = BFS.NIdDistH[i];
00064     if (Dist > NodeEcc) {
00065       NodeEcc = Dist;
00066     }
00067   }
00068   return NodeEcc;
00069 }
00070 
00071 // Page Rank -- there are two different implementations (uncomment the desired 2 lines):
00072 //   Berkhin -- (the correct way) see Algorithm 1 of P. Berkhin, A Survey on PageRank Computing, Internet Mathematics, 2005
00073 //   iGraph -- iGraph implementation(which treats leaked PageRank in a funny way)
00074 template<class PGraph>
00075 void GetPageRank(const PGraph& Graph, TIntFltH& PRankH, const double& C, const double& Eps, const int& MaxIter) {
00076   const int NNodes = Graph->GetNodes();
00077   //const double OneOver = 1.0/double(NNodes);
00078   PRankH.Gen(NNodes);
00079   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00080     PRankH.AddDat(NI.GetId(), 1.0/NNodes);
00081     //IAssert(NI.GetId() == PRankH.GetKey(PRankH.Len()-1));
00082   }
00083   TFltV TmpV(NNodes);
00084   for (int iter = 0; iter < MaxIter; iter++) {
00085     int j = 0;
00086     for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++, j++) {
00087       TmpV[j] = 0;
00088       for (int e = 0; e < NI.GetInDeg(); e++) {
00089         const int InNId = NI.GetInNId(e);
00090         const int OutDeg = Graph->GetNI(InNId).GetOutDeg();
00091         if (OutDeg > 0) {
00092           TmpV[j] += PRankH.GetDat(InNId) / OutDeg; }
00093       }
00094       TmpV[j] =  C*TmpV[j]; // Berkhin (the correct way of doing it)
00095       //TmpV[j] =  C*TmpV[j] + (1.0-C)*OneOver; // iGraph
00096     }
00097     double diff=0, sum=0, NewVal;
00098     for (int i = 0; i < TmpV.Len(); i++) { sum += TmpV[i]; }
00099     const double Leaked = (1.0-sum) / double(NNodes);
00100     for (int i = 0; i < PRankH.Len(); i++) { // re-instert leaked PageRank
00101       NewVal = TmpV[i] + Leaked; // Berkhin
00102       //NewVal = TmpV[i] / sum;  // iGraph
00103       diff += fabs(NewVal-PRankH[i]);
00104       PRankH[i] = NewVal;
00105     }
00106     if (diff < Eps) { break; }
00107   }
00108 }
00109 
00110 template<class PGraph>
00111 void GetHits(const PGraph& Graph, TIntFltH& NIdHubH, TIntFltH& NIdAuthH, const int& MaxIter) {
00112   const int NNodes = Graph->GetNodes();
00113   NIdHubH.Gen(NNodes);
00114   NIdAuthH.Gen(NNodes);
00115   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00116     NIdHubH.AddDat(NI.GetId(), 1.0);
00117     NIdAuthH.AddDat(NI.GetId(), 1.0);
00118   }
00119   double Norm=0;
00120   for (int iter = 0; iter < MaxIter; iter++) {
00121     // update authority scores
00122     Norm = 0;
00123     for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00124       double& Auth = NIdAuthH.GetDat(NI.GetId()).Val;
00125       Auth = 0;
00126       for (int e = 0; e < NI.GetInDeg(); e++) {
00127         Auth +=  NIdHubH.GetDat(NI.GetInNId(e)); }
00128       Norm += Auth*Auth;
00129     }
00130     Norm = sqrt(Norm);
00131     for (int i = 0; i < NIdAuthH.Len(); i++) { NIdAuthH[i] /= Norm; }
00132     // update hub scores
00133     for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00134       double& Hub = NIdHubH.GetDat(NI.GetId()).Val;
00135       Hub = 0;
00136       for (int e = 0; e < NI.GetOutDeg(); e++) {
00137         Hub += NIdAuthH.GetDat(NI.GetOutNId(e)); }
00138       Norm += Hub*Hub;
00139     }
00140     Norm = sqrt(Norm);
00141     for (int i = 0; i < NIdHubH.Len(); i++) { NIdHubH[i] /= Norm; }
00142   }
00143 }
00144 
00145 }; // namespace TSnap