SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
rolx.cpp File Reference
#include "stdafx.h"
#include "Snap.h"
#include "rolx.h"
Include dependency graph for rolx.cpp:

Go to the source code of this file.

Functions

void PrintFeatures (const TIntFtrH &Features)
 Prints all nodes' feature. More...
 
TIntFtrH CreateEmptyFeatures (const PUNGraph Graph)
 Creates an empty node-feature mapping of all nodes in the given graph. More...
 
TIntFtrH CreateEmptyFeatures (const TIntFtrH &Features)
 Creates an empty node-feature mapping of all nodes from an existing mapping. More...
 
int GetNumFeatures (const TIntFtrH &Features)
 Gets number of features from the node-feature mapping. More...
 
TFtr GetNthFeature (const TIntFtrH &Features, const int N)
 Gets the n-th feature of all nodes. More...
 
TIntFtrH ExtractFeatures (const PUNGraph Graph)
 Performs feature extraction, the first step of RolX. More...
 
void AddNeighborhoodFeatures (const PUNGraph Graph, TIntFtrH &Features)
 Adds neighborhood features (local + egonet) to the node-feature mapping. More...
 
void AddRecursiveFeatures (const PUNGraph Graph, TIntFtrH &Features)
 Adds recursive features to the node-feature mapping. More...
 
void AddLocalFeatures (const PUNGraph Graph, TIntFtrH &Features)
 Adds local features to the node-feature mapping. More...
 
void AddEgonetFeatures (const PUNGraph Graph, TIntFtrH &Features)
 Adds egonet features to the node-feature mapping. More...
 
TIntFtrH GenerateRecursiveFeatures (const PUNGraph Graph, const TIntFtrH &CurrFeatures)
 Generates recursive features out of current features. More...
 
TIntFtrH PruneRecursiveFeatures (const PUNGraph Graph, const TIntFtrH &Features, const TIntFtrH &NewFeatures, const int SimilarityThreshold)
 Prunes recursive features. More...
 
void AppendFeatures (TIntFtrH &DstFeatures, const TIntFtrH &SrcFeatures, const int ColIdx)
 Appends all src features to dst features. More...
 
TIntFtrH CalcVerticalLogBinning (const TIntFtrH &Features, const float BinFraction)
 Calculates vertical logarithmic binning features from the given features. More...
 
PUNGraph BuildFeatureGraph (const TIntFtrH &LogBinFeatures, const int SimilarityThreshold)
 Builds s-friend graph given similarity threshold. More...
 
TIntFtrH SummarizeConnectedComponents (const PUNGraph FeatureGraph, const TIntFtrH &Features, const TIntFtrH &NewFeatures)
 Summarizes s-friend graph and return retained features. More...
 
TVec< TIntGetNIdSorted (const TIntFtrH &Features, const int Idx)
 Sorts the Idx-th feature, return the list of corresponding node ID. More...
 
void AssignBinValue (const TVec< TInt > &SortedNId, const float BinFraction, TIntFtrH &LogBinFeatures)
 Assigns logarithmic binning value to features. More...
 
bool IsSimilarFeature (const TFtr &F1, const TFtr &F2, const int SimilarityThreshold)
 Whether the two features are similar, given similarity threshold. More...
 
TFltVV ConvertFeatureToMatrix (const TIntFtrH &Features, const TIntIntH &NodeIdMtxIdxH)
 Converts node-feature mapping to matrix. (i, j): i-th node, j-th feature. More...
 
void PrintMatrix (const TFltVV &Matrix)
 Prints feature matrix to stdout. More...
 
TFltVV CreateRandMatrix (const int XDim, const int YDim)
 Creates a random matrix with specified dimension. More...
 
bool FltIsZero (const TFlt Number)
 Whether the float is zero. More...
 
void CalcNonNegativeFactorization (const TFltVV &V, const int NumRoles, TFltVV &W, TFltVV &H, const double Threshold)
 Performs non-negative factorization V = WH. 2nd dim of W == number of roles. More...
 
TFlt CalcDescriptionLength (const TFltVV &V, const TFltVV &G, const TFltVV &F)
 Calculates the description length L = M + E. More...
 
TIntIntH CreateNodeIdMtxIdxHash (const TIntFtrH &Features)
 Creates the mapping of <node ID, matrix index>. More...
 
int GetMtxIdx (const TInt NodeId, const TIntIntH &NodeIdMtxIdxH)
 Gets matrix index of the node ID. More...
 
int GetNodeId (const TInt MtxId, const TIntIntH &NodeIdMtxIdxH)
 
TIntIntH FindRoles (const TFltVV &G, const TIntIntH &NodeIdMtxIdxH)
 Gets matrix index of the node ID. More...
 
void PlotRoles (const PUNGraph Graph, const TIntIntH &Roles)
 Plots found roles on a picture (.png). More...
 
void PrintRoles (const TIntIntH &Roles)
 Prints found roles on stdout. More...
 
void FPrintMatrix (const TFltVV &Matrix, const TStr &Path)
 Prints feature matrix to file. More...
 
void FPrintNodeMappings (const TIntIntH &NodeIdMtxIdxH, const TStr &Path)
 Prints node mappings to file, feature line -> node ID. More...
 
void FPrintRoles (const TIntIntH &Roles, const TStr &Path)
 Prints found roles to file. More...
 

Function Documentation

void AddEgonetFeatures ( const PUNGraph  Graph,
TIntFtrH Features 
)

Adds egonet features to the node-feature mapping.

Definition at line 87 of file rolx.cpp.

References THash< TKey, TDat, THashFunc >::GetDat(), and TSnap::GetEgonet().

Referenced by AddNeighborhoodFeatures().

