MotifCluster Class Reference

#include <motifcluster.h>

Static Public Member Functions
static void	GetMotifCluster (PNGraph graph, MotifType motif, TSweepCut &sweepcut, double tol=kDefaultTol, int maxiter=kMaxIter)
static void	GetMotifCluster (PUNGraph graph, MotifType motif, TSweepCut &sweepcut, double tol=kDefaultTol, int maxiter=kMaxIter)
static void	MotifAdjacency (PNGraph graph, MotifType motif, WeightVH &weights)
static void	MotifAdjacency (PUNGraph graph, MotifType motif, WeightVH &weights)
static void	SpectralCut (const WeightVH &weights, TSweepCut &sweepcut, double tol=kDefaultTol, int maxiter=kMaxIter)
static double	NFiedlerVector (const TSparseColMatrix &W, TFltV &fvec, double tol=kDefaultTol, int maxiter=kMaxIter)
static MotifType	ParseMotifType (const TStr &motif)
static bool	IsMotifM1 (PNGraph graph, int u, int v, int w)
static bool	IsMotifM2 (PNGraph graph, int u, int v, int w)
static bool	IsMotifM3 (PNGraph graph, int u, int v, int w)
static bool	IsMotifM4 (PNGraph graph, int u, int v, int w)
static bool	IsMotifM5 (PNGraph graph, int u, int v, int w)
static bool	IsMotifM6 (PNGraph graph, int u, int v, int w)
static bool	IsMotifM7 (PNGraph graph, int u, int v, int w)
static bool	IsMotifM8 (PNGraph graph, int center, int v, int w)
static bool	IsMotifM9 (PNGraph graph, int center, int v, int w)
static bool	IsMotifM10 (PNGraph graph, int center, int v, int w)
static bool	IsMotifM11 (PNGraph graph, int center, int v, int w)
static bool	IsMotifM12 (PNGraph graph, int center, int v, int w)
static bool	IsMotifM13 (PNGraph graph, int center, int v, int w)
static bool	IsUnidirEdge (PNGraph graph, int u, int v)
static bool	IsBidirEdge (PNGraph graph, int u, int v)
static bool	IsNoEdge (PNGraph graph, int u, int v)
static void	DegreeOrdering (PNGraph graph, TIntV &order)

Static Private Member Functions
static void	EdgeMotifAdjacency (PNGraph graph, WeightVH &weights)
static void	EdgeMotifAdjacency (PUNGraph graph, WeightVH &weights)
static void	TriangleMotifAdjacency (PNGraph graph, MotifType motif, WeightVH &weights)
static void	WedgeMotifAdjacency (PNGraph graph, MotifType motif, WeightVH &weights)
static void	BifanMotifAdjacency (PNGraph graph, WeightVH &weights)
static void	SemicliqueMotifAdjacency (PUNGraph graph, WeightVH &weights)
static void	CliqueMotifAdjacency (PUNGraph graph, int clique_size, WeightVH &weights)

Detailed Description

Definition at line 56 of file motifcluster.h.

Member Function Documentation

void MotifCluster::BifanMotifAdjacency ( PNGraph  graph, WeightVH &  weights  )

staticprivate

Definition at line 341 of file motifcluster.cpp.

                                                                       {
  // Find all pairs of nodes that are not adjacent
  // Note: does not scale to large sparse networks but will work for smaller
  // networks such as common neuronal connectivity datasets.
  TIntV node_ids;
  for (TNGraph::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++) {
    node_ids.Add(NI.GetId());
  }
  for (int i = 0; i < node_ids.Len(); i++) {
    for (int j = i + 1; j < node_ids.Len(); j++) {
      int src1 = node_ids[i];
      int src2 = node_ids[j];
      if (IsNoEdge(graph, src1, src2)) {
        // All unidirectional out-neighbors of src1
        THash<TInt, TInt> nbr_counts;
        TNGraph::TNodeI NI1 = graph->GetNI(src1);
        for (int k = 0; k < NI1.GetOutDeg(); k++) {
          int nbr = NI1.GetOutNId(k);
          if (IsUnidirEdge(graph, src1, nbr)) {
            nbr_counts(nbr) += 1;
          }
        }

        // All unidirectional out-neighbors of src2
        TNGraph::TNodeI NI2 = graph->GetNI(src2);
        for (int k = 0; k < NI2.GetOutDeg(); k++) {
          int nbr = NI2.GetOutNId(k);
          if (IsUnidirEdge(graph, src2, nbr)) {
            nbr_counts(nbr) += 1;
          }
        }

        // Get all common outgoing neighbors
        TIntV common;
        for (THash<TInt, TInt>::TIter it = nbr_counts.BegI();
             it < nbr_counts.EndI(); it++) {
          if (it->Dat == 2) {
            common.Add(it->Key);
          }
        }

        // Update weights with all common neighbors
        for (int ind1 = 0; ind1 < common.Len(); ind1++) {
          for (int ind2 = (ind1 + 1); ind2 < common.Len(); ind2++) {
            int dst1 = common[ind1];
            int dst2 = common[ind2];
            if (IsNoEdge(graph, dst1, dst2)) {
              IncrementWeight(src1, src2, weights);
              IncrementWeight(src1, dst1, weights);
              IncrementWeight(src1, dst2, weights);
              IncrementWeight(src2, dst1, weights);
              IncrementWeight(src2, dst2, weights);
              IncrementWeight(dst1, dst2, weights);
            }
          }
        }
      }
    }
  }
}

void MotifCluster::CliqueMotifAdjacency ( PUNGraph  graph, int  clique_size, WeightVH &  weights  )

staticprivate

Definition at line 503 of file motifcluster.cpp.

                                                           {
  ChibaNishizekiWeighter cnw(graph);
  cnw.Run(clique_size);
  weights = cnw.weights();
}

void MotifCluster::DegreeOrdering ( PNGraph  graph, TIntV &  order  )

static

Definition at line 185 of file motifcluster.cpp.

                                                             {
  // Note: This is the most efficient when the nodes are numbered
  // 0, 1, ..., num_nodes - 1.
  int max_nodes = graph->GetMxNId() + 1;
  TVec< TKeyDat<TInt, TInt> > degrees(max_nodes);
  degrees.PutAll(TKeyDat<TInt, TInt>(0, 0));
  // Set the degree of a node to be the number of nodes adjacent to the node in
  // the undirected graph.
  for (TNGraph::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++) {
    int src = NI.GetId();
    int num_nbrs = NI.GetOutDeg();
    // For each incoming edge that is not an outgoing edge, include it.
    for (int i = 0; i < NI.GetInDeg(); ++i) {
      int dst = NI.GetInNId(i);
      if (!NI.IsOutNId(dst)) {
        ++num_nbrs;
      }
    }
    degrees[src] = TKeyDat<TInt, TInt>(num_nbrs, src);
  }

  degrees.Sort();
  order = TIntV(max_nodes);
  for (int i = 0; i < order.Len(); ++i) {
    order[degrees[i].Dat] = i;
  }
}

void MotifCluster::EdgeMotifAdjacency ( PNGraph  graph, WeightVH &  weights  )

staticprivate

Definition at line 443 of file motifcluster.cpp.

                                                                      {
  for (TNGraph::TEdgeI it = graph->BegEI(); it < graph->EndEI(); it++) {
    int src = it.GetSrcNId();    
    int dst = it.GetDstNId();
    if (src == dst) {
      continue;
    }
    // Only count reciprocated edges if src < dst
    if (!graph->IsEdge(dst, src) || src < dst) {
      IncrementWeight(src, dst, weights);
    }
  }
}

void MotifCluster::EdgeMotifAdjacency ( PUNGraph  graph, WeightVH &  weights  )

staticprivate

Definition at line 457 of file motifcluster.cpp.

                                                                       {
  for (TUNGraph::TEdgeI it = graph->BegEI(); it < graph->EndEI(); it++) {
    int src = it.GetSrcNId();    
    int dst = it.GetDstNId();
    if (src == dst) {
      continue;
    }
    IncrementWeight(src, dst, weights);
  }
}

void MotifCluster::GetMotifCluster ( PNGraph  graph, MotifType  motif, TSweepCut &  sweepcut, double  tol = kDefaultTol, int  maxiter = kMaxIter  )

static

Definition at line 701 of file motifcluster.cpp.

                                                {
  WeightVH weights;
  MotifAdjacency(graph, motif, weights);
  SpectralCut(weights, sweepcut, tol, maxiter);
}

void MotifCluster::GetMotifCluster ( PUNGraph  graph, MotifType  motif, TSweepCut &  sweepcut, double  tol = kDefaultTol, int  maxiter = kMaxIter  )

static

Definition at line 709 of file motifcluster.cpp.

                                                {
  WeightVH weights;
  MotifAdjacency(graph, motif, weights);
  SpectralCut(weights, sweepcut, tol, maxiter);
}

bool MotifCluster::IsBidirEdge ( PNGraph  graph, int  u, int  v  )

static

Definition at line 80 of file motifcluster.cpp.

                                                          {
  return graph->IsEdge(u, v) && graph->IsEdge(v, u);
}

bool MotifCluster::IsMotifM1 ( PNGraph  graph, int  u, int  v, int  w  )

static

Definition at line 84 of file motifcluster.cpp.

                                                               {
  return ((IsUnidirEdge(graph, u, v) && IsUnidirEdge(graph, v, w) &&
           IsUnidirEdge(graph, w, u)) ||
          (IsUnidirEdge(graph, u, w) && IsUnidirEdge(graph, w, v) &&
           IsUnidirEdge(graph, v, u)));
}

bool MotifCluster::IsMotifM10 ( PNGraph  graph, int  center, int  v, int  w  )

static

Definition at line 160 of file motifcluster.cpp.

                                                                     {
  return IsNoEdge(graph, v, w) && IsUnidirEdge(graph, v, center) &&
    IsUnidirEdge(graph, w, center);
}

bool MotifCluster::IsMotifM11 ( PNGraph  graph, int  center, int  v, int  w  )

static

Definition at line 165 of file motifcluster.cpp.

                                                                     {
  return IsNoEdge(graph, v, w) &&
    ((IsBidirEdge(graph, center, v) && IsUnidirEdge(graph, center, w)) ||
     (IsBidirEdge(graph, center, w) && IsUnidirEdge(graph, center, v)));
}

bool MotifCluster::IsMotifM12 ( PNGraph  graph, int  center, int  v, int  w  )

static

Definition at line 171 of file motifcluster.cpp.

                                                                     {
  return IsNoEdge(graph, v, w) &&
    ((IsBidirEdge(graph, center, v) && IsUnidirEdge(graph, w, center)) ||
     (IsBidirEdge(graph, center, w) && IsUnidirEdge(graph, v, center)));
}

bool MotifCluster::IsMotifM13 ( PNGraph  graph, int  center, int  v, int  w  )

static

Definition at line 177 of file motifcluster.cpp.

                                                                     {
  return IsNoEdge(graph, v, w) && IsBidirEdge(graph, center, v)
    && IsBidirEdge(graph, center, w);
}

bool MotifCluster::IsMotifM2 ( PNGraph  graph, int  u, int  v, int  w  )

static

Definition at line 91 of file motifcluster.cpp.

                                                               {
  return ((IsBidirEdge(graph, u, v) && IsUnidirEdge(graph, u, w) &&
           IsUnidirEdge(graph, w, v)) ||
          (IsBidirEdge(graph, u, v) && IsUnidirEdge(graph, w, u) &&
           IsUnidirEdge(graph, v, w)) ||
          (IsBidirEdge(graph, u, w) && IsUnidirEdge(graph, u, v) &&
           IsUnidirEdge(graph, v, w)) ||
          (IsBidirEdge(graph, u, w) && IsUnidirEdge(graph, v, u) &&
           IsUnidirEdge(graph, w, v)) ||
          (IsBidirEdge(graph, v, w) && IsUnidirEdge(graph, v, u) &&
           IsUnidirEdge(graph, u, w)) ||
          (IsBidirEdge(graph, v, w) && IsUnidirEdge(graph, u, v) &&
           IsUnidirEdge(graph, w, u)));
}

bool MotifCluster::IsMotifM3 ( PNGraph  graph, int  u, int  v, int  w  )

static

Definition at line 106 of file motifcluster.cpp.

                                                               {
  if ((IsBidirEdge( graph, u, v) && IsBidirEdge( graph, v, w)) &&
      (IsUnidirEdge(graph, u, w) || IsUnidirEdge(graph, w, u))) { return true; }
  if ((IsBidirEdge( graph, u, w) && IsBidirEdge( graph, w, v)) &&
      (IsUnidirEdge(graph, u, v) || IsUnidirEdge(graph, v, u))) { return true; }
  if ((IsBidirEdge( graph, w, u) && IsBidirEdge( graph, u, v)) &&
      (IsUnidirEdge(graph, w, v) || IsUnidirEdge(graph, v, w))) { return true; }
  return false;
}

bool MotifCluster::IsMotifM4 ( PNGraph  graph, int  u, int  v, int  w  )

static

Definition at line 116 of file motifcluster.cpp.

                                                               {
  return IsBidirEdge(graph, u, v) && IsBidirEdge(graph, u, w) &&
    IsBidirEdge(graph, v, w);
}

bool MotifCluster::IsMotifM5 ( PNGraph  graph, int  u, int  v, int  w  )

static

Definition at line 121 of file motifcluster.cpp.

                                                               {
  if ((IsUnidirEdge(graph, u, v) && IsUnidirEdge(graph, u, w)) && 
      (IsUnidirEdge(graph, v, w) || IsUnidirEdge(graph, w, v))) { return true; }
  if ((IsUnidirEdge(graph, v, u) && IsUnidirEdge(graph, v, w)) && 
      (IsUnidirEdge(graph, u, w) || IsUnidirEdge(graph, w, u))) { return true; }
  if ((IsUnidirEdge(graph, w, v) && IsUnidirEdge(graph, w, u)) && 
      (IsUnidirEdge(graph, v, u) || IsUnidirEdge(graph, u, v))) { return true; }
  return false;
}

bool MotifCluster::IsMotifM6 ( PNGraph  graph, int  u, int  v, int  w  )

static

Definition at line 131 of file motifcluster.cpp.

                                                               {
  return ((IsUnidirEdge(graph, u, v) && IsUnidirEdge(graph, u, w) &&
           IsBidirEdge(graph, v, w)) ||
          (IsUnidirEdge(graph, v, u) && IsUnidirEdge(graph, v, w) &&
           IsBidirEdge(graph, u, w)) ||
          (IsUnidirEdge(graph, w, u) && IsUnidirEdge(graph, w, v) &&
           IsBidirEdge(graph, u, v)));
}

bool MotifCluster::IsMotifM7 ( PNGraph  graph, int  u, int  v, int  w  )

static

Definition at line 140 of file motifcluster.cpp.

                                                               {
  return ((IsUnidirEdge(graph, v, u) && IsUnidirEdge(graph, w, u) &&
           IsBidirEdge(graph, v, w)) ||
          (IsUnidirEdge(graph, u, v) && IsUnidirEdge(graph, w, v) &&
           IsBidirEdge(graph, u, w)) ||
          (IsUnidirEdge(graph, u, w) && IsUnidirEdge(graph, v, w) &&
           IsBidirEdge(graph, u, v)));
}

bool MotifCluster::IsMotifM8 ( PNGraph  graph, int  center, int  v, int  w  )

static

Definition at line 149 of file motifcluster.cpp.

                                                                    {
  return IsNoEdge(graph, v, w) && IsUnidirEdge(graph, center, v) &&
    IsUnidirEdge(graph, center, w);
}

