ChibaNishizekiWeighter Class Reference

#include <motifcluster.h>

Public Member Functions
	ChibaNishizekiWeighter (PUNGraph graph)
void	Run (int k)
WeightVH &	weights ()

Private Member Functions
void	SubgraphDegreeOrder (int k, const TIntV &U, TIntV &order)
void	UpdateWeights (const TIntV &clique)
void	FlushCliques (const TIntV &U)
void	CliqueEnum (int k, const TIntV &U)
void	AdjustLabels (int kcurr, int klast, const TIntV &U)
void	Initialize (int k)

Private Attributes
TVec< TVec< TIntV > >	graph_
TIntV	labels_
TIntV	C_
int	k_
PUNGraph	orig_graph_
WeightVH	weights_

Detailed Description

Definition at line 155 of file motifcluster.h.

Constructor & Destructor Documentation

ChibaNishizekiWeighter::ChibaNishizekiWeighter ( PUNGraph  graph )

inline

Definition at line 157 of file motifcluster.h.

: orig_graph_(graph) {}

Member Function Documentation

void ChibaNishizekiWeighter::AdjustLabels ( int  kcurr, int  klast, const TIntV &  U  )

private

Definition at line 644 of file motifcluster.cpp.

                                                                               {
  for (int i = 0; i < Up.Len(); i++) {
    int node = Up[i];
    TIntV& nbrs_kcurr = graph_[kcurr][node];
    TIntV& nbrs_klast = graph_[klast][node];
    TIntV nbrs_klast_new;
    for (int j = 0; j < nbrs_klast.Len(); j++) {
      int nbr = nbrs_klast[j];
      if (labels_[nbr] == kcurr) {
        nbrs_kcurr.Add(nbr);
      } else {
        nbrs_klast_new.Add(nbr);
      }
    }
    graph_[klast][node] = nbrs_klast_new;
  }
}

void ChibaNishizekiWeighter::CliqueEnum ( int  k, const TIntV &  U  )

private

Definition at line 662 of file motifcluster.cpp.

                                                             {
  // Handle base case
  if (k == 2) {
    FlushCliques(U);
    return;
  }

  // Get the degrees of nodes in U
  TIntV order;
  SubgraphDegreeOrder(k, U, order);
  for (int i = 0; i < order.Len(); i++) {
    int vi = order[i];
    // Get neighbors of current node in the subgraph
    TIntV& U_prime = graph_[k][vi];

    // Re-label
    for (int j = 0; j < U_prime.Len(); j++) {
      labels_[U_prime[j]] = k - 1;
    }
    AdjustLabels(k - 1, k, U_prime);

    // Recurse
    C_.Add(vi);
    CliqueEnum(k - 1, U_prime);
    C_.DelLast();

    // Re-label
    for (int j = 0; j < U_prime.Len(); j++) {
      labels_[U_prime[j]] = k;
    }
    AdjustLabels(k, k - 1, U_prime);
    labels_[vi] = k + 1;
    AdjustLabels(k + 1, k, U_prime);
  }
}

void ChibaNishizekiWeighter::FlushCliques ( const TIntV &  U )

private

Definition at line 624 of file motifcluster.cpp.

                                                        {
  for (int i = 0; i < U.Len(); i++) {
    int node = U[i];
    TIntV& nbrs = graph_[2][node];
    for (int j = 0; j < nbrs.Len(); j++) {
      int nbr = nbrs[j];
      // Only count each edge once
      if (node < nbr) {
        TIntV clique(C_.Len() + 2);
        clique[0] = node;
        clique[1] = nbr;
        for (int k = 0; k < C_.Len(); k++) {
          clique[k + 2] = C_[k];
        }
        UpdateWeights(clique);
      }
    }
  }
}

void ChibaNishizekiWeighter::Initialize ( int  k )

private

Definition at line 549 of file motifcluster.cpp.

                                             {
  k_ = k;
  C_.Clr();

  // Process the k - 1 core
  PUNGraph kcore = TSnap::GetKCore(orig_graph_, k - 1);
  TSnap::DelSelfEdges(kcore);
  int max_nodes = kcore->GetMxNId();
  for (int i = 0; i <= max_nodes; i++) {
    if (!kcore->IsNode(i)) {
      kcore->AddNode(i);
    }
  }

  int N = kcore->GetNodes();
  weights_ = WeightVH(N);
  graph_ = TVec < TVec<TIntV> >(k + 2);
  for (int i = 0; i < k + 2; ++i) {
    graph_[i] = TVec<TIntV>(N);
  }
  labels_ = TIntV(N);
  labels_.PutAll(k);
  
  TVec<TIntV>& graph_k = graph_[k];
  for (int src = 0; src < N; src++) {
    TUNGraph::TNodeI src_it = kcore->GetNI(src);
    int deg = src_it.GetDeg();
    graph_k[src] = TIntV(deg);
    for (int edge = 0; edge < deg; edge++) {
      int dst = src_it.GetNbrNId(edge);
      graph_k[src][edge] = dst;
    }
  }
}

void ChibaNishizekiWeighter::Run

(

int

k

)

Definition at line 584 of file motifcluster.cpp.

                                      {
  Initialize(k);
  TIntV U(graph_[k].Len());
  for (int i = 0; i < U.Len(); i++) {
    U[i] = i;
  }
  CliqueEnum(k, U);
}

void ChibaNishizekiWeighter::SubgraphDegreeOrder ( int  k, const TIntV &  U, TIntV &  order  )

private

Definition at line 593 of file motifcluster.cpp.

                                                               {
  TVec< TKeyDat<TInt, TInt> > degs(U.Len());
  int end_size = 0;
  for (int i = 0; i < U.Len(); i++) {
    int node = U[i];
    int size = graph_[k][node].Len();
    if (size > 0) {
      degs[end_size] = TKeyDat<TInt, TInt>(-size, node);
      ++end_size;
    }
  }
  // Only keep nodes with degree > 0  
  degs.Trunc(end_size);
  // Sort by increasing degree
  degs.Sort();

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

void ChibaNishizekiWeighter::UpdateWeights ( const TIntV &  clique )

private

Definition at line 616 of file motifcluster.cpp.

                                                              {
  for (int i = 0; i < clique.Len(); ++i) {
    for (int j = i + 1; j < clique.Len(); ++j) {
      IncrementWeight(clique[i], clique[j], weights_);
    }
  }
}

WeightVH& ChibaNishizekiWeighter::weights ( )

inline

Definition at line 163 of file motifcluster.h.

{ return weights_; }

Member Data Documentation

TIntV ChibaNishizekiWeighter::C_

private

Definition at line 185 of file motifcluster.h.

TVec< TVec<TIntV> > ChibaNishizekiWeighter::graph_

private

Definition at line 183 of file motifcluster.h.

int ChibaNishizekiWeighter::k_

private

Definition at line 186 of file motifcluster.h.

TIntV ChibaNishizekiWeighter::labels_

private

Definition at line 184 of file motifcluster.h.

PUNGraph ChibaNishizekiWeighter::orig_graph_

private

Definition at line 187 of file motifcluster.h.

WeightVH ChibaNishizekiWeighter::weights_

private

Definition at line 188 of file motifcluster.h.

---

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

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