SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
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 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().

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

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

1428  {
1429  TCNMQMatrix QMatrix(Graph);
1430  // maximize modularity
1431  while (QMatrix.MergeBestQ()) {}
1432  // reconstruct communities
1433  THash<TInt, TIntV> IdCmtyH;
1434  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
1435  IdCmtyH.AddDat(QMatrix.CmtyIdUF.Find(NI.GetId())).Add(NI.GetId());
1436  }
1437  CmtyV.Gen(IdCmtyH.Len());
1438  for (int j = 0; j < IdCmtyH.Len(); j++) {
1439  CmtyV[j].NIdV.Swap(IdCmtyH[j]);
1440  }
1441  return QMatrix.Q;
1442  }
TCNMQMatrix(const PUNGraph &Graph)
Definition: cmty.cpp:1356
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 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().

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

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

1360  {
1361  const double M = 0.5 / Graph->GetEdges(); // 1/2m
1362  Q = 0.0;
1363  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
1364  CmtyIdUF.Add(NI.GetId());
1365  const int OutDeg = NI.GetOutDeg();
1366  if (OutDeg == 0) { continue; }
1367  TCmtyDat& Dat = CmtyQH.AddDat(NI.GetId(), TCmtyDat(M * OutDeg, OutDeg));
1368  for (int e = 0; e < NI.GetOutDeg(); e++) {
1369  const int DstNId = NI.GetOutNId(e);
1370  const double DstMod = 2 * M * (1.0 - OutDeg * Graph->GetNI(DstNId).GetOutDeg() * M);
1371  Dat.AddQ(DstNId, DstMod);
1372  }
1373  Q += -1.0*TMath::Sqr(OutDeg*M);
1374  if (NI.GetId() < Dat.GetMxQNId()) {
1375  MxQHeap.Add(TFltIntIntTr(Dat.GetMxQ(), NI.GetId(), Dat.GetMxQNId()));
1376  }
1377  }
1378  MxQHeap.MakeHeap();
1379  }
int Add(const int &Key)
Adds an element Key to the structure.
Definition: gbase.h:241
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:1352
TTriple< TFlt, TInt, TInt > TFltIntIntTr
Definition: ds.h:182
THash< TInt, TCmtyDat > CmtyQH
Definition: cmty.cpp:1351

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

1391  {
1392  const TFltIntIntTr TopQ = FindMxQEdge();
1393  if (TopQ.Val1 <= 0.0) { return false; }
1394  // joint communities
1395  const int I = TopQ.Val3;
1396  const int J = TopQ.Val2;
1397  CmtyIdUF.Union(I, J); // join
1398  Q += TopQ.Val1;
1399  TCmtyDat& DatJ = CmtyQH.GetDat(J);
1400  { TCmtyDat& DatI = CmtyQH.GetDat(I);
1401  DatI.DelLink(J); DatJ.DelLink(I);
1402  for (int i = -1; DatJ.NIdQH.FNextKeyId(i); ) {
1403  const int K = DatJ.NIdQH.GetKey(i);
1404  TCmtyDat& DatK = CmtyQH.GetDat(K);
1405  double NewQ = DatJ.NIdQH[i];
1406  if (DatI.NIdQH.IsKey(K)) { NewQ = NewQ + DatI.NIdQH.GetDat(K); DatK.DelLink(I); } // K connected to I and J
1407  else { NewQ = NewQ - 2 * DatI.DegFrac*DatK.DegFrac; } // K connected to J not I
1408  DatJ.AddQ(K, NewQ);
1409  DatK.AddQ(J, NewQ);
1410  MxQHeap.PushHeap(TFltIntIntTr(NewQ, TMath::Mn(J, K), TMath::Mx(J, K)));
1411  }
1412  for (int i = -1; DatI.NIdQH.FNextKeyId(i); ) {
1413  const int K = DatI.NIdQH.GetKey(i);
1414  if (!DatJ.NIdQH.IsKey(K)) { // K connected to I not J
1415  TCmtyDat& DatK = CmtyQH.GetDat(K);
1416  const double NewQ = DatI.NIdQH[i] - 2 * DatJ.DegFrac*DatK.DegFrac;
1417  DatJ.AddQ(K, NewQ);
1418  DatK.DelLink(I);
1419  DatK.AddQ(J, NewQ);
1420  MxQHeap.PushHeap(TFltIntIntTr(NewQ, TMath::Mn(J, K), TMath::Mx(J, K)));
1421  }
1422  }
1423  DatJ.DegFrac += DatI.DegFrac; }
1424  if (DatJ.NIdQH.Empty()) { CmtyQH.DelKey(J); } // isolated community (done)
1425  CmtyQH.DelKey(I);
1426  return true;
1427  }
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:1380
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:1352
TTriple< TFlt, TInt, TInt > TFltIntIntTr
Definition: ds.h:182
TVal3 Val3
Definition: ds.h:134
THash< TInt, TCmtyDat > CmtyQH
Definition: cmty.cpp:1351

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

Referenced by CmtyCMN(), Init(), and MergeBestQ().

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

Definition at line 1351 of file cmty.cpp.

Referenced by FindMxQEdge(), Init(), and MergeBestQ().

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

Definition at line 1352 of file cmty.cpp.

Referenced by FindMxQEdge(), Init(), and MergeBestQ().

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

Definition at line 1354 of file cmty.cpp.

Referenced by CmtyCMN(), Init(), and MergeBestQ().


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