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
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: