rolx.h File Reference

#include "Snap.h"

Go to the source code of this file.

Typedefs
typedef TVec< TFlt >	TFtr
	Feature of a node. More...
typedef THash< TInt, TFtr >	TIntFtrH
	The node-feature mapping: <node ID, feature>. More...

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=-1)
	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 &LogFeatures, 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< TInt >	GetNIdSorted (const TIntFtrH &Feature, 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...
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	FPrintRoles (const TIntIntH &Roles, const TStr &Path)
	Prints found roles to file. More...

Typedef Documentation

typedef TVec<TFlt> TFtr

Feature of a node.

Definition at line 6 of file rolx.h.

typedef THash<TInt, TFtr> TIntFtrH

The node-feature mapping: <node ID, feature>.

Definition at line 8 of file rolx.h.

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.

                                                                 {
  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    int NId = NI.GetId();
    int ArndEdges;
    PUNGraph Egonet = TSnap::GetEgonet(Graph, NId, ArndEdges);
    Features.GetDat(NId).Add(Egonet->GetEdges());
    Features.GetDat(NId).Add(ArndEdges);
  }
}

void AddLocalFeatures	(	const PUNGraph	Graph,
		TIntFtrH &	Features
	)

Adds local features to the node-feature mapping.

Definition at line 81 of file rolx.cpp.

                                                                {
  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    Features.GetDat(TInt(NI.GetId())).Add(NI.GetInDeg());
  }
}

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.

                                                                       {
  AddLocalFeatures(Graph, Features);
  printf("finish local features\n");
  AddEgonetFeatures(Graph, Features);
  printf("finish egonet features\n");
}

void AddRecursiveFeatures	(	const PUNGraph	Graph,
		TIntFtrH &	Features
	)

Adds recursive features to the node-feature mapping.

Definition at line 64 of file rolx.cpp.

                                                                    {
  int SimilarityThreshold = 0;
  TIntFtrH RetainedFeatures = Features;
  while (true) {
    TIntFtrH NewFeatures = GenerateRecursiveFeatures(Graph, RetainedFeatures);
    RetainedFeatures = PruneRecursiveFeatures(Graph, Features, NewFeatures,
        SimilarityThreshold);
    if (0 == GetNumFeatures(RetainedFeatures)) {
      break;
    }
    AppendFeatures(Features, RetainedFeatures);
    ++SimilarityThreshold;
    printf("recursion %d: ", SimilarityThreshold);
    printf("current feature number %d\n", GetNumFeatures(Features));
  }
}

void AppendFeatures	(	TIntFtrH &	DstFeatures,
		const TIntFtrH &	SrcFeatures,
		const int	ColIdx = -1
	)

Appends all src features to dst features.

Definition at line 131 of file rolx.cpp.

                      {
  for (TIntFtrH::TIter HI = SrcFeatures.BegI();
      HI < SrcFeatures.EndI();
      HI++) {
    const TFtr& Feature = HI.GetDat();
    if (ColIdx >= 0) {
      DstFeatures.GetDat(HI.GetKey()).Add(Feature[ColIdx]);
    } else {
      for (int i = 0; i < Feature.Len(); ++i) {
        DstFeatures.GetDat(HI.GetKey()).Add(Feature[i]);
      }
    }
  }
}

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.

                              {
  int NumNodes = LogBinFeatures.Len();
  int NumAssigned = 0;
  int BinValue = 0;
  while (NumAssigned < NumNodes) {
    int NumToAssign = ceil(BinFraction * (NumNodes - NumAssigned));
    for (int i = NumAssigned; i < NumAssigned + NumToAssign; ++i) {
      int NId = SortedNId[i];
      LogBinFeatures.GetDat(NId).Add(BinValue);
    }
    NumAssigned += NumToAssign;
    ++BinValue;
  }
}

PUNGraph BuildFeatureGraph	(	const TIntFtrH &	LogFeatures,
		const int	SimilarityThreshold
	)

Builds s-friend graph given similarity threshold.

