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
TSnap::TSnapDetail::TCNMQMatrix Class Reference
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, TCmtyDatCmtyQH
 
THeap< TFltIntIntTrMxQHeap
 
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 1326 of file cmty.cpp.

Constructor & Destructor Documentation

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

Definition at line 1358 of file cmty.cpp.

References Init().

1358  : CmtyQH(Graph->GetNodes()),
1359  MxQHeap(Graph->GetNodes()), CmtyIdUF(Graph->GetNodes()) {
1360  Init(Graph);
1361  }
THeap< TFltIntIntTr > MxQHeap
Definition: cmty.cpp:1354
void Init(const PUNGraph &Graph)
Definition: cmty.cpp:1362
THash< TInt, TCmtyDat > CmtyQH
Definition: cmty.cpp:1353

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 1430 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().

1430  {
1431  TCNMQMatrix QMatrix(Graph);
1432  // maximize modularity
1433  while (QMatrix.MergeBestQ()) {}
1434  // reconstruct communities
1435  THash<TInt, TIntV> IdCmtyH;
1436  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
1437  IdCmtyH.AddDat(QMatrix.CmtyIdUF.Find(NI.GetId())).Add(NI.GetId());
1438  }
1439  CmtyV.Gen(IdCmtyH.Len());
1440  for (int j = 0; j < IdCmtyH.Len(); j++) {
1441  CmtyV[j].NIdV.Swap(IdCmtyH[j]);
1442  }
1443  return QMatrix.Q;
1444  }
TCNMQMatrix(const PUNGraph &Graph)
Definition: cmty.cpp:1358
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

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

References THeap< TVal, TCmp >::Empty(), THash< TKey, TDat, THashFunc >::GetDat(), TSnap::TSnapDetail::TCNMQMatrix::TCmtyDat::GetMxQ(), THash< TKey, TDat, THashFunc >::IsKey(), THeap< TVal, TCmp >::PopHeap(), TTriple< TVal1, TVal2, TVal3 >::Val1, TTriple< TVal1, TVal2, TVal3 >::Val2, and TTriple< TVal1, TVal2, TVal3 >::Val3.

Referenced by MergeBestQ().

1382  {
1383  while (true) {
1384  if (MxQHeap.Empty()) { break; }
1385  const TFltIntIntTr TopQ = MxQHeap.PopHeap();
1386  if (!CmtyQH.IsKey(TopQ.Val2) || !CmtyQH.IsKey(TopQ.Val3)) { continue; }
1387  if (TopQ.Val1 != CmtyQH.GetDat(TopQ.Val2).GetMxQ() && TopQ.Val1 != CmtyQH.GetDat(TopQ.Val3).GetMxQ()) { continue; }
1388  return TopQ;
1389  }
1390  return TFltIntIntTr(-1, -1, -1);
1391  }
Definition: ds.h:130
TVal1 Val1
Definition: ds.h:132
TVal2 Val2
Definition: ds.h:133
THeap< TFltIntIntTr > MxQHeap
Definition: cmty.cpp:1354
TTriple< TFlt, TInt, TInt > TFltIntIntTr
Definition: ds.h:182
TVal3 Val3
Definition: ds.h:134
THash< TInt, TCmtyDat > CmtyQH
Definition: cmty.cpp:1353

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

References TUnionFind::Add(), THeap< TVal, TCmp >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), TSnap::TSnapDetail::TCNMQMatrix::TCmtyDat::AddQ(), TUNGraph::BegNI(), TUNGraph::EndNI(), TUNGraph::GetEdges(), TSnap::TSnapDetail::TCNMQMatrix::TCmtyDat::GetMxQ(), TSnap::TSnapDetail::TCNMQMatrix::TCmtyDat::GetMxQNId(), TUNGraph::GetNI(), TUNGraph::TNodeI::GetOutDeg(), THeap< TVal, TCmp >::MakeHeap(), and TMath::Sqr().

Referenced by TCNMQMatrix().

1362  {
1363  const double M = 0.5 / Graph->GetEdges(); // 1/2m
1364  Q = 0.0;
1365  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
1366  CmtyIdUF.Add(NI.GetId());
1367  const int OutDeg = NI.GetOutDeg();
1368  if (OutDeg == 0) { continue; }
1369  TCmtyDat& Dat = CmtyQH.AddDat(NI.GetId(), TCmtyDat(M * OutDeg, OutDeg));
1370  for (int e = 0; e < NI.GetOutDeg(); e++) {
1371  const int DstNId = NI.GetOutNId(e);
1372  const double DstMod = 2 * M * (1.0 - OutDeg * Graph->GetNI(DstNId).GetOutDeg() * M);
1373  Dat.AddQ(DstNId, DstMod);
1374  }
1375  Q += -1.0*TMath::Sqr(OutDeg*M);
1376  if (NI.GetId() < Dat.GetMxQNId()) {
1377  MxQHeap.Add(TFltIntIntTr(Dat.GetMxQ(), NI.GetId(), Dat.GetMxQNId()));
1378  }
1379  }
1380  MxQHeap.MakeHeap();
1381  }
int Add(const int &Key)
Adds an element Key to the structure.
Definition: gbase.h:254
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
static double Sqr(const double &x)
Definition: xmath.h:12
THeap< TFltIntIntTr > MxQHeap
Definition: cmty.cpp:1354
TTriple< TFlt, TInt, TInt > TFltIntIntTr
Definition: ds.h:182
THash< TInt, TCmtyDat > CmtyQH
Definition: cmty.cpp:1353

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

