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.cpp File Reference
#include "stdafx.h"
#include "Snap.h"
#include "biasedrandomwalk.h"
Include dependency graph for biasedrandomwalk.cpp:

Go to the source code of this file.

Functions

void GetNodeAlias (TFltV &PTblV, TIntVFltVPr &NTTable)
 
int64 AliasDrawInt (TIntVFltVPr &NTTable, TRnd &Rnd)
 
void PreprocessNode (PWNet &InNet, const double &ParamP, const double &ParamQ, TWNet::TNodeI NI, int64 &NCnt, const bool &Verbose)
 
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...
 
int64 PredictMemoryRequirements (PWNet &InNet)
 
void SimulateWalk (PWNet &InNet, int64 StartNId, const int &WalkLen, TRnd &Rnd, TIntV &WalkV)
 Simulates one walk and writes it into Walk vector. More...
 

Function Documentation

int64 AliasDrawInt ( TIntVFltVPr NTTable,
TRnd Rnd 
)

Definition at line 51 of file biasedrandomwalk.cpp.

References TRnd::GetUniDev(), TPair< TVal1, TVal2 >::GetVal1(), and TPair< TVal1, TVal2 >::GetVal2().

Referenced by SimulateWalk().

51  {
52  int64 N = NTTable.GetVal1().Len();
53  TInt X = static_cast<int64>(Rnd.GetUniDev()*N);
54  double Y = Rnd.GetUniDev();
55  return Y < NTTable.GetVal2()[X] ? X : NTTable.GetVal1()[X];
56 }
const TVal1 & GetVal1() const
Definition: ds.h:60
const TVal2 & GetVal2() const
Definition: ds.h:61
Definition: dt.h:1137
long long int64
Definition: bd.h:27
double GetUniDev()
Definition: dt.h:30

Here is the call graph for this function:

Here is the caller graph for this function:

void GetNodeAlias ( TFltV PTblV,
TIntVFltVPr NTTable 
)

Definition at line 6 of file biasedrandomwalk.cpp.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::DelLast(), TVec< TVal, TSizeTy >::Last(), TVec< TVal, TSizeTy >::Len(), TPair< TVal1, TVal2 >::Val1, and TPair< TVal1, TVal2 >::Val2.

Referenced by PreprocessNode().

6  {
7  int64 N = PTblV.Len();
8  TIntV& KTbl = NTTable.Val1;
9  TFltV& UTbl = NTTable.Val2;
10  for (int64 i = 0; i < N; i++) {
11  KTbl[i]=0;
12  UTbl[i]=0;
13  }
14  TIntV UnderV;
15  TIntV OverV;
16  for (int64 i = 0; i < N; i++) {
17  UTbl[i] = PTblV[i]*N;
18  if (UTbl[i] < 1) {
19  UnderV.Add(i);
20  } else {
21  OverV.Add(i);
22  }
23  }
24  while (UnderV.Len() > 0 && OverV.Len() > 0) {
25  int64 Small = UnderV.Last();
26  int64 Large = OverV.Last();
27  UnderV.DelLast();
28  OverV.DelLast();
29  KTbl[Small] = Large;
30  UTbl[Large] = UTbl[Large] + UTbl[Small] - 1;
31  if (UTbl[Large] < 1) {
32  UnderV.Add(Large);
33  } else {
34  OverV.Add(Large);
35  }
36  }
37  while(UnderV.Len() > 0){
38  int64 curr = UnderV.Last();
39  UnderV.DelLast();
40  UTbl[curr]=1;
41  }
42  while(OverV.Len() > 0){
43  int64 curr = OverV.Last();
44  OverV.DelLast();
45  UTbl[curr]=1;
46  }
47 
48 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
long long int64
Definition: bd.h:27
TVal1 Val1
Definition: ds.h:34
TVal2 Val2
Definition: ds.h:35
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
void DelLast()
Removes the last element of the vector.
Definition: ds.h:665

Here is the call graph for this function:

Here is the caller graph for this function:

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 PreprocessNode ( PWNet InNet,
const double &  ParamP,
const double &  ParamQ,
TWNet::TNodeI  NI,
int64 NCnt,
const bool &  Verbose 
)

Definition at line 58 of file biasedrandomwalk.cpp.

References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddKey(), TNodeEDatNet< TNodeData, TEdgeData >::TNodeI::GetDat(), TNodeEDatNet< TNodeData, TEdgeData >::TNodeI::GetId(), TNodeEDatNet< TNodeData, TEdgeData >::TNodeI::GetNbrNId(), GetNodeAlias(), TNodeEDatNet< TNodeData, TEdgeData >::TNodeI::GetOutDeg(), and THash< TKey, TDat, THashFunc >::IsKey().

Referenced by PreprocessTransitionProbs().

59  {
60  if (Verbose && NCnt%100 == 0) {
61  printf("\rPreprocessing progress: %.2lf%% ",(double)NCnt*100/(double)(InNet->GetNodes()));fflush(stdout);
62  }
63  //for node t
64  THash <TInt, TBool> NbrH; //Neighbors of t
65  for (int64 i = 0; i < NI.GetOutDeg(); i++) {
66  NbrH.AddKey(NI.GetNbrNId(i));
67  }
68  for (int64 i = 0; i < NI.GetOutDeg(); i++) {
69  TWNet::TNodeI CurrI = InNet->GetNI(NI.GetNbrNId(i)); //for each node v
70  double Psum = 0;
71  TFltV PTable; //Probability distribution table
72  for (int64 j = 0; j < CurrI.GetOutDeg(); j++) { //for each node x
73  int64 FId = CurrI.GetNbrNId(j);
74  TFlt Weight;
75  if (!(InNet->GetEDat(CurrI.GetId(), FId, Weight))){ continue; }
76  if (FId==NI.GetId()) {
77  PTable.Add(Weight / ParamP);
78  Psum += Weight / ParamP;
79  } else if (NbrH.IsKey(FId)) {
80  PTable.Add(Weight);
81  Psum += Weight;
82  } else {
83  PTable.Add(Weight / ParamQ);
84  Psum += Weight / ParamQ;
85  }
86  }
87  //Normalizing table
88  for (int64 j = 0; j < CurrI.GetOutDeg(); j++) {
89  PTable[j] /= Psum;
90  }
91  GetNodeAlias(PTable,CurrI.GetDat().GetDat(NI.GetId()));
92  }
93  NCnt++;
94 }
Definition: dt.h:1386
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: network.h:571
void GetNodeAlias(TFltV &PTblV, TIntVFltVPr &NTTable)
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
int AddKey(const TKey &Key)
Definition: hash.h:373
long long int64
Definition: bd.h:27
Definition: hash.h:97
TPt< TTable > PTable
Definition: table.h:141
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int GetId() const
Returns ID of the current node.
Definition: network.h:553
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 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 WalkV 
)

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)
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal & LastLast() const
Returns a reference to the one before last element of the vector.
Definition: ds.h:585
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
long long int64
Definition: bd.h:27
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: