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
biasedrandomwalk.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs

typedef TNodeEDatNet< TIntIntVFltVPrH, TFltTWNet
 
typedef TPt< TWNetPWNet
 

Functions

void PreprocessTransitionProbs (PWNet &InNet, const double &ParamP, const double &ParamQ, const bool &verbose)
 Preprocesses transition probabilities for random walks. Has to be called once before SimulateWalk calls. More...
 
void SimulateWalk (PWNet &InNet, int64 StartNId, const int &WalkLen, TRnd &Rnd, TIntV &Walk)
 Simulates one walk and writes it into Walk vector. More...
 
int64 PredictMemoryRequirements (PWNet &InNet)
 

Typedef Documentation

typedef TPt<TWNet> PWNet

Definition at line 5 of file biasedrandomwalk.h.

Definition at line 4 of file biasedrandomwalk.h.

Function Documentation

int64 PredictMemoryRequirements ( PWNet InNet)

Definition at line 119 of file biasedrandomwalk.cpp.

References TNodeEDatNet< TNodeData, TEdgeData >::TNodeI::GetOutDeg().

119  {
120  int64 MemNeeded = 0;
121  for (TWNet::TNodeI NI = InNet->BegNI(); NI < InNet->EndNI(); NI++) {
122  for (int64 i = 0; i < NI.GetOutDeg(); i++) {
123  TWNet::TNodeI CurrI = InNet->GetNI(NI.GetNbrNId(i));
124  MemNeeded += CurrI.GetOutDeg()*(sizeof(TInt) + sizeof(TFlt));
125  }
126  }
127  return MemNeeded;
128 }
Definition: dt.h:1386
int GetOutDeg() const
Returns out-degree of the current node.
Definition: network.h:559
Node iterator. Only forward iteration (operator++) is supported.
Definition: network.h:537
Definition: dt.h:1137
long long int64
Definition: bd.h:27

Here is the call graph for this function:

void PreprocessTransitionProbs ( PWNet InNet,
const double &  ParamP,
const double &  ParamQ,
const bool &  verbose 
)

Preprocesses transition probabilities for random walks. Has to be called once before SimulateWalk calls.

Definition at line 97 of file biasedrandomwalk.cpp.

References TVec< TVal, TSizeTy >::Add(), TNodeEDatNet< TNodeData, TEdgeData >::TNodeI::GetDat(), TNodeEDatNet< TNodeData, TEdgeData >::TNodeI::GetOutDeg(), TVec< TVal, TSizeTy >::Len(), and PreprocessNode().

Referenced by node2vec().

97  {
98  for (TWNet::TNodeI NI = InNet->BegNI(); NI < InNet->EndNI(); NI++) {
99  InNet->SetNDat(NI.GetId(),TIntIntVFltVPrH());
100  }
101  for (TWNet::TNodeI NI = InNet->BegNI(); NI < InNet->EndNI(); NI++) {
102  for (int64 i = 0; i < NI.GetOutDeg(); i++) { //allocating space in advance to avoid issues with multithreading
103  TWNet::TNodeI CurrI = InNet->GetNI(NI.GetNbrNId(i));
104  CurrI.GetDat().AddDat(NI.GetId(),TPair<TIntV,TFltV>(TIntV(CurrI.GetOutDeg()),TFltV(CurrI.GetOutDeg())));
105  }
106  }
107  int64 NCnt = 0;
108  TIntV NIds;
109  for (TWNet::TNodeI NI = InNet->BegNI(); NI < InNet->EndNI(); NI++) {
110  NIds.Add(NI.GetId());
111  }
112 #pragma omp parallel for schedule(dynamic)
113  for (int64 i = 0; i < NIds.Len(); i++) {
114  PreprocessNode(InNet, ParamP, ParamQ, InNet->GetNI(NIds[i]), NCnt, Verbose);
115  }
116  if(Verbose){ printf("\n"); }
117 }
THash< TInt, TIntVFltVPr > TIntIntVFltVPrH
Definition: hash.h:625
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
int GetOutDeg() const
Returns out-degree of the current node.
Definition: network.h:559
Node iterator. Only forward iteration (operator++) is supported.
Definition: network.h:537
Definition: ds.h:32
TVec< TFlt > TFltV
Definition: ds.h:1596
long long int64
Definition: bd.h:27
void PreprocessNode(PWNet &InNet, const double &ParamP, const double &ParamQ, TWNet::TNodeI NI, int64 &NCnt, const bool &Verbose)
TVec< TInt > TIntV
Definition: ds.h:1594
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
const TNodeData & GetDat() const
Definition: network.h:581

Here is the call graph for this function:

Here is the caller graph for this function:

void SimulateWalk ( PWNet InNet,
int64  StartNId,
const int &  WalkLen,
TRnd Rnd,
TIntV Walk 
)

Simulates one walk and writes it into Walk vector.

Definition at line 131 of file biasedrandomwalk.cpp.

References TVec< TVal, TSizeTy >::Add(), AliasDrawInt(), TRnd::GetUniDevInt(), TVec< TVal, TSizeTy >::Last(), TVec< TVal, TSizeTy >::LastLast(), and TVec< TVal, TSizeTy >::Len().

Referenced by node2vec().

131  {
132  WalkV.Add(StartNId);
133  if (WalkLen == 1) { return; }
134  if (InNet->GetNI(StartNId).GetOutDeg() == 0) { return; }
135  WalkV.Add(InNet->GetNI(StartNId).GetNbrNId(Rnd.GetUniDevInt(InNet->GetNI(StartNId).GetOutDeg())));
136  while (WalkV.Len() < WalkLen) {
137  int64 Dst = WalkV.Last();
138  int64 Src = WalkV.LastLast();
139  if (InNet->GetNI(Dst).GetOutDeg() == 0) { return; }
140  int64 Next = AliasDrawInt(InNet->GetNDat(Dst).GetDat(Src),Rnd);
141  WalkV.Add(InNet->GetNI(Dst).GetNbrNId(Next));
142  }
143 }
int64 AliasDrawInt(TIntVFltVPr &NTTable, TRnd &Rnd)
long long int64
Definition: bd.h:27
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39

Here is the call graph for this function:

Here is the caller graph for this function: