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

                                                                                                     {
    TIntPrV EdgeV(G->GetEdges(), 0);
    for (typename PGraph::TObj::TEdgeI EI = G->BegEI(); EI < G->EndEI(); EI++) {
      EdgeV.Add(TIntPr(EI.GetSrcNId(), EI.GetDstNId()));
    }
    EdgeV.Shuffle(Rnd);

    const bool GraphType = HasGraphFlag(typename PGraph::TObj, gfDirected);
    HoldOutSet.Gen(G->GetNodes());
    int HOTotal = int(HOFrac * G->GetNodes() * (G->GetNodes() - 1) / 2.0);
    if (GraphType) { HOTotal *= 2;}
    int HOCnt = 0;
    int HOEdges = (int) TMath::Round(HOFrac * G->GetEdges());
    printf("holding out %d edges...\n", HOEdges);
    for (int he = 0; he < (int) HOEdges; he++) {
      HoldOutSet[EdgeV[he].Val1].AddKey(EdgeV[he].Val2);
      if (! GraphType) { HoldOutSet[EdgeV[he].Val2].AddKey(EdgeV[he].Val1); }
      HOCnt++;
    }
    printf("%d Edges hold out\n", HOCnt);
    while(HOCnt++ < HOTotal) {
      int SrcNID = Rnd.GetUniDevInt(G->GetNodes());
      int DstNID = Rnd.GetUniDevInt(G->GetNodes());
      if (SrcNID == DstNID) { continue; }
      HoldOutSet[SrcNID].AddKey(DstNID);
      if (! GraphType) { HoldOutSet[DstNID].AddKey(SrcNID); }
    }
  }

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

                                                                                         {
  const bool GraphType = HasGraphFlag(typename PGraph::TObj, gfDirected);
  int Edges2;
  if (GraphType) { Edges2 = Edges >= 0 ? Edges : Graph->GetEdges(); }
  else { Edges2 = Edges >= 0 ? 2 * Edges : Graph->GetEdges(); }
  int Vol = 0,  Cut = 0; 
  double Phi = 0.0;
  for (int i = 0; i < CmtyS.Len(); i++) {
    if (! Graph->IsNode(CmtyS[i])) { continue; }
    typename PGraph::TObj::TNodeI  NI = Graph->GetNI(CmtyS[i]);
    for (int e = 0; e < NI.GetOutDeg(); e++) {
      if (! CmtyS.IsKey(NI.GetOutNId(e))) { Cut += 1; }
    }
    Vol += NI.GetOutDeg();
  }
  // get conductance
  if (Vol != Edges2) {
    if (2 * Vol > Edges2) { Phi = Cut / double (Edges2 - Vol); }
    else if (Vol == 0) { Phi = 0.0; }
    else { Phi = Cut / double(Vol); }
  } else {
    if (Vol == Edges2) { Phi = 1.0; }
  }
  return Phi;
}

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

                                                                              {
    typename PGraph::TObj::TNodeI NI = Graph->GetNI(NID);
    NBCmtyS.Gen(NI.GetDeg());
    NBCmtyS.AddKey(NID);
    for (int e = 0; e < NI.GetDeg(); e++) {
      NBCmtyS.AddKey(NI.GetNbrNId(e));
    }
  }

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

                                                               {
    NIdPhiV.Gen(G->GetNodes(), 0);
    const int Edges = G->GetEdges();
    TExeTm RunTm;
    //compute conductance of neighborhood community
    for (typename PGraph::TObj::TNodeI NI = G->BegNI(); NI < G->EndNI(); NI++) {
      TIntSet NBCmty(NI.GetDeg() + 1);
      double Phi;
      if (NI.GetDeg() < 5) { //do not include nodes with too few degree
        Phi = 1.0; 
      } else {
        TAGMFastUtil::GetNbhCom<PGraph>(G, NI.GetId(), NBCmty);
        Phi = TAGMFastUtil::GetConductance(G, NBCmty, Edges);
      }
      NIdPhiV.Add(TFltIntPr(Phi, NI.GetId()));
    }
    printf("conductance computation completed [%s]\n", RunTm.GetTmStr());
    fflush(stdout);
  }

Here is the call graph for this function:

---

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

• snap-adv/agmfast.h