87  {
88  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
89  int NId = NI.GetId();
90  int ArndEdges;
91  PUNGraph Egonet = TSnap::GetEgonet(Graph, NId, ArndEdges);
92  Features.GetDat(NId).Add(Egonet->GetEdges());
93  Features.GetDat(NId).Add(ArndEdges);
94  }
95 }
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
PUNGraph GetEgonet(const PUNGraph &Graph, const int CtrNId, int &ArndEdges)
Returns the egonet of node CtrNId as center in undirected graph Graph. And returns number of edges ar...
Definition: subgraph.cpp:82
Definition: bd.h:196

Here is the call graph for this function:

Here is the caller graph for this function:

void AddLocalFeatures ( const PUNGraph  Graph,
TIntFtrH Features 
)

Adds local features to the node-feature mapping.

Definition at line 81 of file rolx.cpp.

References THash< TKey, TDat, THashFunc >::GetDat().

Referenced by AddNeighborhoodFeatures().

81  {
82  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
83  Features.GetDat(TInt(NI.GetId())).Add(NI.GetInDeg());
84  }
85 }
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
Definition: dt.h:1137

Here is the call graph for this function:

Here is the caller graph for this function:

void AddNeighborhoodFeatures ( const PUNGraph  Graph,
TIntFtrH Features 
)

Adds neighborhood features (local + egonet) to the node-feature mapping.

Definition at line 57 of file rolx.cpp.

References AddEgonetFeatures(), and AddLocalFeatures().

Referenced by ExtractFeatures().

57  {
58  AddLocalFeatures(Graph, Features);
59  printf("finish local features\n");
60  AddEgonetFeatures(Graph, Features);
61  printf("finish egonet features\n");
62 }
void AddLocalFeatures(const PUNGraph Graph, TIntFtrH &Features)
Adds local features to the node-feature mapping.
Definition: rolx.cpp:81
void AddEgonetFeatures(const PUNGraph Graph, TIntFtrH &Features)
Adds egonet features to the node-feature mapping.
Definition: rolx.cpp:87

Here is the call graph for this function:

Here is the caller graph for this function:

void AddRecursiveFeatures ( const PUNGraph  Graph,
TIntFtrH Features 
)

Adds recursive features to the node-feature mapping.

Definition at line 64 of file rolx.cpp.

References AppendFeatures(), GenerateRecursiveFeatures(), GetNumFeatures(), and PruneRecursiveFeatures().

Referenced by ExtractFeatures().

64  {
65  int SimilarityThreshold = 0;
66  TIntFtrH RetainedFeatures = Features;
67  while (true) {
68  TIntFtrH NewFeatures = GenerateRecursiveFeatures(Graph, RetainedFeatures);
69  RetainedFeatures = PruneRecursiveFeatures(Graph, Features, NewFeatures,
70  SimilarityThreshold);
71  if (0 == GetNumFeatures(RetainedFeatures)) {
72  break;
73  }
74  AppendFeatures(Features, RetainedFeatures);
75  ++SimilarityThreshold;
76  printf("recursion %d: ", SimilarityThreshold);
77  printf("current feature number %d\n", GetNumFeatures(Features));
78  }
79 }
int GetNumFeatures(const TIntFtrH &Features)
Gets number of features from the node-feature mapping.
Definition: rolx.cpp:35
TIntFtrH PruneRecursiveFeatures(const PUNGraph Graph, const TIntFtrH &Features, const TIntFtrH &NewFeatures, const int SimilarityThreshold)
Prunes recursive features.
Definition: rolx.cpp:119
TIntFtrH GenerateRecursiveFeatures(const PUNGraph Graph, const TIntFtrH &CurrFeatures)
Generates recursive features out of current features.
Definition: rolx.cpp:97
Definition: hash.h:97
void AppendFeatures(TIntFtrH &DstFeatures, const TIntFtrH &SrcFeatures, const int ColIdx)
Appends all src features to dst features.
Definition: rolx.cpp:131

Here is the call graph for this function:

Here is the caller graph for this function:

void AppendFeatures ( TIntFtrH DstFeatures,
const TIntFtrH SrcFeatures,
const int  ColIdx 
)

Appends all src features to dst features.

Definition at line 131 of file rolx.cpp.

References THash< TKey, TDat, THashFunc >::BegI(), THash< TKey, TDat, THashFunc >::EndI(), THash< TKey, TDat, THashFunc >::GetDat(), TVec< TVal, TSizeTy >::GetDat(), and TVec< TVal, TSizeTy >::Len().

Referenced by AddRecursiveFeatures(), PruneRecursiveFeatures(), and SummarizeConnectedComponents().

132  {
133  for (TIntFtrH::TIter HI = SrcFeatures.BegI();
134  HI < SrcFeatures.EndI();
135  HI++) {
136  const TFtr& Feature = HI.GetDat();
137  if (ColIdx >= 0) {
138  DstFeatures.GetDat(HI.GetKey()).Add(Feature[ColIdx]);
139  } else {
140  for (int i = 0; i < Feature.Len(); ++i) {
141  DstFeatures.GetDat(HI.GetKey()).Add(Feature[i]);
142  }
143  }
144  }
145 }
TIter BegI() const
Definition: hash.h:213
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TIter EndI() const
Definition: hash.h:218
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:838

Here is the call graph for this function:

Here is the caller graph for this function:

void AssignBinValue ( const TVec< TInt > &  SortedNId,
const float  BinFraction,
TIntFtrH LogBinFeatures 
)

Assigns logarithmic binning value to features.

Definition at line 212 of file rolx.cpp.

References THash< TKey, TDat, THashFunc >::GetDat(), and THash< TKey, TDat, THashFunc >::Len().

Referenced by CalcVerticalLogBinning().

