Collaboration diagram for TSnap::TSnapDetail::TCNMQMatrix:

Classes
struct	TCmtyDat

Public Member Functions
	TCNMQMatrix (const PUNGraph &Graph)

void	Init (const PUNGraph &Graph)

TFltIntIntTr	FindMxQEdge ()

bool	MergeBestQ ()

Static Public Member Functions
static double	CmtyCMN (const PUNGraph &Graph, TCnComV &CmtyV)

Private Attributes
THash< TInt, TCmtyDat >	CmtyQH

THeap< TFltIntIntTr >	MxQHeap

TUnionFind	CmtyIdUF

double	Q

Detailed Description

Clauset-Newman-Moore community detection method. At every step two communities that contribute maximum positive value to global modularity are merged. See: Finding community structure in very large networks, A. Clauset, M.E.J. Newman, C. Moore, 2004

Definition at line 1324 of file cmty.cpp.

Constructor & Destructor Documentation

TSnap::TSnapDetail::TCNMQMatrix::TCNMQMatrix ( const PUNGraph & Graph )

inline

Definition at line 1356 of file cmty.cpp.

References Init().

                                      : CmtyQH(Graph->GetNodes()), 
     MxQHeap(Graph->GetNodes()), CmtyIdUF(Graph->GetNodes()) {
     Init(Graph);
   }

Here is the call graph for this function:

Member Function Documentation

static double TSnap::TSnapDetail::TCNMQMatrix::CmtyCMN	(	const PUNGraph &	Graph,
		TCnComV &	CmtyV
	)

inlinestatic

Definition at line 1428 of file cmty.cpp.

References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), TUNGraph::BegNI(), CmtyIdUF, TUNGraph::EndNI(), TUnionFind::Find(), TVec< TVal, TSizeTy >::Gen(), THash< TKey, TDat, THashFunc >::Len(), MergeBestQ(), Q, and TVec< TVal, TSizeTy >::Swap().

Referenced by TSnap::CommunityCNM().

                                                                {
     TCNMQMatrix QMatrix(Graph);
     // maximize modularity
     while (QMatrix.MergeBestQ()) {}
     // reconstruct communities
     THash<TInt, TIntV> IdCmtyH;
     for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
       IdCmtyH.AddDat(QMatrix.CmtyIdUF.Find(NI.GetId())).Add(NI.GetId());
     }
     CmtyV.Gen(IdCmtyH.Len());
     for (int j = 0; j < IdCmtyH.Len(); j++) {
       CmtyV[j].NIdV.Swap(IdCmtyH[j]);
     }
     return QMatrix.Q;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

TFltIntIntTr TSnap::TSnapDetail::TCNMQMatrix::FindMxQEdge ( )

inline

Definition at line 1380 of file cmty.cpp.

References CmtyQH, MxQHeap, TTriple< TVal1, TVal2, TVal3 >::Val1, TTriple< TVal1, TVal2, TVal3 >::Val2, and TTriple< TVal1, TVal2, TVal3 >::Val3.

Referenced by MergeBestQ().

                              {
     while (true) {
       if (MxQHeap.Empty()) { break; }
       const TFltIntIntTr TopQ = MxQHeap.PopHeap();
       if (!CmtyQH.IsKey(TopQ.Val2) || !CmtyQH.IsKey(TopQ.Val3)) { continue; }
       if (TopQ.Val1 != CmtyQH.GetDat(TopQ.Val2).GetMxQ() && TopQ.Val1 != CmtyQH.GetDat(TopQ.Val3).GetMxQ()) { continue; }
       return TopQ;
     }
     return TFltIntIntTr(-1, -1, -1);
   }

Here is the caller graph for this function:

void TSnap::TSnapDetail::TCNMQMatrix::Init ( const PUNGraph & Graph )

inline

Definition at line 1360 of file cmty.cpp.

References TUnionFind::Add(), TSnap::TSnapDetail::TCNMQMatrix::TCmtyDat::AddQ(), TUNGraph::BegNI(), CmtyIdUF, CmtyQH, TUNGraph::EndNI(), TUNGraph::GetEdges(), TSnap::TSnapDetail::TCNMQMatrix::TCmtyDat::GetMxQ(), TSnap::TSnapDetail::TCNMQMatrix::TCmtyDat::GetMxQNId(), TUNGraph::GetNI(), TUNGraph::TNodeI::GetOutDeg(), MxQHeap, Q, and TMath::Sqr().