bool MotifCluster::IsMotifM9 ( PNGraph  graph, int  center, int  v, int  w  )

static

Definition at line 154 of file motifcluster.cpp.

                                                                    {
  return IsNoEdge(graph, v, w) &&
    ((IsUnidirEdge(graph, center, v) && IsUnidirEdge(graph, w, center)) ||
     (IsUnidirEdge(graph, center, w) && IsUnidirEdge(graph, v, center)));
}

bool MotifCluster::IsNoEdge ( PNGraph  graph, int  u, int  v  )

static

Definition at line 72 of file motifcluster.cpp.

                                                       {
  return !graph->IsEdge(u, v) && !graph->IsEdge(v, u);
}

bool MotifCluster::IsUnidirEdge ( PNGraph  graph, int  u, int  v  )

static

Definition at line 76 of file motifcluster.cpp.

                                                           {
  return graph->IsEdge(u, v) && !graph->IsEdge(v, u);
}

void MotifCluster::MotifAdjacency ( PNGraph  graph, MotifType  motif, WeightVH &  weights  )

static

Definition at line 471 of file motifcluster.cpp.

                                                     {
  weights = WeightVH(graph->GetMxNId() + 1);
  switch (motif) {
  case M1:
  case M2:
  case M3:
  case M4:
  case M5:
  case M6:
  case M7:
    TriangleMotifAdjacency(graph, motif, weights);
    break;
  case M8:
  case M9:
  case M10:
  case M11:
  case M12:
  case M13:
    WedgeMotifAdjacency(graph, motif, weights);
    break;    
  case bifan:
    BifanMotifAdjacency(graph, weights);
    break;
  case edge:
    EdgeMotifAdjacency(graph, weights);
    break;
  default:
    TExcept::Throw("Unknown directed motif type");
  }
}

void MotifCluster::MotifAdjacency ( PUNGraph  graph, MotifType  motif, WeightVH &  weights  )

static

Definition at line 510 of file motifcluster.cpp.

                                                     {
  weights = WeightVH(graph->GetMxNId() + 1);
  switch (motif) {
  case triangle:
  case clique3:
    CliqueMotifAdjacency(graph, 3, weights);
    break;
  case clique4:
    CliqueMotifAdjacency(graph, 4, weights);
    break;
  case clique5:
    CliqueMotifAdjacency(graph, 5, weights);
    break;    
  case clique6:
    CliqueMotifAdjacency(graph, 6, weights);
    break;    
  case clique7:
    CliqueMotifAdjacency(graph, 7, weights);
    break;    
  case clique8:
    CliqueMotifAdjacency(graph, 8, weights);
    break;    
  case clique9:
    CliqueMotifAdjacency(graph, 9, weights);
    break;
  case semiclique:
    SemicliqueMotifAdjacency(graph, weights);
    break;
  case edge:
    EdgeMotifAdjacency(graph, weights);
  default:
    TExcept::Throw("Unknown undirected motif type");
  }
}

double MotifCluster::NFiedlerVector ( const TSparseColMatrix &  W, TFltV &  fvec, double  tol = kDefaultTol, int  maxiter = kMaxIter  )

static