213  {
214  int NumNodes = LogBinFeatures.Len();
215  int NumAssigned = 0;
216  int BinValue = 0;
217  while (NumAssigned < NumNodes) {
218  int NumToAssign = ceil(BinFraction * (NumNodes - NumAssigned));
219  for (int i = NumAssigned; i < NumAssigned + NumToAssign; ++i) {
220  int NId = SortedNId[i];
221  LogBinFeatures.GetDat(NId).Add(BinValue);
222  }
223  NumAssigned += NumToAssign;
224  ++BinValue;
225  }
226 }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
int Len() const
Definition: hash.h:228

Here is the call graph for this function:

Here is the caller graph for this function:

PUNGraph BuildFeatureGraph ( const TIntFtrH LogBinFeatures,
const int  SimilarityThreshold 
)

Builds s-friend graph given similarity threshold.

Definition at line 158 of file rolx.cpp.

References GetNthFeature(), GetNumFeatures(), IsSimilarFeature(), and TPt< TRec >::New().

Referenced by PruneRecursiveFeatures().

159  {
160  PUNGraph FeatureGraph = PUNGraph::New();
161  const int NumFeatures = GetNumFeatures(LogBinFeatures);
162  for (int i = 0; i < NumFeatures; ++i) {
163  FeatureGraph->AddNode(i);
164  }
165  for (int i = 0; i < NumFeatures; ++i) {
166  TFtr IthFeature = GetNthFeature(LogBinFeatures, i);
167  for (int j = i + 1; j < NumFeatures; ++j) {
168  TFtr JthFeature = GetNthFeature(LogBinFeatures, j);
169  if (IsSimilarFeature(IthFeature, JthFeature, SimilarityThreshold) &&
170  !FeatureGraph->IsEdge(i, j)) {
171  FeatureGraph->AddEdge(i, j);
172  }
173  }
174  }
175  return FeatureGraph;
176 }
int GetNumFeatures(const TIntFtrH &Features)
Gets number of features from the node-feature mapping.
Definition: rolx.cpp:35
static TPt New()
Definition: bd.h:479
TFtr GetNthFeature(const TIntFtrH &Features, const int N)
Gets the n-th feature of all nodes.
Definition: rolx.cpp:39
bool IsSimilarFeature(const TFtr &F1, const TFtr &F2, const int SimilarityThreshold)
Whether the two features are similar, given similarity threshold.
Definition: rolx.cpp:228
Definition: bd.h:196

Here is the call graph for this function:

Here is the caller graph for this function:

TFlt CalcDescriptionLength ( const TFltVV V,
const TFltVV G,
const TFltVV F 
)

Calculates the description length L = M + E.

Definition at line 352 of file rolx.cpp.

References FltIsZero(), TVVec< TVal, TSizeTy >::GetXDim(), TVVec< TVal, TSizeTy >::GetYDim(), TMath::Log(), and TLinAlg::Multiply().

353  {
354  int B = 64;
355  int M = B * V.GetYDim() * (V.GetXDim() + F.GetYDim());
356  TFlt E = 0;
357  TFltVV GF(G.GetXDim(), F.GetYDim());
358  TLinAlg::Multiply(G, F, GF);
359  for (int i = 0; i < V.GetXDim(); ++i) {
360  for (int j = 0; j < V.GetYDim(); ++j) {
361  TFlt ValueV = V(i, j);
362  TFlt ValueGF = GF(i, j);
363  if (FltIsZero(ValueV)) {
364  E += ValueGF;
365  } else if (!FltIsZero(ValueGF)) {
366  E += ValueV * TMath::Log(ValueV / ValueGF) - ValueV + ValueGF;
367  }
368  }
369  }
370  return M + E;
371 }
Definition: dt.h:1386
TSizeTy GetYDim() const
Definition: ds.h:2251
bool FltIsZero(const TFlt Number)
Whether the float is zero.
Definition: rolx.cpp:282
static void Multiply(const TFltVV &A, const TFltV &x, TFltV &y)
Definition: linalg.cpp:428
TSizeTy GetXDim() const
Definition: ds.h:2250
static double Log(const double &Val)
Definition: xmath.h:14

Here is the call graph for this function:

void CalcNonNegativeFactorization ( const TFltVV V,
const int  NumRoles,
TFltVV W,
TFltVV H,
const double  Threshold 
)

Performs non-negative factorization V = WH. 2nd dim of W == number of roles.

Definition at line 286 of file rolx.cpp.

References TFlt::Abs(), TVVec< TVal, TSizeTy >::At(), CreateRandMatrix(), FltIsZero(), TVVec< TVal, TSizeTy >::GetXDim(), TVVec< TVal, TSizeTy >::GetYDim(), TMath::Log(), and TLinAlg::Multiply().

