TSnap::TSnapDetail::TCNMQMatrix Class Reference

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

Constructor & Destructor Documentation

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

inline

Definition at line 217 of file cmty.cpp.

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

Member Function Documentation

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

inlinestatic

Definition at line 285 of file cmty.cpp.

                                                               {
    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;
  }

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

inline

Definition at line 238 of file cmty.cpp.

                             {
    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);
  }

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

inline

Definition at line 219 of file cmty.cpp.

                                   {
    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();
  }

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

inline

Definition at line 248 of file cmty.cpp.

                    {
    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;
  }

Member Data Documentation

TUnionFind TSnap::TSnapDetail::TCNMQMatrix::CmtyIdUF

private

Definition at line 214 of file cmty.cpp.

THash<TInt, TCmtyDat> TSnap::TSnapDetail::TCNMQMatrix::CmtyQH

private

Definition at line 212 of file cmty.cpp.

THeap<TFltIntIntTr> TSnap::TSnapDetail::TCNMQMatrix::MxQHeap

private

Definition at line 213 of file cmty.cpp.

double TSnap::TSnapDetail::TCNMQMatrix::Q

private

Definition at line 215 of file cmty.cpp.

---

The documentation for this class was generated from the following file:

• snap-core/cmty.cpp