Definition at line 158 of file rolx.cpp.

                                   {
  PUNGraph FeatureGraph = PUNGraph::New();
  const int NumFeatures = GetNumFeatures(LogBinFeatures);
  for (int i = 0; i < NumFeatures; ++i) {
    FeatureGraph->AddNode(i);
  }
  for (int i = 0; i < NumFeatures; ++i) {
    TFtr IthFeature = GetNthFeature(LogBinFeatures, i);
    for (int j = i + 1; j < NumFeatures; ++j) {
      TFtr JthFeature = GetNthFeature(LogBinFeatures, j);
      if (IsSimilarFeature(IthFeature, JthFeature, SimilarityThreshold) &&
          !FeatureGraph->IsEdge(i, j)) {
        FeatureGraph->AddEdge(i, j);
      }
    }
  }
  return FeatureGraph;
}

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.

                     {
  int B = 64;
  int M = B * V.GetYDim() * (V.GetXDim() + F.GetYDim());
  TFlt E = 0;
  TFltVV GF(G.GetXDim(), F.GetYDim());
  TLinAlg::Multiply(G, F, GF);
  for (int i = 0; i < V.GetXDim(); ++i) {
    for (int j = 0; j < V.GetYDim(); ++j) {
      TFlt ValueV = V(i, j);
      TFlt ValueGF = GF(i, j);
      if (FltIsZero(ValueV)) {
        E += ValueGF;
      } else if (!FltIsZero(ValueGF)) {
        E += ValueV * TMath::Log(ValueV / ValueGF) - ValueV + ValueGF;
      }
    }
  }
  return M + E;
}

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.

                                                  {
  double Cost = 100, NewCost = 0;
  int NumNodes = V.GetXDim();
  int NumFeatures = V.GetYDim();
  W = CreateRandMatrix(NumNodes, NumRoles);
  H = CreateRandMatrix(NumRoles, NumFeatures);
  TFltVV NewW(NumNodes, NumRoles);
  TFltVV NewH(NumRoles, NumFeatures);
  TFltVV Product(NumNodes, NumFeatures);
  TFltV Sum(NumRoles);
  TFltVV *PW = &W, *PH = &H, *PNewW = &NewW, *PNewH = &NewH, *Tmp;
  //int IterNum = 1;
  while (TFlt::Abs((NewCost - Cost)/Cost) > Threshold) {
    TLinAlg::Multiply(*PW, *PH, Product);
    //converge condition
    Cost = NewCost;
    NewCost = 0;
    for (int i = 0; i < NumNodes; i++) {
      for (int j = 0; j < NumFeatures; j++) {
        NewCost += V(i, j) * TMath::Log(Product(i, j)) - Product(i, j);
      }
    }
    // update W
    for (int i = 0; i < NumNodes; i++) {
      for (int a = 0; a < NumRoles; a++) {
        double SumU = 0;
        for (int u = 0; u < NumFeatures; ++u) {
          if (!FltIsZero(Product(i, u))) {
            SumU += V(i, u) / Product(i, u) * PH->At(a, u);
          }
        }
        PNewW->At(i, a) = PW->At(i, a) * SumU;
      }
    }
    for (int i = 0; i < NumRoles; i++) {
      Sum[i] = 0;
    }
    for (int i = 0; i < NumNodes; i++) {
      for (int j = 0; j < NumRoles; j++) {
        Sum[j] += PNewW->At(i, j);
      }
    }
    for (int i = 0; i < NumNodes; i++) {
      for (int j = 0; j < NumRoles; j++) {
        PNewW->At(i, j) /= Sum[j];
      }
    }
    // update H
    for (int a = 0; a < NumRoles; a++) {
      for (int u = 0; u < NumFeatures; u++) {
        double SumI = 0;
        for (int i = 0; i < NumNodes; ++i) {
          if (!FltIsZero(Product(i, u))) {
            SumI += PW->At(i, a) * V(i, u) / Product(i, u);
          }
        }
        PNewH->At(a, u) = PH->At(a, u) * SumI;
      }
    }
    //printf("iteration %d, cost is %f\n", IterNum++, NewCost);
    Tmp = PW; PW = PNewW; PNewW = Tmp;
    Tmp = PH; PH = PNewH; PNewH = Tmp;
  }
}

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.

                             {
  const int NumFeatures = GetNumFeatures(Features);
  TIntFtrH LogBinFeatures = CreateEmptyFeatures(Features);
  for (int i = 0; i < NumFeatures; ++i) {
    TVec<TInt> SortedNId = GetNIdSorted(Features, i);
    AssignBinValue(SortedNId, BinFraction, LogBinFeatures);
  }
  return LogBinFeatures;
}

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.

                                   {
  const int NumNodes = Features.Len();
  const int NumFeatures = GetNumFeatures(Features);
  TFltVV FeaturesMtx(NumNodes, NumFeatures);
  for (TIntFtrH::TIter HI = Features.BegI(); HI < Features.EndI(); HI++) {
    int i = GetMtxIdx(HI.GetKey(), NodeIdMtxIdxH);
    for (int j = 0; j < NumFeatures; ++j) {
      FeaturesMtx(i, j) = HI.GetDat()[j];
    }
  }
  return FeaturesMtx;
}

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.

                                                   {
  TIntFtrH EmptyFeatures;
  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    EmptyFeatures.AddDat(TInt(NI.GetId()), TFtr());
  }
  return EmptyFeatures;
}

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.

                                                       {
  TIntFtrH EmptyFeatures;
  for (TIntFtrH::TIter HI = Features.BegI(); HI < Features.EndI(); HI++) {
    EmptyFeatures.AddDat(HI.GetKey(), TFtr());
  }
  return EmptyFeatures;
}