287  {
288  double Cost = 100, NewCost = 0;
289  int NumNodes = V.GetXDim();
290  int NumFeatures = V.GetYDim();
291  W = CreateRandMatrix(NumNodes, NumRoles);
292  H = CreateRandMatrix(NumRoles, NumFeatures);
293  TFltVV NewW(NumNodes, NumRoles);
294  TFltVV NewH(NumRoles, NumFeatures);
295  TFltVV Product(NumNodes, NumFeatures);
296  TFltV Sum(NumRoles);
297  TFltVV *PW = &W, *PH = &H, *PNewW = &NewW, *PNewH = &NewH, *Tmp;
298  //int IterNum = 1;
299  while (TFlt::Abs((NewCost - Cost)/Cost) > Threshold) {
300  TLinAlg::Multiply(*PW, *PH, Product);
301  //converge condition
302  Cost = NewCost;
303  NewCost = 0;
304  for (int i = 0; i < NumNodes; i++) {
305  for (int j = 0; j < NumFeatures; j++) {
306  NewCost += V(i, j) * TMath::Log(Product(i, j)) - Product(i, j);
307  }
308  }
309  // update W
310  for (int i = 0; i < NumNodes; i++) {
311  for (int a = 0; a < NumRoles; a++) {
312  double SumU = 0;
313  for (int u = 0; u < NumFeatures; ++u) {
314  if (!FltIsZero(Product(i, u))) {
315  SumU += V(i, u) / Product(i, u) * PH->At(a, u);
316  }
317  }
318  PNewW->At(i, a) = PW->At(i, a) * SumU;
319  }
320  }
321  for (int i = 0; i < NumRoles; i++) {
322  Sum[i] = 0;
323  }
324  for (int i = 0; i < NumNodes; i++) {
325  for (int j = 0; j < NumRoles; j++) {
326  Sum[j] += PNewW->At(i, j);
327  }
328  }
329  for (int i = 0; i < NumNodes; i++) {
330  for (int j = 0; j < NumRoles; j++) {
331  PNewW->At(i, j) /= Sum[j];
332  }
333  }
334  // update H
335  for (int a = 0; a < NumRoles; a++) {
336  for (int u = 0; u < NumFeatures; u++) {
337  double SumI = 0;
338  for (int i = 0; i < NumNodes; ++i) {
339  if (!FltIsZero(Product(i, u))) {
340  SumI += PW->At(i, a) * V(i, u) / Product(i, u);
341  }
342  }
343  PNewH->At(a, u) = PH->At(a, u) * SumI;
344  }
345  }
346  //printf("iteration %d, cost is %f\n", IterNum++, NewCost);
347  Tmp = PW; PW = PNewW; PNewW = Tmp;
348  Tmp = PH; PH = PNewH; PNewH = Tmp;
349  }
350 }
TSizeTy GetYDim() const
Definition: ds.h:2251
bool FltIsZero(const TFlt Number)
Whether the float is zero.
Definition: rolx.cpp:282
static void Multiply(const TFltVV &A, const TFltV &x, TFltV &y)
Definition: linalg.cpp:428
static double Abs(const double &Flt)
Definition: dt.h:1430
TFltVV CreateRandMatrix(const int XDim, const int YDim)
Creates a random matrix with specified dimension.
Definition: rolx.cpp:270
TSizeTy GetXDim() const
Definition: ds.h:2250
static double Log(const double &Val)
Definition: xmath.h:14
const TVal & At(const TSizeTy &X, const TSizeTy &Y) const
Definition: ds.h:2256

Here is the call graph for this function:

TIntFtrH CalcVerticalLogBinning ( const TIntFtrH Features,
const float  BinFraction 
)

Calculates vertical logarithmic binning features from the given features.

Definition at line 147 of file rolx.cpp.

References AssignBinValue(), CreateEmptyFeatures(), GetNIdSorted(), and GetNumFeatures().

Referenced by PruneRecursiveFeatures().

148  {
149  const int NumFeatures = GetNumFeatures(Features);
150  TIntFtrH LogBinFeatures = CreateEmptyFeatures(Features);
151  for (int i = 0; i < NumFeatures; ++i) {
152  TVec<TInt> SortedNId = GetNIdSorted(Features, i);
153  AssignBinValue(SortedNId, BinFraction, LogBinFeatures);
154  }
155  return LogBinFeatures;
156 }
int GetNumFeatures(const TIntFtrH &Features)
Gets number of features from the node-feature mapping.
Definition: rolx.cpp:35
TIntFtrH CreateEmptyFeatures(const PUNGraph Graph)
Creates an empty node-feature mapping of all nodes in the given graph.
Definition: rolx.cpp:19
void AssignBinValue(const TVec< TInt > &SortedNId, const float BinFraction, TIntFtrH &LogBinFeatures)
Assigns logarithmic binning value to features.
Definition: rolx.cpp:212
Definition: hash.h:97
TVec< TInt > GetNIdSorted(const TIntFtrH &Features, const int Idx)
Sorts the Idx-th feature, return the list of corresponding node ID.
Definition: rolx.cpp:199

Here is the call graph for this function:

Here is the caller graph for this function:

TFltVV ConvertFeatureToMatrix ( const TIntFtrH Features,
const TIntIntH NodeIdMtxIdxH 
)

Converts node-feature mapping to matrix. (i, j): i-th node, j-th feature.

Definition at line 239 of file rolx.cpp.

References THash< TKey, TDat, THashFunc >::BegI(), THash< TKey, TDat, THashFunc >::EndI(), GetMtxIdx(), GetNumFeatures(), and THash< TKey, TDat, THashFunc >::Len().

240  {
241  const int NumNodes = Features.Len();
242  const int NumFeatures = GetNumFeatures(Features);
243  TFltVV FeaturesMtx(NumNodes, NumFeatures);
244  for (TIntFtrH::TIter HI = Features.BegI(); HI < Features.EndI(); HI++) {
245  int i = GetMtxIdx(HI.GetKey(), NodeIdMtxIdxH);
246  for (int j = 0; j < NumFeatures; ++j) {
247  FeaturesMtx(i, j) = HI.GetDat()[j];
248  }
249  }
250  return FeaturesMtx;
251 }
int GetNumFeatures(const TIntFtrH &Features)
Gets number of features from the node-feature mapping.
Definition: rolx.cpp:35
TIter BegI() const
Definition: hash.h:213
TIter EndI() const
Definition: hash.h:218
int GetMtxIdx(const TInt NodeId, const TIntIntH &NodeIdMtxIdxH)
Gets matrix index of the node ID.
Definition: rolx.cpp:383
int Len() const
Definition: hash.h:228

Here is the call graph for this function:

TIntFtrH CreateEmptyFeatures ( const PUNGraph  Graph)

Creates an empty node-feature mapping of all nodes in the given graph.

Definition at line 19 of file rolx.cpp.

References THash< TKey, TDat, THashFunc >::AddDat().

Referenced by CalcVerticalLogBinning(), ExtractFeatures(), GenerateRecursiveFeatures(), PruneRecursiveFeatures(), and SummarizeConnectedComponents().

