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
cmty.h
Go to the documentation of this file.
1 namespace TSnap {
2 
4 // Modularity
7 template<typename PGraph> double GetModularity(const PGraph& G, const TIntV& NIdV, int GEdges=-1);
10 template<typename PGraph> double GetModularity(const PGraph& G, const TCnComV& CmtyV, int GEdges=-1);
14 template<typename PGraph> void GetEdgesInOut(const PGraph& Graph, const TIntV& NIdV, int& EdgesInX, int& EdgesOutX);
15 
18 double CommunityGirvanNewman(PUNGraph& Graph, TCnComV& CmtyV);
19 
23 double CommunityCNM(const PUNGraph& Graph, TCnComV& CmtyV);
24 
27 double Infomap(PUNGraph& Graph, TCnComV& CmtyV);
28 
29 double InfomapOnline(PUNGraph& Graph, int n1, int n2, TIntFltH& PAlpha, double& SumPAlphaLogPAlpha, TIntFltH& Qi, TIntH& Module, int& Br, TCnComV& CmtyV);
30 
31 void CmtyEvolutionFileBatch(TStr InFNm, TIntIntHH& sizesCont, TIntIntHH& cCont, TIntIntVH& edges, double alpha, double beta, int CmtyAlg);
32 void CmtyEvolutionFileBatchV(TStr InFNm, TIntIntVH& sizesContV, TIntIntVH& cContV, TIntIntVH& edges, double alpha, double beta, int CmtyAlg);
33 void CmtyEvolutionJson(TStr& Json, TIntIntVH& sizesContV, TIntIntVH& cContV, TIntIntVH& edges);
34 TStr CmtyTest(TStr t, int CmtyAlg);
35 void ReebSimplify(PNGraph& Graph, TIntH& t, int e, PNGraph& gFinal, TIntH& tFinal, bool collapse);
36 void ReebRefine(PNGraph& Graph, TIntH& t, int e, PNGraph& gFinal, TIntH& tFinal, bool collapse);
37 
38 namespace TSnapDetail {
40 void CmtyGirvanNewmanStep(PUNGraph& Graph, TIntV& Cmty1, TIntV& Cmty2);
41 }
42 
44 // Implementation
45 template<typename PGraph>
46 double GetModularity(const PGraph& Graph, const TIntV& NIdV, int GEdges) {
47  if (GEdges == -1) { GEdges = Graph->GetEdges(); }
48  double EdgesIn = 0.0, EEdgesIn = 0.0; // EdgesIn=2*number of edges inside the cluster, EEdgesIn=expected edges inside
49  TIntSet NIdSet(NIdV.Len());
50  for (int e = 0; e < NIdV.Len(); e++) { // edges inside
51  NIdSet.AddKey(NIdV[e]);
52  }
53  for (int e1 = 0; e1 < NIdV.Len(); e1++) {
54  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NIdV[e1]);
55  EEdgesIn += NI.GetOutDeg();
56  for (int i = 0; i < NI.GetOutDeg(); i++) {
57  if (NIdSet.IsKey(NI.GetOutNId(i))) { EdgesIn += 1; }
58  }
59  }
60  EEdgesIn = EEdgesIn*EEdgesIn / (2.0*GEdges);
61  if ((EdgesIn - EEdgesIn) == 0) { return 0; }
62  else { return (EdgesIn - EEdgesIn) / (2.0*GEdges); } // modularity
63 }
64 
65 template<typename PGraph>
66 double GetModularity(const PGraph& G, const TCnComV& CmtyV, int GEdges) {
67  if (GEdges == -1) { GEdges = G->GetEdges(); }
68  double Modularity = 0;
69  for (int c = 0; c < CmtyV.Len(); c++) {
70  Modularity += GetModularity(G, CmtyV[c](), GEdges);
71  }
72  return Modularity;
73 }
74 
75 template<typename PGraph>
76 void GetEdgesInOut(const PGraph& Graph, const TIntV& NIdV, int& EdgesIn, int& EdgesOut) {
77  EdgesIn = 0;
78  EdgesOut = 0;
79  TIntSet NIdSet(NIdV.Len());
80  for (int e = 0; e < NIdV.Len(); e++) {
81  NIdSet.AddKey(NIdV[e]);
82  }
83  for (int e = 0; e < NIdV.Len(); e++) {
84  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NIdV[e]);
85  for (int i = 0; i < NI.GetOutDeg(); i++) {
86  if (NIdSet.IsKey(NI.GetOutNId(i))) { EdgesIn += 1; }
87  else { EdgesOut += 1; }
88  }
89  }
90  EdgesIn /= 2;
91 }
92 
93 }; // namespace TSnap
double CommunityGirvanNewman(PUNGraph &Graph, TCnComV &CmtyV)
Definition: cmty.cpp:312
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
double InfomapOnline(PUNGraph &Graph, int n1, int n2, TIntFltH &PAlpha, double &SumPAlphaLogPAlpha, TIntFltH &Qi, TIntH &Module, int &Br, TCnComV &CmtyV)
Definition: cmty.cpp:417
void ReebSimplify(PNGraph &Graph, TIntH &t, int e, PNGraph &gFinal, TIntH &tFinal, bool collapse)
Definition: cmty.cpp:842
void GetEdgesInOut(const PGraph &Graph, const TIntV &NIdV, int &EdgesInX, int &EdgesOutX)
Definition: cmty.h:76
void CmtyEvolutionFileBatch(TStr InFNm, TIntIntHH &sizesCont, TIntIntHH &cCont, TIntIntVH &edges, double alpha, double beta, int CmtyAlg)
Definition: cmty.cpp:488
void CmtyEvolutionFileBatchV(TStr InFNm, TIntIntVH &sizesContV, TIntIntVH &cContV, TIntIntVH &edges, double alpha, double beta, int CmtyAlg)
Definition: cmty.cpp:439
int AddKey(const TKey &Key)
Definition: shash.h:1254
TStr CmtyTest(TStr InFNm, int CmtyAlg)
Definition: cmty.cpp:825
double GetModularity(const PGraph &G, const TIntV &NIdV, int GEdges=-1)
Definition: cmty.h:46
void CmtyEvolutionJson(TStr &Json, TIntIntVH &sizesContV, TIntIntVH &cContV, TIntIntVH &edges)
Definition: cmty.cpp:723
Definition: dt.h:412
double CommunityCNM(const PUNGraph &Graph, TCnComV &CmtyV)
Definition: cmty.cpp:1447
void ReebRefine(PNGraph &Graph, TIntH &t, int e, PNGraph &gFinal, TIntH &tFinal, bool collapse)
Definition: cmty.cpp:982
Definition: bd.h:196
double Infomap(PUNGraph &Graph, TCnComV &CmtyV)
Definition: cmty.cpp:337
void CmtyGirvanNewmanStep(PUNGraph &Graph, TIntV &Cmty1, TIntV &Cmty2)
A single step of Girvan-Newman clustering procedure.
Definition: cmty.cpp:15