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
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