19  {
20  TIntFtrH EmptyFeatures;
21  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
22  EmptyFeatures.AddDat(TInt(NI.GetId()), TFtr());
23  }
24  return EmptyFeatures;
25 }
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
Definition: dt.h:1137
Definition: hash.h:97
TVec< TFlt > TFtr
Feature of a node.
Definition: rolx.h:6
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

Here is the caller graph for this function:

TIntFtrH CreateEmptyFeatures ( const TIntFtrH Features)

Creates an empty node-feature mapping of all nodes from an existing mapping.

Definition at line 27 of file rolx.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), and THash< TKey, TDat, THashFunc >::EndI().

27  {
28  TIntFtrH EmptyFeatures;
29  for (TIntFtrH::TIter HI = Features.BegI(); HI < Features.EndI(); HI++) {
30  EmptyFeatures.AddDat(HI.GetKey(), TFtr());
31  }
32  return EmptyFeatures;
33 }
TIter BegI() const
Definition: hash.h:213
TIter EndI() const
Definition: hash.h:218
Definition: hash.h:97
TVec< TFlt > TFtr
Feature of a node.
Definition: rolx.h:6
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

TIntIntH CreateNodeIdMtxIdxHash ( const TIntFtrH Features)

Creates the mapping of <node ID, matrix index>.

Definition at line 373 of file rolx.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), and THash< TKey, TDat, THashFunc >::EndI().

373  {
374  TIntIntH H;
375  TInt Idx = 0;
376  for (TIntFtrH::TIter HI = Features.BegI(); HI < Features.EndI(); HI++) {
377  H.AddDat(HI.GetKey(), Idx);
378  Idx++;
379  }
380  return H;
381 }
TIter BegI() const
Definition: hash.h:213
TIter EndI() const
Definition: hash.h:218
Definition: dt.h:1137
Definition: hash.h:97
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

TFltVV CreateRandMatrix ( const int  XDim,
const int  YDim 
)

Creates a random matrix with specified dimension.

Definition at line 270 of file rolx.cpp.

Referenced by CalcNonNegativeFactorization().

270  {
271  int Seed = 13;
272  TFltVV Matrix(XDim, YDim);
273  for (int i = 0; i < XDim; ++i) {
274  for (int j = 0; j < YDim; ++j) {
275  Matrix(i, j) = (double)Seed / 10007;
276  Seed = (Seed * 1871) % 10007;
277  }
278  }
279  return Matrix;
280 }

Here is the caller graph for this function:

TIntFtrH ExtractFeatures ( const PUNGraph  Graph)

Performs feature extraction, the first step of RolX.

Definition at line 48 of file rolx.cpp.

References AddNeighborhoodFeatures(), AddRecursiveFeatures(), and CreateEmptyFeatures().

48  {
49  TIntFtrH Features = CreateEmptyFeatures(Graph);
50  AddNeighborhoodFeatures(Graph, Features);
51  printf("finish neighborhood features\n");
52  AddRecursiveFeatures(Graph, Features);
53  printf("finish recursive features\n");
54  return Features;
55 }
TIntFtrH CreateEmptyFeatures(const PUNGraph Graph)
Creates an empty node-feature mapping of all nodes in the given graph.
Definition: rolx.cpp:19
void AddRecursiveFeatures(const PUNGraph Graph, TIntFtrH &Features)
Adds recursive features to the node-feature mapping.
Definition: rolx.cpp:64
void AddNeighborhoodFeatures(const PUNGraph Graph, TIntFtrH &Features)
Adds neighborhood features (local + egonet) to the node-feature mapping.
Definition: rolx.cpp:57
Definition: hash.h:97

Here is the call graph for this function:

TIntIntH FindRoles ( const TFltVV G,
const TIntIntH NodeIdMtxIdxH 
)

Gets matrix index of the node ID.

Definition at line 398 of file rolx.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), GetNodeId(), TVVec< TVal, TSizeTy >::GetXDim(), TVVec< TVal, TSizeTy >::GetYDim(), and TFlt::Mn.

398  {
399  TIntIntH Roles;
400  for (int i = 0; i < G.GetXDim(); i++) {
401  int Role = -1;
402  TFlt Max = TFlt::Mn;
403  for (int j = 0; j < G.GetYDim(); j ++) {
404  if (G(i, j) > Max) {
405  Max = G(i, j);
406  Role = j;
407  }
408  }
409  int NodeId = GetNodeId(i, NodeIdMtxIdxH);
410  Roles.AddDat(NodeId, Role);
411  }
412  return Roles;
413 }
Definition: dt.h:1386
TSizeTy GetYDim() const
Definition: ds.h:2251
int GetNodeId(const TInt MtxId, const TIntIntH &NodeIdMtxIdxH)
Definition: rolx.cpp:387
TSizeTy GetXDim() const
Definition: ds.h:2250
Definition: hash.h:97
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
static const double Mn
Definition: dt.h:1390

Here is the call graph for this function:

bool FltIsZero ( const TFlt  Number)

Whether the float is zero.

Definition at line 282 of file rolx.cpp.

References TFlt::Abs(), and TFlt::Eps.

Referenced by CalcDescriptionLength(), and CalcNonNegativeFactorization().

282  {
283  return TFlt::Abs(Number) < TFlt::Eps;
284 }
static double Abs(const double &Flt)
Definition: dt.h:1430
static const double Eps
Definition: dt.h:1394

Here is the call graph for this function:

Here is the caller graph for this function:

void FPrintMatrix ( const TFltVV Matrix,
const TStr Path 
)

Prints feature matrix to file.

Definition at line 434 of file rolx.cpp.

References TStr::CStr(), TVVec< TVal, TSizeTy >::GetXDim(), and TVVec< TVal, TSizeTy >::GetYDim().