TIntIntH CreateNodeIdMtxIdxHash

(

const TIntFtrH &

Features

)

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

Definition at line 373 of file rolx.cpp.

                                                          {
  TIntIntH H;
  TInt Idx = 0;
  for (TIntFtrH::TIter HI = Features.BegI(); HI < Features.EndI(); HI++) {
    H.AddDat(HI.GetKey(), Idx);
    Idx++;
  }
  return H;
}

TFltVV CreateRandMatrix	(	const int	XDim,
		const int	YDim
	)

Creates a random matrix with specified dimension.

Definition at line 270 of file rolx.cpp.

                                                        {
  int Seed = 13;
  TFltVV Matrix(XDim, YDim);
  for (int i = 0; i < XDim; ++i) {
    for (int j = 0; j < YDim; ++j) {
      Matrix(i, j) = (double)Seed / 10007;
      Seed = (Seed * 1871) % 10007;
    }
  }
  return Matrix;
}

TIntFtrH ExtractFeatures

(

const PUNGraph

Graph

)

Performs feature extraction, the first step of RolX.

Definition at line 48 of file rolx.cpp.

                                               {
  TIntFtrH Features = CreateEmptyFeatures(Graph);
  AddNeighborhoodFeatures(Graph, Features);
  printf("finish neighborhood features\n");
  AddRecursiveFeatures(Graph, Features);
  printf("finish recursive features\n");
  return Features;
}

TIntIntH FindRoles	(	const TFltVV &	G,
		const TIntIntH &	NodeIdMtxIdxH
	)

Gets matrix index of the node ID.

Definition at line 398 of file rolx.cpp.

                                                                   {
  TIntIntH Roles;
  for (int i = 0; i < G.GetXDim(); i++) {
    int Role = -1;
    TFlt Max = TFlt::Mn;
    for (int j = 0; j < G.GetYDim(); j ++) {
      if (G(i, j) > Max) {
        Max = G(i, j);
        Role = j;
      }
    }
    int NodeId = GetNodeId(i, NodeIdMtxIdxH);
    Roles.AddDat(NodeId, Role);
  }
  return Roles;
}

bool FltIsZero

(

const TFlt

Number

)

Whether the float is zero.

