SNAP Library 4.1, Developer 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
n2v.cpp
Go to the documentation of this file.
1 #include "stdafx.h"
2 #include "n2v.h"
3 
4 void node2vec(PWNet& InNet, const double& ParamP, const double& ParamQ,
5  const int& Dimensions, const int& WalkLen, const int& NumWalks,
6  const int& WinSize, const int& Iter, const bool& Verbose,
7  const bool& OutputWalks, TVVec<TInt, int64>& WalksVV,
8  TIntFltVH& EmbeddingsHV) {
9  //Preprocess transition probabilities
10  PreprocessTransitionProbs(InNet, ParamP, ParamQ, Verbose);
11  TIntV NIdsV;
12  for (TWNet::TNodeI NI = InNet->BegNI(); NI < InNet->EndNI(); NI++) {
13  NIdsV.Add(NI.GetId());
14  }
15  //Generate random walks
16  int64 AllWalks = (int64)NumWalks * NIdsV.Len();
17  WalksVV = TVVec<TInt, int64>(AllWalks,WalkLen);
18  TRnd Rnd(time(NULL));
19  int64 WalksDone = 0;
20  for (int64 i = 0; i < NumWalks; i++) {
21  NIdsV.Shuffle(Rnd);
22 #pragma omp parallel for schedule(dynamic)
23  for (int64 j = 0; j < NIdsV.Len(); j++) {
24  if ( Verbose && WalksDone%10000 == 0 ) {
25  printf("\rWalking Progress: %.2lf%%",(double)WalksDone*100/(double)AllWalks);fflush(stdout);
26  }
27  TIntV WalkV;
28  SimulateWalk(InNet, NIdsV[j], WalkLen, Rnd, WalkV);
29  for (int64 k = 0; k < WalkV.Len(); k++) {
30  WalksVV.PutXY(i*NIdsV.Len()+j, k, WalkV[k]);
31  }
32  WalksDone++;
33  }
34  }
35  if (Verbose) {
36  printf("\n");
37  fflush(stdout);
38  }
39  //Learning embeddings
40  if (!OutputWalks) {
41  LearnEmbeddings(WalksVV, Dimensions, WinSize, Iter, Verbose, EmbeddingsHV);
42  }
43 }
44 
45 void node2vec(PWNet& InNet, const double& ParamP, const double& ParamQ,
46  const int& Dimensions, const int& WalkLen, const int& NumWalks,
47  const int& WinSize, const int& Iter, const bool& Verbose,
48  TIntFltVH& EmbeddingsHV) {
49  TVVec <TInt, int64> WalksVV;
50  bool OutputWalks = 0;
51  node2vec(InNet, ParamP, ParamQ, Dimensions, WalkLen, NumWalks, WinSize,
52  Iter, Verbose, OutputWalks, WalksVV, EmbeddingsHV);
53 }
54 
55 
56 void node2vec(const PNGraph& InNet, const double& ParamP, const double& ParamQ,
57  const int& Dimensions, const int& WalkLen, const int& NumWalks,
58  const int& WinSize, const int& Iter, const bool& Verbose,
59  const bool& OutputWalks, TVVec<TInt, int64>& WalksVV,
60  TIntFltVH& EmbeddingsHV) {
61  PWNet NewNet = PWNet::New();
62  for (TNGraph::TEdgeI EI = InNet->BegEI(); EI < InNet->EndEI(); EI++) {
63  if (!NewNet->IsNode(EI.GetSrcNId())) { NewNet->AddNode(EI.GetSrcNId()); }
64  if (!NewNet->IsNode(EI.GetDstNId())) { NewNet->AddNode(EI.GetDstNId()); }
65  NewNet->AddEdge(EI.GetSrcNId(), EI.GetDstNId(), 1.0);
66  }
67  node2vec(NewNet, ParamP, ParamQ, Dimensions, WalkLen, NumWalks, WinSize, Iter,
68  Verbose, OutputWalks, WalksVV, EmbeddingsHV);
69 }
70 
71 void node2vec(const PNGraph& InNet, const double& ParamP, const double& ParamQ,
72  const int& Dimensions, const int& WalkLen, const int& NumWalks,
73  const int& WinSize, const int& Iter, const bool& Verbose,
74  TIntFltVH& EmbeddingsHV) {
75  TVVec <TInt, int64> WalksVV;
76  bool OutputWalks = 0;
77  node2vec(InNet, ParamP, ParamQ, Dimensions, WalkLen, NumWalks, WinSize,
78  Iter, Verbose, OutputWalks, WalksVV, EmbeddingsHV);
79 }
80 
81 void node2vec(const PNEANet& InNet, const double& ParamP, const double& ParamQ,
82  const int& Dimensions, const int& WalkLen, const int& NumWalks,
83  const int& WinSize, const int& Iter, const bool& Verbose,
84  const bool& OutputWalks, TVVec<TInt, int64>& WalksVV,
85  TIntFltVH& EmbeddingsHV) {
86  PWNet NewNet = PWNet::New();
87  for (TNEANet::TEdgeI EI = InNet->BegEI(); EI < InNet->EndEI(); EI++) {
88  if (!NewNet->IsNode(EI.GetSrcNId())) { NewNet->AddNode(EI.GetSrcNId()); }
89  if (!NewNet->IsNode(EI.GetDstNId())) { NewNet->AddNode(EI.GetDstNId()); }
90  NewNet->AddEdge(EI.GetSrcNId(), EI.GetDstNId(), InNet->GetFltAttrDatE(EI,"weight"));
91  }
92  node2vec(NewNet, ParamP, ParamQ, Dimensions, WalkLen, NumWalks, WinSize, Iter,
93  Verbose, OutputWalks, WalksVV, EmbeddingsHV);
94 }
95 
96 void node2vec(const PNEANet& InNet, const double& ParamP, const double& ParamQ,
97  const int& Dimensions, const int& WalkLen, const int& NumWalks,
98  const int& WinSize, const int& Iter, const bool& Verbose,
99  TIntFltVH& EmbeddingsHV) {
100  TVVec <TInt, int64> WalksVV;
101  bool OutputWalks = 0;
102  node2vec(InNet, ParamP, ParamQ, Dimensions, WalkLen, NumWalks, WinSize,
103  Iter, Verbose, OutputWalks, WalksVV, EmbeddingsHV);
104 }
105 
Definition: dt.h:11
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:588
static TPt New()
Definition: bd.h:479
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:586
void LearnEmbeddings(TVVec< TInt, int64 > &WalksVV, const int &Dimensions, const int &WinSize, const int &Iter, const bool &Verbose, TIntFltVH &EmbeddingsHV)
Learns embeddings using SGD, Skip-gram with negative sampling.
Definition: word2vec.cpp:160
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:426
Definition: ds.h:2223
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.
Edge iterator. Only forward iteration (operator++) is supported.
Definition: network.h:1867
void PutXY(const TSizeTy &X, const TSizeTy &Y, const TVal &Val)
Definition: ds.h:2267
long long int64
Definition: bd.h:27
Definition: hash.h:97
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1335
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...
void node2vec(PWNet &InNet, const double &ParamP, const double &ParamQ, const int &Dimensions, const int &WalkLen, const int &NumWalks, const int &WinSize, const int &Iter, const bool &Verbose, const bool &OutputWalks, TVVec< TInt, int64 > &WalksVV, TIntFltVH &EmbeddingsHV)
Calculates node2vec feature representation for nodes and writes them into EmbeddinsHV, see http://arxiv.org/pdf/1607.00653v1.pdf.
Definition: n2v.cpp:4
Definition: bd.h:196
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602