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
TAGMFastUtil Class Reference

Utility functions for BigCLAM, Coda. More...

#include <agmfast.h>

Static Public Member Functions

template<class PGraph >
static double GetConductance (const PGraph &Graph, const TIntSet &CmtyS, const int Edges)
 
template<class PGraph >
static void GenHoldOutPairs (const PGraph &G, TVec< TIntSet > &HoldOutSet, double HOFrac, TRnd &Rnd)
 
template<class PGraph >
static void GetNbhCom (const PGraph &Graph, const int NID, TIntSet &NBCmtyS)
 
template<class PGraph >
static void GetNIdPhiV (const PGraph &G, TFltIntPrV &NIdPhiV)
 

Detailed Description

Utility functions for BigCLAM, Coda.

Definition at line 126 of file agmfast.h.

Member Function Documentation

template<class PGraph >
static void TAGMFastUtil::GenHoldOutPairs ( const PGraph &  G,
TVec< TIntSet > &  HoldOutSet,
double  HOFrac,
TRnd Rnd 
)
inlinestatic

Definition at line 159 of file agmfast.h.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Gen(), TRnd::GetUniDevInt(), gfDirected, HasGraphFlag, and TMath::Round().

Referenced by TCoda::FindComsByCV(), and TCoda::SetHoldOut().

159  {
160  TIntPrV EdgeV(G->GetEdges(), 0);
161  for (typename PGraph::TObj::TEdgeI EI = G->BegEI(); EI < G->EndEI(); EI++) {
162  EdgeV.Add(TIntPr(EI.GetSrcNId(), EI.GetDstNId()));
163  }
164  EdgeV.Shuffle(Rnd);
165 
166  const bool GraphType = HasGraphFlag(typename PGraph::TObj, gfDirected);
167  HoldOutSet.Gen(G->GetNodes());
168  int HOTotal = int(HOFrac * G->GetNodes() * (G->GetNodes() - 1) / 2.0);
169  if (GraphType) { HOTotal *= 2;}
170  int HOCnt = 0;
171  int HOEdges = (int) TMath::Round(HOFrac * G->GetEdges());
172  printf("holding out %d edges...\n", HOEdges);
173  for (int he = 0; he < (int) HOEdges; he++) {
174  HoldOutSet[EdgeV[he].Val1].AddKey(EdgeV[he].Val2);
175  if (! GraphType) { HoldOutSet[EdgeV[he].Val2].AddKey(EdgeV[he].Val1); }
176  HOCnt++;
177  }
178  printf("%d Edges hold out\n", HOCnt);
179  while(HOCnt++ < HOTotal) {
180  int SrcNID = Rnd.GetUniDevInt(G->GetNodes());
181  int DstNID = Rnd.GetUniDevInt(G->GetNodes());
182  if (SrcNID == DstNID) { continue; }
183  HoldOutSet[SrcNID].AddKey(DstNID);
184  if (! GraphType) { HoldOutSet[DstNID].AddKey(SrcNID); }
185  }
186  }
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
static double Round(const double &Val)
Definition: xmath.h:16
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

Here is the caller graph for this function:

template<class PGraph >
static double TAGMFastUtil::GetConductance ( const PGraph &  Graph,
const TIntSet CmtyS,
const int  Edges 
)
inlinestatic

Definition at line 131 of file agmfast.h.

References gfDirected, HasGraphFlag, THashSet< TKey, THashFunc >::IsKey(), and THashSet< TKey, THashFunc >::Len().

Referenced by GetNIdPhiV().

131  {
132  const bool GraphType = HasGraphFlag(typename PGraph::TObj, gfDirected);
133  int Edges2;
134  if (GraphType) { Edges2 = Edges >= 0 ? Edges : Graph->GetEdges(); }
135  else { Edges2 = Edges >= 0 ? 2 * Edges : Graph->GetEdges(); }
136  int Vol = 0, Cut = 0;
137  double Phi = 0.0;
138  for (int i = 0; i < CmtyS.Len(); i++) {
139  if (! Graph->IsNode(CmtyS[i])) { continue; }
140  typename PGraph::TObj::TNodeI NI = Graph->GetNI(CmtyS[i]);
141  for (int e = 0; e < NI.GetOutDeg(); e++) {
142  if (! CmtyS.IsKey(NI.GetOutNId(e))) { Cut += 1; }
143  }
144  Vol += NI.GetOutDeg();
145  }
146  // get conductance
147  if (Vol != Edges2) {
148  if (2 * Vol > Edges2) { Phi = Cut / double (Edges2 - Vol); }
149  else if (Vol == 0) { Phi = 0.0; }
150  else { Phi = Cut / double(Vol); }
151  } else {
152  if (Vol == Edges2) { Phi = 1.0; }
153  }
154  return Phi;
155 }
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
int Len() const
Definition: shash.h:1121

Here is the call graph for this function:

Here is the caller graph for this function:

template<class PGraph >
static void TAGMFastUtil::GetNbhCom ( const PGraph &  Graph,
const int  NID,
TIntSet NBCmtyS 
)
inlinestatic

Definition at line 189 of file agmfast.h.

References THashSet< TKey, THashFunc >::AddKey(), and THashSet< TKey, THashFunc >::Gen().

189  {
190  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NID);
191  NBCmtyS.Gen(NI.GetDeg());
192  NBCmtyS.AddKey(NID);
193  for (int e = 0; e < NI.GetDeg(); e++) {
194  NBCmtyS.AddKey(NI.GetNbrNId(e));
195  }
196  }
void Gen(const int &ExpectVals)
Definition: shash.h:1115
int AddKey(const TKey &Key)
Definition: shash.h:1254

Here is the call graph for this function:

template<class PGraph >
static void TAGMFastUtil::GetNIdPhiV ( const PGraph &  G,
TFltIntPrV NIdPhiV 
)
inlinestatic

Definition at line 198 of file agmfast.h.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Gen(), GetConductance(), and TExeTm::GetTmStr().

198  {
199  NIdPhiV.Gen(G->GetNodes(), 0);
200  const int Edges = G->GetEdges();
201  TExeTm RunTm;
202  //compute conductance of neighborhood community
203  for (typename PGraph::TObj::TNodeI NI = G->BegNI(); NI < G->EndNI(); NI++) {
204  TIntSet NBCmty(NI.GetDeg() + 1);
205  double Phi;
206  if (NI.GetDeg() < 5) { //do not include nodes with too few degree
207  Phi = 1.0;
208  } else {
209  TAGMFastUtil::GetNbhCom<PGraph>(G, NI.GetId(), NBCmty);
210  Phi = TAGMFastUtil::GetConductance(G, NBCmty, Edges);
211  }
212  NIdPhiV.Add(TFltIntPr(Phi, NI.GetId()));
213  }
214  printf("conductance computation completed [%s]\n", RunTm.GetTmStr());
215  fflush(stdout);
216  }
TPair< TFlt, TInt > TFltIntPr
Definition: ds.h:97
Definition: tm.h:355
static double GetConductance(const PGraph &Graph, const TIntSet &CmtyS, const int Edges)
Definition: agmfast.h:131
const char * GetTmStr() const
Definition: tm.h:370
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

Here is the call graph for this function:


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