Referenced by TCNMQMatrix().

                                    {
     const double M = 0.5 / Graph->GetEdges(); // 1/2m
     Q = 0.0;
     for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
       CmtyIdUF.Add(NI.GetId());
       const int OutDeg = NI.GetOutDeg();
       if (OutDeg == 0) { continue; }
       TCmtyDat& Dat = CmtyQH.AddDat(NI.GetId(), TCmtyDat(M * OutDeg, OutDeg));
       for (int e = 0; e < NI.GetOutDeg(); e++) {
         const int DstNId = NI.GetOutNId(e);
         const double DstMod = 2 * M * (1.0 - OutDeg * Graph->GetNI(DstNId).GetOutDeg() * M);
         Dat.AddQ(DstNId, DstMod);
       }
       Q += -1.0*TMath::Sqr(OutDeg*M);
       if (NI.GetId() < Dat.GetMxQNId()) {
         MxQHeap.Add(TFltIntIntTr(Dat.GetMxQ(), NI.GetId(), Dat.GetMxQNId()));
       }
     }
     MxQHeap.MakeHeap();
   }

Here is the call graph for this function:

Here is the caller graph for this function:

bool TSnap::TSnapDetail::TCNMQMatrix::MergeBestQ ( )

inline

Definition at line 1391 of file cmty.cpp.

References TSnap::TSnapDetail::TCNMQMatrix::TCmtyDat::AddQ(), CmtyIdUF, CmtyQH, TSnap::TSnapDetail::TCNMQMatrix::TCmtyDat::DegFrac, TSnap::TSnapDetail::TCNMQMatrix::TCmtyDat::DelLink(), THash< TKey, TDat, THashFunc >::Empty(), FindMxQEdge(), THash< TKey, TDat, THashFunc >::FNextKeyId(), THash< TKey, TDat, THashFunc >::GetDat(), THash< TKey, TDat, THashFunc >::GetKey(), THash< TKey, TDat, THashFunc >::IsKey(), TMath::Mn(), TMath::Mx(), MxQHeap, TSnap::TSnapDetail::TCNMQMatrix::TCmtyDat::NIdQH, Q, TUnionFind::Union(), TTriple< TVal1, TVal2, TVal3 >::Val1, TTriple< TVal1, TVal2, TVal3 >::Val2, and TTriple< TVal1, TVal2, TVal3 >::Val3.

Referenced by CmtyCMN().

                     {
     const TFltIntIntTr TopQ = FindMxQEdge();
     if (TopQ.Val1 <= 0.0) { return false; }
     // joint communities
     const int I = TopQ.Val3;
     const int J = TopQ.Val2;
     CmtyIdUF.Union(I, J); // join
     Q += TopQ.Val1;
     TCmtyDat& DatJ = CmtyQH.GetDat(J);
     { TCmtyDat& DatI = CmtyQH.GetDat(I);
     DatI.DelLink(J);  DatJ.DelLink(I);
     for (int i = -1; DatJ.NIdQH.FNextKeyId(i); ) {
       const int K = DatJ.NIdQH.GetKey(i);
       TCmtyDat& DatK = CmtyQH.GetDat(K);
       double NewQ = DatJ.NIdQH[i];
       if (DatI.NIdQH.IsKey(K)) { NewQ = NewQ + DatI.NIdQH.GetDat(K);  DatK.DelLink(I); }     // K connected to I and J
       else { NewQ = NewQ - 2 * DatI.DegFrac*DatK.DegFrac; }  // K connected to J not I
       DatJ.AddQ(K, NewQ);
       DatK.AddQ(J, NewQ);
       MxQHeap.PushHeap(TFltIntIntTr(NewQ, TMath::Mn(J, K), TMath::Mx(J, K)));
     }
     for (int i = -1; DatI.NIdQH.FNextKeyId(i); ) {
       const int K = DatI.NIdQH.GetKey(i);
       if (!DatJ.NIdQH.IsKey(K)) { // K connected to I not J
         TCmtyDat& DatK = CmtyQH.GetDat(K);
         const double NewQ = DatI.NIdQH[i] - 2 * DatJ.DegFrac*DatK.DegFrac; 
         DatJ.AddQ(K, NewQ);
         DatK.DelLink(I);
         DatK.AddQ(J, NewQ);
         MxQHeap.PushHeap(TFltIntIntTr(NewQ, TMath::Mn(J, K), TMath::Mx(J, K)));
       }
     }
     DatJ.DegFrac += DatI.DegFrac; }
     if (DatJ.NIdQH.Empty()) { CmtyQH.DelKey(J); } // isolated community (done)
     CmtyQH.DelKey(I);
     return true;
   }