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 84 of file cmty.cpp.

Constructor & Destructor Documentation

TSnap::TSnapDetail::TCNMQMatrix::TCNMQMatrix ( const PUNGraph & Graph ) [inline]

Definition at line 109 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
	)		`[inline, static]`

Definition at line 177 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 130 of file cmty.cpp.

References CmtyQH, THeap< TVal, TCmp >::Empty(), THash< TKey, TDat, THashFunc >::GetDat(), TSnap::TSnapDetail::TCNMQMatrix::TCmtyDat::GetMxQ(), THash< TKey, TDat, THashFunc >::IsKey(), MxQHeap, THeap< TVal, TCmp >::PopHeap(), 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 call graph for this function:

Here is the caller graph for this function:

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

Definition at line 111 of file cmty.cpp.

References TUnionFind::Add(), THeap< TVal, TCmp >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), 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(), THeap< TVal, TCmp >::MakeHeap(), 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 140 of file cmty.cpp.

References TSnap::TSnapDetail::TCNMQMatrix::TCmtyDat::AddQ(), CmtyIdUF, CmtyQH, TSnap::TSnapDetail::TCNMQMatrix::TCmtyDat::DegFrac, THash< TKey, TDat, THashFunc >::DelKey(), 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, THeap< TVal, TCmp >::PushHeap(), 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;
  }