Definition at line 282 of file rolx.cpp.

                                  {
  return TFlt::Abs(Number) < TFlt::Eps;
}

void FPrintMatrix	(	const TFltVV &	Matrix,
		const TStr &	Path
	)

Prints feature matrix to file.

Definition at line 434 of file rolx.cpp.

                                                          {
  FILE *Fp;
  Fp = fopen(Path.CStr(), "w");
  int XDim = Matrix.GetXDim();
  int YDim = Matrix.GetYDim();
  for (int i = 0; i < XDim; ++i) {
    for (int j = 0; j < YDim; ++j) {
      if (j != 0) {
        fprintf(Fp, " ");
      }
      fprintf(Fp, "%f", Matrix(i, j)());
    }
    fprintf(Fp, "\n");
  }
  fclose(Fp);
}

void FPrintRoles	(	const TIntIntH &	Roles,
		const TStr &	Path
	)

Prints found roles to file.

Definition at line 451 of file rolx.cpp.

                                                          {
  FILE *Fp;
  Fp = fopen(Path.CStr(), "w");
  fprintf(Fp, "--roles (node ID role ID)--\n\n");
  for (TIntIntH::TIter HI = Roles.BegI(); HI < Roles.EndI(); HI++) {
    fprintf(Fp, "%d\t%d\n", HI.GetKey()(), HI.GetDat()());
  }
  fclose(Fp);
}

TIntFtrH GenerateRecursiveFeatures	(	const PUNGraph	Graph,
		const TIntFtrH &	CurrFeatures
	)

Generates recursive features out of current features.

Definition at line 97 of file rolx.cpp.

                                  {
  const int NumCurrFeatures = GetNumFeatures(CurrFeatures);
  if (0 == NumCurrFeatures) {
    return CurrFeatures;
  }
  TIntFtrH NewFeatures = CreateEmptyFeatures(CurrFeatures);
  for (int i = 0; i < NumCurrFeatures; ++i) {
    for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
      float Sum = 0;
      for (int j = 0; j < NI.GetInDeg(); ++j) {
        int NbrNId = NI.GetInNId(j);
        Sum += CurrFeatures.GetDat(NbrNId)[i]();
      }
      NewFeatures.GetDat(NI.GetId()).Add(Sum);
      NewFeatures.GetDat(NI.GetId()).Add(0 == NI.GetInDeg()?
          0 : (float(Sum) / NI.GetInDeg()));
    }
  }
  return NewFeatures;
}

int GetMtxIdx	(	const TInt	NodeId,
		const TIntIntH &	NodeIdMtxIdxH
	)

Gets matrix index of the node ID.

Definition at line 383 of file rolx.cpp.

                                                                {
  return NodeIdMtxIdxH.GetDat(NodeId)();
}

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

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

Definition at line 199 of file rolx.cpp.

                                                                 {
  THash<TInt, TFlt> F;
  for (TIntFtrH::TIter HI = Features.BegI(); HI < Features.EndI(); HI++) {
    F.AddDat(HI.GetKey(), HI.GetDat()[Idx]);
  }
  F.SortByDat();
  TVec<TInt> SortedNId;
  for (THash<TInt, TFlt>::TIter HI = F.BegI(); HI < F.EndI(); HI++) {
    SortedNId.Add(HI.GetKey());
  }
  return SortedNId;
}

TFtr GetNthFeature	(	const TIntFtrH &	Features,
		const int	N
	)

Gets the n-th feature of all nodes.

Definition at line 39 of file rolx.cpp.

                                                          {
  TFtr NthFeature;
  IAssert(0 <= N && N < GetNumFeatures(Features));
  for (TIntFtrH::TIter HI = Features.BegI(); HI < Features.EndI(); HI++) {
    NthFeature.Add(HI.GetDat()[N]);
  }
  return NthFeature;
}

int GetNumFeatures

(

const TIntFtrH &

Features

)

Gets number of features from the node-feature mapping.