434  {
435  FILE *Fp;
436  Fp = fopen(Path.CStr(), "w");
437  int XDim = Matrix.GetXDim();
438  int YDim = Matrix.GetYDim();
439  for (int i = 0; i < XDim; ++i) {
440  for (int j = 0; j < YDim; ++j) {
441  if (j != 0) {
442  fprintf(Fp, " ");
443  }
444  fprintf(Fp, "%f", Matrix(i, j)());
445  }
446  fprintf(Fp, "\n");
447  }
448  fclose(Fp);
449 }
TSizeTy GetYDim() const
Definition: ds.h:2251
TSizeTy GetXDim() const
Definition: ds.h:2250
char * CStr()
Definition: dt.h:479

Here is the call graph for this function:

void FPrintNodeMappings ( const TIntIntH NodeIdMtxIdxH,
const TStr Path 
)

Prints node mappings to file, feature line -> node ID.

Definition at line 451 of file rolx.cpp.

References TStr::CStr(), GetNodeId(), and THash< TKey, TDat, THashFunc >::Len().

451  {
452  FILE *Fp;
453  Fp = fopen(Path.CStr(), "w");
454  fprintf(Fp, "# mappings from the feature line numbers to node IDs\n");
455  for (int i = 0; i < NodeIdMtxIdxH.Len(); i++) {
456  int NodeId = GetNodeId(i, NodeIdMtxIdxH);
457  fprintf(Fp, "%d %d\n", i, NodeId);
458  }
459  fclose(Fp);
460 }
int GetNodeId(const TInt MtxId, const TIntIntH &NodeIdMtxIdxH)
Definition: rolx.cpp:387
char * CStr()
Definition: dt.h:479
int Len() const
Definition: hash.h:228

Here is the call graph for this function:

void FPrintRoles ( const TIntIntH Roles,
const TStr Path 
)

Prints found roles to file.

Definition at line 462 of file rolx.cpp.

References THash< TKey, TDat, THashFunc >::BegI(), TStr::CStr(), and THash< TKey, TDat, THashFunc >::EndI().

462  {
463  FILE *Fp;
464  Fp = fopen(Path.CStr(), "w");
465  fprintf(Fp, "--roles (node ID role ID)--\n\n");
466  for (TIntIntH::TIter HI = Roles.BegI(); HI < Roles.EndI(); HI++) {
467  fprintf(Fp, "%d\t%d\n", HI.GetKey()(), HI.GetDat()());
468  }
469  fclose(Fp);
470 }
TIter BegI() const
Definition: hash.h:213
TIter EndI() const
Definition: hash.h:218
char * CStr()
Definition: dt.h:479

Here is the call graph for this function:

TIntFtrH GenerateRecursiveFeatures ( const PUNGraph  Graph,
const TIntFtrH CurrFeatures 
)

Generates recursive features out of current features.

Definition at line 97 of file rolx.cpp.

References CreateEmptyFeatures(), THash< TKey, TDat, THashFunc >::GetDat(), and GetNumFeatures().

Referenced by AddRecursiveFeatures().

98  {
99  const int NumCurrFeatures = GetNumFeatures(CurrFeatures);
100  if (0 == NumCurrFeatures) {
101  return CurrFeatures;
102  }
103  TIntFtrH NewFeatures = CreateEmptyFeatures(CurrFeatures);
104  for (int i = 0; i < NumCurrFeatures; ++i) {
105  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
106  float Sum = 0;
107  for (int j = 0; j < NI.GetInDeg(); ++j) {
108  int NbrNId = NI.GetInNId(j);
109  Sum += CurrFeatures.GetDat(NbrNId)[i]();
110  }
111  NewFeatures.GetDat(NI.GetId()).Add(Sum);
112  NewFeatures.GetDat(NI.GetId()).Add(0 == NI.GetInDeg()?
113  0 : (float(Sum) / NI.GetInDeg()));
114  }
115  }
116  return NewFeatures;
117 }
int GetNumFeatures(const TIntFtrH &Features)
Gets number of features from the node-feature mapping.
Definition: rolx.cpp:35
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
TIntFtrH CreateEmptyFeatures(const PUNGraph Graph)
Creates an empty node-feature mapping of all nodes in the given graph.
Definition: rolx.cpp:19
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
Definition: hash.h:97

Here is the call graph for this function:

Here is the caller graph for this function:

int GetMtxIdx ( const TInt  NodeId,
const TIntIntH NodeIdMtxIdxH 
)

Gets matrix index of the node ID.

Definition at line 383 of file rolx.cpp.

References THash< TKey, TDat, THashFunc >::GetDat().

Referenced by ConvertFeatureToMatrix().

383  {
384  return NodeIdMtxIdxH.GetDat(NodeId)();
385 }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262

Here is the call graph for this function:

Here is the caller graph for this function:

TVec<TInt> GetNIdSorted ( const TIntFtrH Features,
const int  Idx 
)

Sorts the Idx-th feature, return the list of corresponding node ID.

Definition at line 199 of file rolx.cpp.

References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), THash< TKey, TDat, THashFunc >::EndI(), and THash< TKey, TDat, THashFunc >::SortByDat().

Referenced by CalcVerticalLogBinning().

199  {
201  for (TIntFtrH::TIter HI = Features.BegI(); HI < Features.EndI(); HI++) {
202  F.AddDat(HI.GetKey(), HI.GetDat()[Idx]);
203  }
204  F.SortByDat();
205  TVec<TInt> SortedNId;
206  for (THash<TInt, TFlt>::TIter HI = F.BegI(); HI < F.EndI(); HI++) {
207  SortedNId.Add(HI.GetKey());
208  }
209  return SortedNId;
210 }
TIter BegI() const
Definition: hash.h:213
TIter EndI() const
Definition: hash.h:218
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
void SortByDat(const bool &Asc=true)
Definition: hash.h:292

