SNAP Library 4.0, User Reference  2017-07-27 13:18:06
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 File Reference
#include "stdafx.h"
#include "Snap.h"
#include "biasedrandomwalk.h"

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, double &ParamP, double &ParamQ, TWNet::TNodeI NI, int64 &NCnt, bool &Verbose)
 
void PreprocessTransitionProbs (PWNet &InNet, double &ParamP, double &ParamQ, 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, 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 40 of file biasedrandomwalk.cpp.

40  {
41  int64 N = NTTable.GetVal1().Len();
42  TInt X = static_cast<int64>(Rnd.GetUniDev()*N);
43  double Y = Rnd.GetUniDev();
44  return Y < NTTable.GetVal2()[X] ? X : NTTable.GetVal1()[X];
45 }
const TVal1 & GetVal1() const
Definition: ds.h:60
const TVal2 & GetVal2() const
Definition: ds.h:61
Definition: dt.h:1134
long long int64
Definition: bd.h:27
double GetUniDev()
Definition: dt.h:30
void GetNodeAlias ( TFltV PTblV,
TIntVFltVPr NTTable 
)

Definition at line 6 of file biasedrandomwalk.cpp.

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 }
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
int64 PredictMemoryRequirements ( PWNet InNet)

Definition at line 108 of file biasedrandomwalk.cpp.

108  {
109  int64 MemNeeded = 0;
110  for (TWNet::TNodeI NI = InNet->BegNI(); NI < InNet->EndNI(); NI++) {
111  for (int64 i = 0; i < NI.GetOutDeg(); i++) {
112  TWNet::TNodeI CurrI = InNet->GetNI(NI.GetNbrNId(i));
113  MemNeeded += CurrI.GetOutDeg()*(sizeof(TInt) + sizeof(TFlt));
114  }
115  }
116  return MemNeeded;
117 }
Definition: dt.h:1383
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:1134
long long int64
Definition: bd.h:27
void PreprocessNode ( PWNet InNet,
double &  ParamP,
double &  ParamQ,
TWNet::TNodeI  NI,
int64 NCnt,
bool &  Verbose 
)

Definition at line 47 of file biasedrandomwalk.cpp.

48  {
49  if (Verbose && NCnt%100 == 0) {
50  printf("\rPreprocessing progress: %.2lf%% ",(double)NCnt*100/(double)(InNet->GetNodes()));fflush(stdout);
51  }
52  //for node t
53  THash <TInt, TBool> NbrH; //Neighbors of t
54  for (int64 i = 0; i < NI.GetOutDeg(); i++) {
55  NbrH.AddKey(NI.GetNbrNId(i));
56  }
57  for (int64 i = 0; i < NI.GetOutDeg(); i++) {
58  TWNet::TNodeI CurrI = InNet->GetNI(NI.GetNbrNId(i)); //for each node v
59  double Psum = 0;
60  TFltV PTable; //Probability distribution table
61  for (int64 j = 0; j < CurrI.GetOutDeg(); j++) { //for each node x
62  int64 FId = CurrI.GetNbrNId(j);
63  TFlt Weight;
64  if (!(InNet->GetEDat(CurrI.GetId(), FId, Weight))){ continue; }
65  if (FId==NI.GetId()) {
66  PTable.Add(Weight / ParamP);
67  Psum += Weight / ParamP;
68  } else if (NbrH.IsKey(FId)) {
69  PTable.Add(Weight);
70  Psum += Weight;
71  } else {
72  PTable.Add(Weight / ParamQ);
73  Psum += Weight / ParamQ;
74  }
75  }
76  //Normalizing table
77  for (int64 j = 0; j < CurrI.GetOutDeg(); j++) {
78  PTable[j] /= Psum;
79  }
80  GetNodeAlias(PTable,CurrI.GetDat().GetDat(NI.GetId()));
81  }
82  NCnt++;
83 }
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
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
void PreprocessTransitionProbs ( PWNet InNet,
double &  ParamP,
double &  ParamQ,
bool &  Verbose 
)

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

Definition at line 86 of file biasedrandomwalk.cpp.

86  {
87  for (TWNet::TNodeI NI = InNet->BegNI(); NI < InNet->EndNI(); NI++) {
88  InNet->SetNDat(NI.GetId(),TIntIntVFltVPrH());
89  }
90  for (TWNet::TNodeI NI = InNet->BegNI(); NI < InNet->EndNI(); NI++) {
91  for (int64 i = 0; i < NI.GetOutDeg(); i++) { //allocating space in advance to avoid issues with multithreading
92  TWNet::TNodeI CurrI = InNet->GetNI(NI.GetNbrNId(i));
93  CurrI.GetDat().AddDat(NI.GetId(),TPair<TIntV,TFltV>(TIntV(CurrI.GetOutDeg()),TFltV(CurrI.GetOutDeg())));
94  }
95  }
96  int64 NCnt = 0;
97  TIntV NIds;
98  for (TWNet::TNodeI NI = InNet->BegNI(); NI < InNet->EndNI(); NI++) {
99  NIds.Add(NI.GetId());
100  }
101 #pragma omp parallel for schedule(dynamic)
102  for (int64 i = 0; i < NIds.Len(); i++) {
103  PreprocessNode(InNet, ParamP, ParamQ, InNet->GetNI(NIds[i]), NCnt, Verbose);
104  }
105  if(Verbose){ printf("\n"); }
106 }
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
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
void PreprocessNode(PWNet &InNet, double &ParamP, double &ParamQ, TWNet::TNodeI NI, int64 &NCnt, bool &Verbose)
const TNodeData & GetDat() const
Definition: network.h:581
void SimulateWalk ( PWNet InNet,
int64  StartNId,
int &  WalkLen,
TRnd Rnd,
TIntV WalkV 
)

Simulates one walk and writes it into Walk vector.

Definition at line 120 of file biasedrandomwalk.cpp.

120  {
121  WalkV.Add(StartNId);
122  if (WalkLen == 1) { return; }
123  if (InNet->GetNI(StartNId).GetOutDeg() == 0) { return; }
124  WalkV.Add(InNet->GetNI(StartNId).GetNbrNId(Rnd.GetUniDevInt(InNet->GetNI(StartNId).GetOutDeg())));
125  while (WalkV.Len() < WalkLen) {
126  int64 Dst = WalkV.Last();
127  int64 Src = WalkV.LastLast();
128  if (InNet->GetNI(Dst).GetOutDeg() == 0) { return; }
129  int64 Next = AliasDrawInt(InNet->GetNDat(Dst).GetDat(Src),Rnd);
130  WalkV.Add(InNet->GetNI(Dst).GetNbrNId(Next));
131  }
132 }
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