SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
rolx.cpp
Go to the documentation of this file.
1 #include "stdafx.h"
2 #include "Snap.h"
3 #include "rolx.h"
4 
5 void PrintFeatures(const TIntFtrH& Features) {
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 }
18 
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 }
26 
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 }
34 
35 int GetNumFeatures(const TIntFtrH& Features) {
36  return Features.BegI().GetDat().Len();
37 }
38 
39 TFtr GetNthFeature(const TIntFtrH& Features, const int N) {
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 }
47 
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 }
56 
57 void AddNeighborhoodFeatures(const PUNGraph Graph, TIntFtrH& Features) {
58  AddLocalFeatures(Graph, Features);
59  printf("finish local features\n");
60  AddEgonetFeatures(Graph, Features);
61  printf("finish egonet features\n");
62 }
63 
64 void AddRecursiveFeatures(const PUNGraph Graph, TIntFtrH& Features) {
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 }
80 
81 void AddLocalFeatures(const PUNGraph Graph, TIntFtrH& Features) {
82  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
83  Features.GetDat(TInt(NI.GetId())).Add(NI.GetInDeg());
84  }
85 }
86 
87 void AddEgonetFeatures(const PUNGraph Graph, TIntFtrH& Features) {
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 }
96 
98  const TIntFtrH& CurrFeatures) {
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 }
118 
119 TIntFtrH PruneRecursiveFeatures(const PUNGraph Graph, const TIntFtrH& Features,
120  const TIntFtrH& NewFeatures, const int SimilarityThreshold) {
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 }
130 
131 void AppendFeatures(TIntFtrH& DstFeatures, const TIntFtrH& SrcFeatures,
132  const int ColIdx) {
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 }
146 
148  const float BinFraction) {
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 }
157 
158 PUNGraph BuildFeatureGraph(const TIntFtrH& LogBinFeatures,
159  const int SimilarityThreshold) {
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 }
177 
179  const TIntFtrH& Features, const TIntFtrH& NewFeatures) {
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 }
198 
199 TVec<TInt> GetNIdSorted(const TIntFtrH& Features, const int Idx) {
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 }
211 
212 void AssignBinValue(const TVec<TInt>& SortedNId, const float BinFraction,
213  TIntFtrH& LogBinFeatures) {
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 }
227 
228 bool IsSimilarFeature(const TFtr& F1, const TFtr& F2,
229  const int SimilarityThreshold) {
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 }
238 
240  const TIntIntH& NodeIdMtxIdxH) {
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 }
252 
253 void PrintMatrix(const TFltVV& Matrix) {
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 }
269 
270 TFltVV CreateRandMatrix(const int XDim, const int YDim) {
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 }
281 
282 bool FltIsZero(const TFlt Number) {
283  return TFlt::Abs(Number) < TFlt::Eps;
284 }
285 
286 void CalcNonNegativeFactorization(const TFltVV& V, const int NumRoles,
287  TFltVV& W, TFltVV& H, const double Threshold) {
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 }
351 
353  const TFltVV& F) {
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 }
372 
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 }
382 
383 int GetMtxIdx(const TInt NodeId, const TIntIntH& NodeIdMtxIdxH) {
384  return NodeIdMtxIdxH.GetDat(NodeId)();
385 }
386 
387 int GetNodeId(const TInt MtxId, const TIntIntH& NodeIdMtxIdxH) {
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 }
397 
398 TIntIntH FindRoles(const TFltVV& G, const TIntIntH& NodeIdMtxIdxH) {
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 }
414 
415 void PlotRoles(const PUNGraph Graph, const TIntIntH& Roles) {
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 }
424 
425 void PrintRoles(const TIntIntH& Roles) {
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 }
433 
434 void FPrintMatrix(const TFltVV& Matrix, const TStr& Path) {
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 }
450 
451 void FPrintNodeMappings(const TIntIntH& NodeIdMtxIdxH, const TStr& Path) {
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 }
461 
462 void FPrintRoles(const TIntIntH& Roles, const TStr& Path) {
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 }
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
#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
TIntFtrH SummarizeConnectedComponents(const PUNGraph FeatureGraph, const TIntFtrH &Features, const TIntFtrH &NewFeatures)
Summarizes s-friend graph and return retained features.
Definition: rolx.cpp:178
void AddLocalFeatures(const PUNGraph Graph, TIntFtrH &Features)
Adds local features to the node-feature mapping.
Definition: rolx.cpp:81
static TPt New()
Definition: bd.h:479
TIter BegI() const
Definition: hash.h:213
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
TIntIntH FindRoles(const TFltVV &G, const TIntIntH &NodeIdMtxIdxH)
Gets matrix index of the node ID.
Definition: rolx.cpp:398
void PlotRoles(const PUNGraph Graph, const TIntIntH &Roles)
Plots found roles on a picture (.png).
Definition: rolx.cpp:415
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
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: rolx.cpp:286
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
TIntFtrH PruneRecursiveFeatures(const PUNGraph Graph, const TIntFtrH &Features, const TIntFtrH &NewFeatures, const int SimilarityThreshold)
Prunes recursive features.
Definition: rolx.cpp:119
TFltVV ConvertFeatureToMatrix(const TIntFtrH &Features, const TIntIntH &NodeIdMtxIdxH)
Converts node-feature mapping to matrix. (i, j): i-th node, j-th feature.
Definition: rolx.cpp:239
Definition: dt.h:1386
TIntFtrH ExtractFeatures(const PUNGraph Graph)
Performs feature extraction, the first step of RolX.
Definition: rolx.cpp:48
const TDat & GetDat() const
Definition: hash.h:81
void PrintRoles(const TIntIntH &Roles)
Prints found roles on stdout.
Definition: rolx.cpp:425
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
TSizeTy GetYDim() const
Definition: ds.h:2251
TFtr GetNthFeature(const TIntFtrH &Features, const int N)
Gets the n-th feature of all nodes.
Definition: rolx.cpp:39
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:838
void AddRecursiveFeatures(const PUNGraph Graph, TIntFtrH &Features)
Adds recursive features to the node-feature mapping.
Definition: rolx.cpp:64
TIntFtrH GenerateRecursiveFeatures(const PUNGraph Graph, const TIntFtrH &CurrFeatures)
Generates recursive features out of current features.
Definition: rolx.cpp:97
bool FltIsZero(const TFlt Number)
Whether the float is zero.
Definition: rolx.cpp:282
void AddNeighborhoodFeatures(const PUNGraph Graph, TIntFtrH &Features)
Adds neighborhood features (local + egonet) to the node-feature mapping.
Definition: rolx.cpp:57
Definition: gviz.h:3
int GetNodeId(const TInt MtxId, const TIntIntH &NodeIdMtxIdxH)
Definition: rolx.cpp:387
void AssignBinValue(const TVec< TInt > &SortedNId, const float BinFraction, TIntFtrH &LogBinFeatures)
Assigns logarithmic binning value to features.
Definition: rolx.cpp:212
bool IsSimilarFeature(const TFtr &F1, const TFtr &F2, const int SimilarityThreshold)
Whether the two features are similar, given similarity threshold.
Definition: rolx.cpp:228
TIntIntH CreateNodeIdMtxIdxHash(const TIntFtrH &Features)
Creates the mapping of .
Definition: rolx.cpp:373
void PrintMatrix(const TFltVV &Matrix)
Prints feature matrix to stdout.
Definition: rolx.cpp:253
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
Definition: dt.h:1137
void PrintFeatures(const TIntFtrH &Features)
Prints all nodes' feature.
Definition: rolx.cpp:5
void FPrintMatrix(const TFltVV &Matrix, const TStr &Path)
Prints feature matrix to file.
Definition: rolx.cpp:434
TFltVV CreateRandMatrix(const int XDim, const int YDim)
Creates a random matrix with specified dimension.
Definition: rolx.cpp:270
TFlt CalcDescriptionLength(const TFltVV &V, const TFltVV &G, const TFltVV &F)
Calculates the description length L = M + E.
Definition: rolx.cpp:352
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: dt.h:412
TSizeTy GetXDim() const
Definition: ds.h:2250
void AddEgonetFeatures(const PUNGraph Graph, TIntFtrH &Features)
Adds egonet features to the node-feature mapping.
Definition: rolx.cpp:87
Definition: hash.h:97
Definition: bd.h:196
void FPrintNodeMappings(const TIntIntH &NodeIdMtxIdxH, const TStr &Path)
Prints node mappings to file, feature line -> node ID.
Definition: rolx.cpp:451
static double Log(const double &Val)
Definition: xmath.h:14
TVec< TFlt > TFtr
Feature of a node.
Definition: rolx.h:6
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
char * CStr()
Definition: dt.h:479
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
int Len() const
Definition: hash.h:228
void FPrintRoles(const TIntIntH &Roles, const TStr &Path)
Prints found roles to file.
Definition: rolx.cpp:462
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
void GetWccs(const PGraph &Graph, TCnComV &CnComV)
Returns all weakly connected components in a Graph.
Definition: cncom.h:376
static const double Eps
Definition: dt.h:1394
static const double Mn
Definition: dt.h:1390
PUNGraph BuildFeatureGraph(const TIntFtrH &LogBinFeatures, const int SimilarityThreshold)
Builds s-friend graph given similarity threshold.
Definition: rolx.cpp:158
const TVal & At(const TSizeTy &X, const TSizeTy &Y) const
Definition: ds.h:2256
TIntFtrH CalcVerticalLogBinning(const TIntFtrH &Features, const float BinFraction)
Calculates vertical logarithmic binning features from the given features.
Definition: rolx.cpp:147
void SortByDat(const bool &Asc=true)
Definition: hash.h:292