SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
biasedrandomwalk.cpp
Go to the documentation of this file.
1 #include "stdafx.h"
2 #include "Snap.h"
3 #include "biasedrandomwalk.h"
4 
5 //Preprocess alias sampling method
6 void GetNodeAlias(TFltV& PTblV, TIntVFltVPr& NTTable) {
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 }
49 
50 //Get random element using alias sampling method
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 }
57 
58 void PreprocessNode (PWNet& InNet, const double& ParamP, const double& ParamQ,
59  TWNet::TNodeI NI, int64& NCnt, const bool& Verbose) {
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 }
95 
96 //Preprocess transition probabilities for each path t->v->x
97 void PreprocessTransitionProbs(PWNet& InNet, const double& ParamP, const double& ParamQ, const bool& Verbose) {
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 }
118 
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 }
129 
130 //Simulates a random walk
131 void SimulateWalk(PWNet& InNet, int64 StartNId, const int& WalkLen, TRnd& Rnd, TIntV& WalkV) {
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 }
THash< TInt, TIntVFltVPr > TIntIntVFltVPrH
Definition: hash.h:625
int64 AliasDrawInt(TIntVFltVPr &NTTable, TRnd &Rnd)
Definition: dt.h:11
const TVal1 & GetVal1() const
Definition: ds.h:60
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal2 & GetVal2() const
Definition: ds.h:61
int64 PredictMemoryRequirements(PWNet &InNet)
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
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
Node iterator. Only forward iteration (operator++) is supported.
Definition: network.h:537
void SimulateWalk(PWNet &InNet, int64 StartNId, const int &WalkLen, TRnd &Rnd, TIntV &WalkV)
Simulates one walk and writes it into Walk vector.
Definition: dt.h:1137
Definition: ds.h:32
int AddKey(const TKey &Key)
Definition: hash.h:373
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)
Definition: hash.h:97
double GetUniDev()
Definition: dt.h:30
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 cal...
TVal1 Val1
Definition: ds.h:34
TVec< TInt > TIntV
Definition: ds.h:1594
TVal2 Val2
Definition: ds.h:35
Definition: bd.h:196
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
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
void DelLast()
Removes the last element of the vector.
Definition: ds.h:665
int GetId() const
Returns ID of the current node.
Definition: network.h:553
const TNodeData & GetDat() const
Definition: network.h:581