Definition at line 717 of file motifcluster.cpp.

                                                             {
  if (W.GetRows() != W.GetCols()) {
    TExcept::Throw("Matrix must be square.");
  }

  int N = W.GetCols();
  
  // all ones vector
  TFltV e(N);
  e.PutAll(1.0);
  // degree vector
  TFltV d(N);
  d.PutAll(0.0);
  W.Multiply(e, d);

  // Unit first eigenvector and d^{-1/2}
  TFltV v0(N);
  TFltV dnorm(N);
  for (int i = 0; i < d.Len(); i++) {
    if (d[i] <= 0.0) {
      TExcept::Throw("Node with zero degree.");
    }
    v0[i] = TMath::Sqrt(d[i]);
    dnorm[i] = 1.0 / TMath::Sqrt(d[i]);
  }
  TLinAlg::Normalize(v0);

  // Form I + Ln, where Ln is normalized Laplacian
  TVec< TIntFltKdV > L_weights(N);
  for (int j = 0; j < N; j++) {
    const TIntFltKdV& W_col = W.ColSpVV[j];
    TIntFltKdV& L_col = L_weights[j];
    for (int ind = 0; ind < W_col.Len(); ind++) {
      int i = W_col[ind].Key;
      double val = W_col[ind].Dat;
      L_col.Add(TIntFltKd(i, -val * dnorm[i] * dnorm[j]));
    }
    L_col.Add(TIntFltKd(j, 2.0));    
  }

  TSparseColMatrix L(L_weights, N, N);
  TFltV evals;
  TFullColMatrix evecs;
  SymeigsSmallest(L, 2, evals, evecs, tol, maxiter);
  fvec = evecs.ColV[1];
  for (int i = 0; i < fvec.Len(); i++) {
    fvec[i] *= dnorm[i];
  }
  // Adjust by 1 on the eigenvalue since we added the identity
  return evals[1] - 1;
}

MotifType MotifCluster::ParseMotifType ( const TStr &  motif )

static

Definition at line 36 of file motifcluster.cpp.

                                                        {
  TStr motif_lc = motif.GetLc();
  if      (motif_lc == "m1")          { return M1; }
  else if (motif_lc == "m2")          { return M2; }
  else if (motif_lc == "m3")          { return M3; }
  else if (motif_lc == "m4")          { return M4; }
  else if (motif_lc == "m5")          { return M5; }
  else if (motif_lc == "m6")          { return M6; }
  else if (motif_lc == "m7")          { return M7; }
  else if (motif_lc == "m8")          { return M8; }
  else if (motif_lc == "m9")          { return M9; }
  else if (motif_lc == "m10")         { return M10; }
  else if (motif_lc == "m11")         { return M11; }
  else if (motif_lc == "m12")         { return M12; }
  else if (motif_lc == "m13")         { return M13; }
  else if (motif_lc == "bifan")       { return bifan; }
  else if (motif_lc == "bi-fan")      { return bifan; }  
  else if (motif_lc == "triangle")    { return triangle; }
  else if (motif_lc == "clique3")     { return clique3; }
  else if (motif_lc == "clique4")     { return clique4; }
  else if (motif_lc == "clique5")     { return clique5; }
  else if (motif_lc == "clique6")     { return clique6; }
  else if (motif_lc == "clique7")     { return clique7; }
  else if (motif_lc == "clique8")     { return clique8; }
  else if (motif_lc == "clique9")     { return clique9; }
  else if (motif_lc == "semiclique")  { return semiclique; }
  else if (motif_lc == "semi-clique") { return semiclique; }    
  else if (motif_lc == "edge")        { return edge; }
  else if (motif_lc == "undir")       { return edge; }
  else if (motif_lc == "undirected")  { return edge; }
  else { TExcept::Throw("Unknown motif"); }
  return edge;
}

void MotifCluster::SemicliqueMotifAdjacency ( PUNGraph  graph, WeightVH &  weights  )

staticprivate

Definition at line 405 of file motifcluster.cpp.

                                                                             {
  for (TUNGraph::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++) {  
    int src = NI.GetId();
    for (int j = 0; j < NI.GetDeg(); j++) {
      int dst = NI.GetNbrNId(j);
      if (dst <= src) { continue; }

      // Common neighbors of dst that are neighbors of src
      TIntV common;
      TUNGraph::TNodeI dst_NI = graph->GetNI(dst);
      for (int k = 0; k < dst_NI.GetOutDeg(); k++) {
        int nbr = dst_NI.GetNbrNId(k);
        if (nbr != src && nbr != dst && NI.IsNbrNId(nbr)) {
          common.Add(nbr);
        }
      }
      
      for (int k = 0; k < common.Len(); k++) {
        for (int l = k + 1; l < common.Len(); l++) {
          int nbr1 = common[k];
          int nbr2 = common[l];
          if (!graph->IsEdge(nbr1, nbr2)) {
            IncrementWeight(src, dst, weights);
            IncrementWeight(src, nbr1, weights);
            IncrementWeight(src, nbr2, weights);            
            IncrementWeight(dst, nbr1, weights);
            IncrementWeight(dst, nbr2, weights);
            IncrementWeight(nbr1, nbr2, weights);
          }
        }
      }
    }
  }
}