Here is the call graph for this function:

Here is the caller graph for this function:

int GetNodeId ( const TInt  MtxId,
const TIntIntH NodeIdMtxIdxH 
)

Definition at line 387 of file rolx.cpp.

References THash< TKey, TDat, THashFunc >::BegI(), and THash< TKey, TDat, THashFunc >::EndI().

Referenced by FindRoles(), and FPrintNodeMappings().

387  {
388  for (TIntIntH::TIter HI = NodeIdMtxIdxH.BegI();
389  HI < NodeIdMtxIdxH.EndI();
390  HI++) {
391  if (HI.GetDat() == MtxId) {
392  return HI.GetKey()();
393  }
394  }
395  return -1;
396 }
TIter BegI() const
Definition: hash.h:213
TIter EndI() const
Definition: hash.h:218

Here is the call graph for this function:

Here is the caller graph for this function:

TFtr GetNthFeature ( const TIntFtrH Features,
const int  N 
)

Gets the n-th feature of all nodes.

Definition at line 39 of file rolx.cpp.

References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::BegI(), THash< TKey, TDat, THashFunc >::EndI(), GetNumFeatures(), and IAssert.

Referenced by BuildFeatureGraph().

39  {
40  TFtr NthFeature;
41  IAssert(0 <= N && N < GetNumFeatures(Features));
42  for (TIntFtrH::TIter HI = Features.BegI(); HI < Features.EndI(); HI++) {
43  NthFeature.Add(HI.GetDat()[N]);
44  }
45  return NthFeature;
46 }
#define IAssert(Cond)
Definition: bd.h:262
int GetNumFeatures(const TIntFtrH &Features)
Gets number of features from the node-feature mapping.
Definition: rolx.cpp:35
TIter BegI() const
Definition: hash.h:213
TIter EndI() const
Definition: hash.h:218
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

Here is the caller graph for this function:

int GetNumFeatures ( const TIntFtrH Features)

Gets number of features from the node-feature mapping.

Definition at line 35 of file rolx.cpp.

References THash< TKey, TDat, THashFunc >::BegI(), and THashKeyDatI< TKey, TDat >::GetDat().

Referenced by AddRecursiveFeatures(), BuildFeatureGraph(), CalcVerticalLogBinning(), ConvertFeatureToMatrix(), GenerateRecursiveFeatures(), GetNthFeature(), and SummarizeConnectedComponents().

35  {
36  return Features.BegI().GetDat().Len();
37 }
TIter BegI() const
Definition: hash.h:213
const TDat & GetDat() const
Definition: hash.h:81

Here is the call graph for this function:

Here is the caller graph for this function:

bool IsSimilarFeature ( const TFtr F1,
const TFtr F2,
const int  SimilarityThreshold 
)

Whether the two features are similar, given similarity threshold.

Definition at line 228 of file rolx.cpp.

References TFlt::Abs(), IAssert, and TVec< TVal, TSizeTy >::Len().

Referenced by BuildFeatureGraph().

229  {
230  IAssert(F1.Len() == F2.Len());
231  for (int i = 0; i < F1.Len(); ++i) {
232  if (TFlt::Abs(F1[i] - F2[i]) > SimilarityThreshold) {
233  return false;
234  }
235  }
236  return true;
237 }
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
static double Abs(const double &Flt)
Definition: dt.h:1430

Here is the call graph for this function:

Here is the caller graph for this function:

void PlotRoles ( const PUNGraph  Graph,
const TIntIntH Roles 
)

Plots found roles on a picture (.png).

Definition at line 415 of file rolx.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), TStr::CStr(), TSnap::DrawGViz(), THash< TKey, TDat, THashFunc >::EndI(), and gvlDot.

415  {
416  TStr RoleToColor[10] = { "white", "black", "red", "green", "blue",
417  "yellow", "gold", "cyan", "magenta", "brown" };
418  TIntStrH Color;
419  for (TIntIntH::TIter HI = Roles.BegI(); HI < Roles.EndI(); HI++) {
420  Color.AddDat(HI.GetKey(), RoleToColor[HI.GetDat()].CStr());
421  }
422  TSnap::DrawGViz(Graph, gvlDot, "gviz_plot.png", "Dot", 1, Color);
423 }
void DrawGViz(const PGraph &Graph, const TGVizLayout &Layout, const TStr &PltFNm, const TStr &Desc=TStr(), const bool &NodeLabels=false, const TIntStrH &NIdColorH=TIntStrH())
Draws a given Graph using a selected GraphViz Layout engine with nodes colored.
Definition: gviz.h:34
TIter BegI() const
Definition: hash.h:213
TIter EndI() const
Definition: hash.h:218
Definition: gviz.h:3
Definition: dt.h:412
char * CStr()
Definition: dt.h:479
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

void PrintFeatures ( const TIntFtrH Features)

Prints all nodes' feature.

Definition at line 5 of file rolx.cpp.

References THash< TKey, TDat, THashFunc >::BegI(), THash< TKey, TDat, THashFunc >::EndI(), TVec< TVal, TSizeTy >::GetDat(), and TVec< TVal, TSizeTy >::Len().

5  {
6  for (TIntFtrH::TIter HI = Features.BegI(); HI < Features.EndI(); HI++) {
7  printf("%d: [", HI.GetKey()());
8  const TFtr& Feature = HI.GetDat();
9  for (int i = 0; i < Feature.Len(); ++i) {
10  if (i > 0) {
11  printf(",");
12  }
13  printf("%f", Feature[i]());
14  }
15  printf("]\n");
16  }
17 }
TIter BegI() const
Definition: hash.h:213
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TIter EndI() const
Definition: hash.h:218
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:838

Here is the call graph for this function:

void PrintMatrix ( const TFltVV Matrix)

Prints feature matrix to stdout.

Definition at line 253 of file rolx.cpp.