References TSnap::TSnapDetail::TCNMQMatrix::TCmtyDat::AddQ(), 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(), TSnap::TSnapDetail::TCNMQMatrix::TCmtyDat::NIdQH, THeap< TVal, TCmp >::PushHeap(), TUnionFind::Union(), TTriple< TVal1, TVal2, TVal3 >::Val1, TTriple< TVal1, TVal2, TVal3 >::Val2, and TTriple< TVal1, TVal2, TVal3 >::Val3.

Referenced by CmtyCMN().

1393  {
1394  const TFltIntIntTr TopQ = FindMxQEdge();
1395  if (TopQ.Val1 <= 0.0) { return false; }
1396  // joint communities
1397  const int I = TopQ.Val3;
1398  const int J = TopQ.Val2;
1399  CmtyIdUF.Union(I, J); // join
1400  Q += TopQ.Val1;
1401  TCmtyDat& DatJ = CmtyQH.GetDat(J);
1402  { TCmtyDat& DatI = CmtyQH.GetDat(I);
1403  DatI.DelLink(J); DatJ.DelLink(I);
1404  for (int i = -1; DatJ.NIdQH.FNextKeyId(i); ) {
1405  const int K = DatJ.NIdQH.GetKey(i);
1406  TCmtyDat& DatK = CmtyQH.GetDat(K);
1407  double NewQ = DatJ.NIdQH[i];
1408  if (DatI.NIdQH.IsKey(K)) { NewQ = NewQ + DatI.NIdQH.GetDat(K); DatK.DelLink(I); } // K connected to I and J
1409  else { NewQ = NewQ - 2 * DatI.DegFrac*DatK.DegFrac; } // K connected to J not I
1410  DatJ.AddQ(K, NewQ);
1411  DatK.AddQ(J, NewQ);
1412  MxQHeap.PushHeap(TFltIntIntTr(NewQ, TMath::Mn(J, K), TMath::Mx(J, K)));
1413  }
1414  for (int i = -1; DatI.NIdQH.FNextKeyId(i); ) {
1415  const int K = DatI.NIdQH.GetKey(i);
1416  if (!DatJ.NIdQH.IsKey(K)) { // K connected to I not J
1417  TCmtyDat& DatK = CmtyQH.GetDat(K);
1418  const double NewQ = DatI.NIdQH[i] - 2 * DatJ.DegFrac*DatK.DegFrac;
1419  DatJ.AddQ(K, NewQ);
1420  DatK.DelLink(I);
1421  DatK.AddQ(J, NewQ);
1422  MxQHeap.PushHeap(TFltIntIntTr(NewQ, TMath::Mn(J, K), TMath::Mx(J, K)));
1423  }
1424  }
1425  DatJ.DegFrac += DatI.DegFrac; }
1426  if (DatJ.NIdQH.Empty()) { CmtyQH.DelKey(J); } // isolated community (done)
1427  CmtyQH.DelKey(I);
1428  return true;
1429  }
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
void Union(const int &Key1, const int &Key2)
Merges sets with elements Key1 and Key2.
Definition: gbase.cpp:40
TFltIntIntTr FindMxQEdge()
Definition: cmty.cpp:1382
Definition: ds.h:130
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TVal1 Val1
Definition: ds.h:132
TVal2 Val2
Definition: ds.h:133
THeap< TFltIntIntTr > MxQHeap
Definition: cmty.cpp:1354
TTriple< TFlt, TInt, TInt > TFltIntIntTr
Definition: ds.h:182
TVal3 Val3
Definition: ds.h:134
THash< TInt, TCmtyDat > CmtyQH
Definition: cmty.cpp:1353

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

TUnionFind TSnap::TSnapDetail::TCNMQMatrix::CmtyIdUF
private

Definition at line 1355 of file cmty.cpp.

Referenced by CmtyCMN().

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

Definition at line 1353 of file cmty.cpp.

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

Definition at line 1354 of file cmty.cpp.

double TSnap::TSnapDetail::TCNMQMatrix::Q
private

Definition at line 1356 of file cmty.cpp.

Referenced by CmtyCMN().


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