void MotifCluster::SpectralCut ( const WeightVH &  weights, TSweepCut &  sweepcut, double  tol = kDefaultTol, int  maxiter = kMaxIter  )

static

Definition at line 871 of file motifcluster.cpp.

                                                        {
  // Form graph and get maximum component
  PUNGraph graph = UnweightedGraphRepresentation(weights);
  TCnComV components;
  TSnap::GetWccs(graph, components);
  int max_wcc_size = 0;
  int max_wcc_ind = -1;
  for (int i = 0; i < components.Len(); i++) {
    int size = components[i].Len();
    if (size > max_wcc_size) {
      max_wcc_size = size;
      max_wcc_ind = i;
    }
  }
  TCnCom comp = components[max_wcc_ind];
  sweepcut.component = comp;
  if (comp.Len() == 1) {
    printf("WARNING: No non-trivial connected components "
           "(likely due to no instances of the motif)\n");
    sweepcut.cond = 0;
    sweepcut.eig = 0;
    return;
  }
  

  // Map largest connected component to a matrix, keeping track of ids.
  THash<TInt, TInt> id_map;
  TIntV rev_id_map;
  MapIdsToFirstN(comp.NIdV, id_map, rev_id_map);

  TVec<TIntFltKdV> matrix_entries(comp.Len());
  for (int ind1 = 0; ind1 < comp.Len(); ++ind1) {
    int c_ind = comp[ind1];
    const THash<TInt, TInt>& edge_list = weights[c_ind];
    int i_ind = id_map(c_ind);
    TIntFltKdV& col = matrix_entries[i_ind];
    for (THash<TInt, TInt>::TIter it = edge_list.BegI(); it < edge_list.EndI();
         it++) {
      int ind2 = it->Key;
      int val = it->Dat;
      if (comp.IsNIdIn(ind2)) {
        int j_ind = id_map(ind2);
        col.Add(TIntFltKd(j_ind, val));
        // Add symmetric part
        matrix_entries[j_ind].Add(TIntFltKd(i_ind, val));
      }
    }
  }

  // Get Fiedler vector and run the sweep
  TSparseColMatrix W(matrix_entries, comp.Len(), comp.Len());
  TFltV fvec;
  sweepcut.eig = NFiedlerVector(W, fvec, tol, maxiter);

  TFltV conds;
  TIntV order;
  Sweep(W, fvec, conds, order);
  sweepcut.sweep_profile = conds;

  // Extract the cluster
  double min_cond = 2.0;
  int min_ind = -1;
  for (int i = 0; i < conds.Len(); i++) {
    double cond = conds[i];
    if (cond < min_cond) {
      min_cond = cond;
      min_ind = i;
    }
  }
  sweepcut.cond = min_cond;
  TIntV cluster;
  int start = 0;
  int end = min_ind + 1;
  if (end >= conds.Len() / 2) {
    start = min_ind + 1;
    end = conds.Len() + 1;
  }
  for (int i = start; i < end; i++) {
    cluster.Add(rev_id_map[order[i]]);    
  }
  sweepcut.cluster = cluster;
}

void MotifCluster::TriangleMotifAdjacency ( PNGraph  graph, MotifType  motif, WeightVH &  weights  )

staticprivate