References TVVec< TVal, TSizeTy >::GetXDim(), and TVVec< TVal, TSizeTy >::GetYDim().

253  {
254  int XDim = Matrix.GetXDim();
255  int YDim = Matrix.GetYDim();
256  printf("[");
257  for (int i = 0; i < XDim; ++i) {
258  printf("[");
259  for (int j = 0; j < YDim; ++j) {
260  if (j != 0) {
261  printf(" ");
262  }
263  printf("%f", Matrix(i, j)());
264  }
265  printf("]\n");
266  }
267  printf("]\n");
268 }
TSizeTy GetYDim() const
Definition: ds.h:2251
TSizeTy GetXDim() const
Definition: ds.h:2250

Here is the call graph for this function:

void PrintRoles ( const TIntIntH Roles)

Prints found roles on stdout.

Definition at line 425 of file rolx.cpp.

References THash< TKey, TDat, THashFunc >::BegI(), and THash< TKey, TDat, THashFunc >::EndI().

425  {
426  printf("--roles (node ID: role ID)--\n");
427  printf("{\n");
428  for (TIntIntH::TIter HI = Roles.BegI(); HI < Roles.EndI(); HI++) {
429  printf("(%d: %d)\n", HI.GetKey()(), HI.GetDat()());
430  }
431  printf("}\n");
432 }
TIter BegI() const
Definition: hash.h:213
TIter EndI() const
Definition: hash.h:218

Here is the call graph for this function:

TIntFtrH PruneRecursiveFeatures ( const PUNGraph  Graph,
const TIntFtrH Features,
const TIntFtrH NewFeatures,
const int  SimilarityThreshold 
)

Prunes recursive features.

Definition at line 119 of file rolx.cpp.

References AppendFeatures(), BuildFeatureGraph(), CalcVerticalLogBinning(), CreateEmptyFeatures(), and SummarizeConnectedComponents().

Referenced by AddRecursiveFeatures().

120  {
121  TIntFtrH AllFeatures = CreateEmptyFeatures(Features);
122  AppendFeatures(AllFeatures, Features);
123  AppendFeatures(AllFeatures, NewFeatures);
124  const float BinFraction = 0.5;
125  TIntFtrH LogBinFeatures = CalcVerticalLogBinning(AllFeatures, BinFraction);
126  PUNGraph FeatureGraph = BuildFeatureGraph(LogBinFeatures,
127  SimilarityThreshold);
128  return SummarizeConnectedComponents(FeatureGraph, Features, NewFeatures);
129 }
TIntFtrH SummarizeConnectedComponents(const PUNGraph FeatureGraph, const TIntFtrH &Features, const TIntFtrH &NewFeatures)
Summarizes s-friend graph and return retained features.
Definition: rolx.cpp:178
TIntFtrH CreateEmptyFeatures(const PUNGraph Graph)
Creates an empty node-feature mapping of all nodes in the given graph.
Definition: rolx.cpp:19
Definition: hash.h:97
Definition: bd.h:196
void AppendFeatures(TIntFtrH &DstFeatures, const TIntFtrH &SrcFeatures, const int ColIdx)
Appends all src features to dst features.
Definition: rolx.cpp:131
PUNGraph BuildFeatureGraph(const TIntFtrH &LogBinFeatures, const int SimilarityThreshold)
Builds s-friend graph given similarity threshold.
Definition: rolx.cpp:158
TIntFtrH CalcVerticalLogBinning(const TIntFtrH &Features, const float BinFraction)
Calculates vertical logarithmic binning features from the given features.
Definition: rolx.cpp:147

Here is the call graph for this function:

Here is the caller graph for this function:

TIntFtrH SummarizeConnectedComponents ( const PUNGraph  FeatureGraph,
const TIntFtrH Features,
const TIntFtrH NewFeatures 
)

Summarizes s-friend graph and return retained features.

Definition at line 178 of file rolx.cpp.

References TVec< TVal, TSizeTy >::Add(), AppendFeatures(), CreateEmptyFeatures(), GetNumFeatures(), TSnap::GetWccs(), TVec< TVal, TSizeTy >::Len(), and TVec< TVal, TSizeTy >::Sort().

Referenced by PruneRecursiveFeatures().

179  {
180  TCnComV Wcc;
181  TSnap::GetWccs(FeatureGraph, Wcc);
182  TVec<TInt> RetainedIdx;
183  for (int i = 0; i < Wcc.Len(); ++i) {
184  RetainedIdx.Add(Wcc[i][0]);
185  }
186  RetainedIdx.Sort();
187 
188  TIntFtrH RetainedFeatures = CreateEmptyFeatures(Features);
189  const int StartIdxNewFeatures = GetNumFeatures(Features);
190  for (int i = 0; i < RetainedIdx.Len(); ++i) {
191  const int IdxNewFeatures = RetainedIdx[i] - StartIdxNewFeatures;
192  if (IdxNewFeatures >= 0) {
193  AppendFeatures(RetainedFeatures, NewFeatures, IdxNewFeatures);
194  }
195  }
196  return RetainedFeatures;
197 }
int GetNumFeatures(const TIntFtrH &Features)
Gets number of features from the node-feature mapping.
Definition: rolx.cpp:35
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TIntFtrH CreateEmptyFeatures(const PUNGraph Graph)
Creates an empty node-feature mapping of all nodes in the given graph.
Definition: rolx.cpp:19
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
Definition: hash.h:97
void AppendFeatures(TIntFtrH &DstFeatures, const TIntFtrH &SrcFeatures, const int ColIdx)
Appends all src features to dst features.
Definition: rolx.cpp:131
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
void GetWccs(const PGraph &Graph, TCnComV &CnComV)
Returns all weakly connected components in a Graph.
Definition: cncom.h:376

Here is the call graph for this function:

Here is the caller graph for this function: