SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
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
Main namespace for all the Snap global entities.
Definition: alg.h:1
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:419
void ReebSimplify(PNGraph &Graph, TIntH &t, int e, PNGraph &gFinal, TIntH &tFinal, bool collapse)
Definition: cmty.cpp:844
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:490
void CmtyEvolutionFileBatchV(TStr InFNm, TIntIntVH &sizesContV, TIntIntVH &cContV, TIntIntVH &edges, double alpha, double beta, int CmtyAlg)
Definition: cmty.cpp:441
int AddKey(const TKey &Key)
Definition: shash.h:1254
TStr CmtyTest(TStr InFNm, int CmtyAlg)
Definition: cmty.cpp:827
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:725
Definition: dt.h:412
double CommunityCNM(const PUNGraph &Graph, TCnComV &CmtyV)
Definition: cmty.cpp:1449
void ReebRefine(PNGraph &Graph, TIntH &t, int e, PNGraph &gFinal, TIntH &tFinal, bool collapse)
Definition: cmty.cpp:984
Definition: bd.h:196
double Infomap(PUNGraph &Graph, TCnComV &CmtyV)
Definition: cmty.cpp:339
void CmtyGirvanNewmanStep(PUNGraph &Graph, TIntV &Cmty1, TIntV &Cmty2)
A single step of Girvan-Newman clustering procedure.
Definition: cmty.cpp:15