Definition at line 213 of file motifcluster.cpp.

                                                             {
  TIntV order;
  DegreeOrdering(graph, order);
  for (TNGraph::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++) {
    int src = NI.GetId();
    int src_pos = order[src];
    
    // Get all neighbors who come later in the ordering
    TIntV neighbors_higher;
    for (int i = 0; i < NI.GetOutDeg(); i++) {
      int nbr = NI.GetOutNId(i);
      if (order[nbr] > src_pos) {
        neighbors_higher.Add(nbr);
      }
    }
    for (int i = 0; i < NI.GetInDeg(); i++) {
      int nbr = NI.GetInNId(i);
      if (!NI.IsOutNId(nbr) && order[nbr] > src_pos) {
        neighbors_higher.Add(nbr);
      }
    }

    for (int ind1 = 0; ind1 < neighbors_higher.Len(); ind1++) {
      for (int ind2 = ind1 + 1; ind2 < neighbors_higher.Len(); ind2++) {
        int dst1 = neighbors_higher[ind1];
        int dst2 = neighbors_higher[ind2];
        // Check for triangle formation
        if (graph->IsEdge(dst1, dst2) || graph->IsEdge(dst2, dst1)) {
          bool motif_occurs = false;
          switch (motif) {
          case M1:
            motif_occurs = IsMotifM1(graph, src, dst1, dst2);
            break;
          case M2:
            motif_occurs = IsMotifM2(graph, src, dst1, dst2);
            break;
          case M3:
            motif_occurs = IsMotifM3(graph, src, dst1, dst2);
            break;
          case M4:
            motif_occurs = IsMotifM4(graph, src, dst1, dst2);
            break;
          case M5:
            motif_occurs = IsMotifM5(graph, src, dst1, dst2);
            break;
          case M6:
            motif_occurs = IsMotifM6(graph, src, dst1, dst2);
            break;
          case M7:
            motif_occurs = IsMotifM7(graph, src, dst1, dst2);
            break;
          default:
            TExcept::Throw("Unknown directed triangle motif");
          }
          // Increment weights of the triad (src, dst1, dst2) if it occurs.
          if (motif_occurs) {
            IncrementWeight(src,  dst1, weights);
            IncrementWeight(src,  dst2, weights);
            IncrementWeight(dst1, dst2, weights);
          }
        }
      }
    }
  }
}

void MotifCluster::WedgeMotifAdjacency ( PNGraph  graph, MotifType  motif, WeightVH &  weights  )

staticprivate

Definition at line 282 of file motifcluster.cpp.

                                                          {
  for (TNGraph::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++) {
    int center = NI.GetId();
    
    // Get all neighbors
    TIntV neighbors;
    for (int i = 0; i < NI.GetOutDeg(); i++) {
      int nbr = NI.GetOutNId(i);
      neighbors.Add(nbr);
    }
    for (int i = 0; i < NI.GetInDeg(); i++) {
      int nbr = NI.GetInNId(i);
      if (!NI.IsOutNId(nbr)) {
        neighbors.Add(nbr);
      }
    }

    for (int ind1 = 0; ind1 < neighbors.Len(); ind1++) {
      for (int ind2 = ind1 + 1; ind2 < neighbors.Len(); ind2++) {
        int dst1 = neighbors[ind1];
        int dst2 = neighbors[ind2];
        bool motif_occurs = false;
        switch (motif) {
        case M8:
          motif_occurs = IsMotifM8(graph, center, dst1, dst2);
          break;
        case M9:
          motif_occurs = IsMotifM9(graph, center, dst1, dst2);
          break;
        case M10:
          motif_occurs = IsMotifM10(graph, center, dst1, dst2);
          break;
        case M11:
          motif_occurs = IsMotifM11(graph, center, dst1, dst2);
          break;
        case M12:
          motif_occurs = IsMotifM12(graph, center, dst1, dst2);
          break;
        case M13:
          motif_occurs = IsMotifM13(graph, center, dst1, dst2);
          break;
        default:
          TExcept::Throw("Unknown directed wedge motif");
        }
        // Increment weights of (center, dst1, dst2) if it occurs.
        if (motif_occurs) {
          IncrementWeight(center, dst1, weights);
          IncrementWeight(center, dst2, weights);
          IncrementWeight(dst1,   dst2, weights);
        }
      }
    }
  }
}

---

The documentation for this class was generated from the following files:

• snap-adv/motifcluster.h
• snap-adv/motifcluster.cpp