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
cmty.h
Go to the documentation of this file.
00001 namespace TSnap {
00002 
00004 // Modularity
00007 template<typename PGraph> double GetModularity(const PGraph& G, const TIntV& NIdV, int GEdges=-1);
00010 template<typename PGraph> double GetModularity(const PGraph& G, const TCnComV& CmtyV, int GEdges=-1);
00014 template<typename PGraph> void GetEdgesInOut(const PGraph& Graph, const TIntV& NIdV, int& EdgesIn, int& EdgesOut);
00015 
00018 double CommunityGirvanNewman(PUNGraph& Graph, TCnComV& CmtyV);
00019 
00023 double CommunityCNM(const PUNGraph& Graph, TCnComV& CmtyV);
00024 
00025 namespace TSnapDetail {
00027 void CmtyGirvanNewmanStep(PUNGraph& Graph, TIntV& Cmty1, TIntV& Cmty2);
00028 }
00029 
00031 // Implementation
00032 template<typename PGraph>
00033 double GetModularity(const PGraph& Graph, const TIntV& NIdV, int GEdges) {
00034   if (GEdges == -1) { GEdges = Graph->GetEdges(); }
00035   double EdgesIn = 0.0, EEdgesIn = 0.0; // EdgesIn=2*number of edges inside the cluster, EEdgesIn=expected edges inside
00036   TIntSet NIdSet(NIdV.Len());
00037   for (int e = 0; e < NIdV.Len(); e++) { // edges inside
00038     NIdSet.AddKey(NIdV[e]); }
00039   for (int e1 = 0; e1 < NIdV.Len(); e1++) {
00040     typename PGraph::TObj::TNodeI NI = Graph->GetNI(NIdV[e1]);
00041     EEdgesIn += NI.GetOutDeg();
00042     for (int i = 0; i < NI.GetOutDeg(); i++) {
00043       if (NIdSet.IsKey(NI.GetOutNId(i))) { EdgesIn += 1; }
00044     }
00045   }
00046   EEdgesIn = EEdgesIn*EEdgesIn/(2.0*GEdges);
00047   if ((EdgesIn - EEdgesIn) == 0) { return 0; }
00048   else { return (EdgesIn - EEdgesIn) / (2.0*GEdges); } // modularity
00049 }
00050 
00051 template<typename PGraph>
00052 double GetModularity(const PGraph& G, const TCnComV& CmtyV, int GEdges) {
00053   if (GEdges == -1) { GEdges = G->GetEdges(); }
00054   double Modularity = 0;
00055   for (int c = 0; c < CmtyV.Len(); c++) {
00056     Modularity += GetModularity(G, CmtyV[c](), GEdges);
00057   }
00058   return Modularity;
00059 }
00060 
00061 template<typename PGraph>
00062 void GetEdgesInOut(const PGraph& Graph, const TIntV& NIdV, int& EdgesIn, int& EdgesOut) {
00063   EdgesIn=0;
00064   EdgesOut=0;
00065   TIntSet NIdSet(NIdV.Len());
00066   for (int e = 0; e < NIdV.Len(); e++) {
00067     NIdSet.AddKey(NIdV[e]); }
00068   for (int e = 0; e < NIdV.Len(); e++) {
00069     typename PGraph::TObj::TNodeI NI = Graph->GetNI(NIdV[e]);
00070     for (int i = 0; i < NI.GetOutDeg(); i++) {
00071       if (NIdSet.IsKey(NI.GetOutNId(i))) { EdgesIn += 1; }
00072       else { EdgesOut += 1; }
00073     }
00074   }
00075   EdgesIn /= 2;
00076 }
00077 
00078 }; // namespace TSnap