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, 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.

                                                    {
  int64 N = NTTable.GetVal1().Len();
  TInt X = static_cast<int64>(Rnd.GetUniDev()*N);
  double Y = Rnd.GetUniDev();
  return Y < NTTable.GetVal2()[X] ? X : NTTable.GetVal1()[X];
}

void GetNodeAlias	(	TFltV &	PTblV,
		TIntVFltVPr &	NTTable
	)

Definition at line 6 of file biasedrandomwalk.cpp.

                                                      {
  int64 N = PTblV.Len();
  TIntV& KTbl = NTTable.Val1;
  TFltV& UTbl = NTTable.Val2;
  for (int64 i = 0; i < N; i++) {
    KTbl[i]=0;
    UTbl[i]=0;
  }
  TIntV UnderV;
  TIntV OverV;
  for (int64 i = 0; i < N; i++) {
    UTbl[i] = PTblV[i]*N;
    if (UTbl[i] < 1) {
      UnderV.Add(i);
    } else {
      OverV.Add(i);
    }
  }
  while (UnderV.Len() > 0 && OverV.Len() > 0) {
    int64 Small = UnderV.Last();
    int64 Large = OverV.Last();
    UnderV.DelLast();
    OverV.DelLast();
    KTbl[Small] = Large;
    UTbl[Large] = UTbl[Large] + UTbl[Small] - 1;
    if (UTbl[Large] < 1) {
      UnderV.Add(Large);
    } else {
      OverV.Add(Large);
    }
  }
  while(UnderV.Len() > 0){
    int64 curr = UnderV.Last();
    UnderV.DelLast();
    UTbl[curr]=1;
  }
  while(OverV.Len() > 0){
    int64 curr = OverV.Last();
    OverV.DelLast();
    UTbl[curr]=1;
  }

}

int64 PredictMemoryRequirements

(

PWNet &

InNet

)

Definition at line 119 of file biasedrandomwalk.cpp.

                                              {
  int64 MemNeeded = 0;
  for (TWNet::TNodeI NI = InNet->BegNI(); NI < InNet->EndNI(); NI++) {
    for (int64 i = 0; i < NI.GetOutDeg(); i++) {
      TWNet::TNodeI CurrI = InNet->GetNI(NI.GetNbrNId(i));
      MemNeeded += CurrI.GetOutDeg()*(sizeof(TInt) + sizeof(TFlt));
    }
  }
  return MemNeeded;
}

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.

                                                   {
  if (Verbose && NCnt%100 == 0) {
    printf("\rPreprocessing progress: %.2lf%% ",(double)NCnt*100/(double)(InNet->GetNodes()));fflush(stdout);
  }
  //for node t
  THash <TInt, TBool> NbrH;                                    //Neighbors of t
  for (int64 i = 0; i < NI.GetOutDeg(); i++) {
    NbrH.AddKey(NI.GetNbrNId(i));
  } 
  for (int64 i = 0; i < NI.GetOutDeg(); i++) {
    TWNet::TNodeI CurrI = InNet->GetNI(NI.GetNbrNId(i));      //for each node v
    double Psum = 0;
    TFltV PTable;                              //Probability distribution table
    for (int64 j = 0; j < CurrI.GetOutDeg(); j++) {           //for each node x
      int64 FId = CurrI.GetNbrNId(j);
      TFlt Weight;
      if (!(InNet->GetEDat(CurrI.GetId(), FId, Weight))){ continue; }
      if (FId==NI.GetId()) {
        PTable.Add(Weight / ParamP);
        Psum += Weight / ParamP;
      } else if (NbrH.IsKey(FId)) {
        PTable.Add(Weight);
        Psum += Weight;
      } else {
        PTable.Add(Weight / ParamQ);
        Psum += Weight / ParamQ;
      }
    }
    //Normalizing table
    for (int64 j = 0; j < CurrI.GetOutDeg(); j++) {
      PTable[j] /= Psum;
    }
    GetNodeAlias(PTable,CurrI.GetDat().GetDat(NI.GetId()));
  }
  NCnt++;
}

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.

                                                                                                              {
  for (TWNet::TNodeI NI = InNet->BegNI(); NI < InNet->EndNI(); NI++) {
    InNet->SetNDat(NI.GetId(),TIntIntVFltVPrH());
  }
  for (TWNet::TNodeI NI = InNet->BegNI(); NI < InNet->EndNI(); NI++) {
    for (int64 i = 0; i < NI.GetOutDeg(); i++) {                    //allocating space in advance to avoid issues with multithreading
      TWNet::TNodeI CurrI = InNet->GetNI(NI.GetNbrNId(i));
      CurrI.GetDat().AddDat(NI.GetId(),TPair<TIntV,TFltV>(TIntV(CurrI.GetOutDeg()),TFltV(CurrI.GetOutDeg())));
    }
  }
  int64 NCnt = 0;
  TIntV NIds;
  for (TWNet::TNodeI NI = InNet->BegNI(); NI < InNet->EndNI(); NI++) {
    NIds.Add(NI.GetId());
  }
#pragma omp parallel for schedule(dynamic)
  for (int64 i = 0; i < NIds.Len(); i++) {
    PreprocessNode(InNet, ParamP, ParamQ, InNet->GetNI(NIds[i]), NCnt, Verbose);
  }
  if(Verbose){ printf("\n"); }
}

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.

                                                                                             {
  WalkV.Add(StartNId);
  if (WalkLen == 1) { return; }
  if (InNet->GetNI(StartNId).GetOutDeg() == 0) { return; }
  WalkV.Add(InNet->GetNI(StartNId).GetNbrNId(Rnd.GetUniDevInt(InNet->GetNI(StartNId).GetOutDeg())));
  while (WalkV.Len() < WalkLen) {
    int64 Dst = WalkV.Last();
    int64 Src = WalkV.LastLast();
    if (InNet->GetNI(Dst).GetOutDeg() == 0) { return; }
    int64 Next = AliasDrawInt(InNet->GetNDat(Dst).GetDat(Src),Rnd);
    WalkV.Add(InNet->GetNI(Dst).GetNbrNId(Next));
  }
}