SNAP Library 4.1, User Reference  2018-07-26 16:30:42
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
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:1383
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:1134
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