Definition at line 35 of file rolx.cpp.

                                             {
  return Features.BegI().GetDat().Len();
}

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.

                                   {
  IAssert(F1.Len() == F2.Len());
  for (int i = 0; i < F1.Len(); ++i) {
    if (TFlt::Abs(F1[i] - F2[i]) > SimilarityThreshold) {
      return false;
    }
  }
  return true;
}

void PlotRoles	(	const PUNGraph	Graph,
		const TIntIntH &	Roles
	)

Plots found roles on a picture (.png).

Definition at line 415 of file rolx.cpp.

                                                            {
  TStr RoleToColor[10] = { "white", "black", "red", "green", "blue",
      "yellow", "gold", "cyan", "magenta", "brown" };
  TIntStrH Color;
  for (TIntIntH::TIter HI = Roles.BegI(); HI < Roles.EndI(); HI++) {
    Color.AddDat(HI.GetKey(), RoleToColor[HI.GetDat()].CStr());
  }
  TSnap::DrawGViz(Graph, gvlDot, "gviz_plot.png", "Dot", 1, Color);
}

void PrintFeatures

(

const TIntFtrH &

Features

)

Prints all nodes' feature.

Definition at line 5 of file rolx.cpp.

                                             {
  for (TIntFtrH::TIter HI = Features.BegI(); HI < Features.EndI(); HI++) {
    printf("%d: [", HI.GetKey()());
    const TFtr& Feature = HI.GetDat();
    for (int i = 0; i < Feature.Len(); ++i) {
      if (i > 0) {
        printf(",");
      }
      printf("%f", Feature[i]());
    }
    printf("]\n");
  }
}

void PrintMatrix

(

const TFltVV &

Matrix

)

Prints feature matrix to stdout.

Definition at line 253 of file rolx.cpp.

                                       {
  int XDim = Matrix.GetXDim();
  int YDim = Matrix.GetYDim();
  printf("[");
  for (int i = 0; i < XDim; ++i) {
    printf("[");
    for (int j = 0; j < YDim; ++j) {
      if (j != 0) {
        printf(" ");
      }
      printf("%f", Matrix(i, j)());
    }
    printf("]\n");
  }
  printf("]\n");
}

void PrintRoles

(

const TIntIntH &

Roles

)

Prints found roles on stdout.

Definition at line 425 of file rolx.cpp.

                                       {
  printf("--roles (node ID: role ID)--\n");
  printf("{\n");
  for (TIntIntH::TIter HI = Roles.BegI(); HI < Roles.EndI(); HI++) {
    printf("(%d: %d)\n", HI.GetKey()(), HI.GetDat()());
  }
  printf("}\n");
}

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.

                                                                {
  TIntFtrH AllFeatures = CreateEmptyFeatures(Features);
  AppendFeatures(AllFeatures, Features);
  AppendFeatures(AllFeatures, NewFeatures);
  const float BinFraction = 0.5;
  TIntFtrH LogBinFeatures = CalcVerticalLogBinning(AllFeatures, BinFraction);
  PUNGraph FeatureGraph = BuildFeatureGraph(LogBinFeatures,
      SimilarityThreshold);
  return SummarizeConnectedComponents(FeatureGraph, Features, NewFeatures);
}

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.

                                                           {
  TCnComV Wcc;
  TSnap::GetWccs(FeatureGraph, Wcc);
  TVec<TInt> RetainedIdx;
  for (int i = 0; i < Wcc.Len(); ++i) {
    RetainedIdx.Add(Wcc[i][0]);
  }
  RetainedIdx.Sort();

  TIntFtrH RetainedFeatures = CreateEmptyFeatures(Features);
  const int StartIdxNewFeatures = GetNumFeatures(Features);
  for (int i = 0; i < RetainedIdx.Len(); ++i) {
    const int IdxNewFeatures = RetainedIdx[i] - StartIdxNewFeatures;
    if (IdxNewFeatures >= 0) {
      AppendFeatures(RetainedFeatures, NewFeatures, IdxNewFeatures);
    }
  }
  return RetainedFeatures;
}