#include <motifcluster.h>

Collaboration diagram for ChibaNishizekiWeighter:

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.

157 : orig_graph_(graph) {}

ChibaNishizekiWeighter::orig_graph_

PUNGraph orig_graph_

Definition: motifcluster.h:187

Member Function Documentation

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

private

Definition at line 644 of file motifcluster.cpp.

References TVec< TVal, TSizeTy >::Add(), graph_, labels_, and TVec< TVal, TSizeTy >::Len().

Referenced by CliqueEnum().

                                                                                {
   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;
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

private

Definition at line 662 of file motifcluster.cpp.

References TVec< TVal, TSizeTy >::Add(), AdjustLabels(), C_, TVec< TVal, TSizeTy >::DelLast(), FlushCliques(), graph_, labels_, TVec< TVal, TSizeTy >::Len(), and SubgraphDegreeOrder().

Referenced by Run().

                                                              {
   // 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);
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void ChibaNishizekiWeighter::FlushCliques ( const TIntV & U )

private

Definition at line 624 of file motifcluster.cpp.

References C_, graph_, TVec< TVal, TSizeTy >::Len(), and UpdateWeights().

Referenced by CliqueEnum().

                                                         {
   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);
       }
     }
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void ChibaNishizekiWeighter::Initialize ( int k )

private

Definition at line 549 of file motifcluster.cpp.

References TUNGraph::AddNode(), C_, TVec< TVal, TSizeTy >::Clr(), TSnap::DelSelfEdges(), edge, TUNGraph::TNodeI::GetDeg(), TSnap::GetKCore(), TUNGraph::GetMxNId(), TUNGraph::TNodeI::GetNbrNId(), TUNGraph::GetNI(), TUNGraph::GetNodes(), graph_, TUNGraph::IsNode(), k_, labels_, orig_graph_, TVec< TVal, TSizeTy >::PutAll(), and weights_.

Referenced by Run().

                                              {
   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;
     }
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void ChibaNishizekiWeighter::Run ( int k )

Definition at line 584 of file motifcluster.cpp.

References CliqueEnum(), graph_, Initialize(), and TVec< TVal, TSizeTy >::Len().

Referenced by MotifCluster::CliqueMotifAdjacency().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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

private

Definition at line 593 of file motifcluster.cpp.

References graph_, TVec< TVal, TSizeTy >::Len(), and TVec< TVal, TSizeTy >::Trunc().

Referenced by CliqueEnum().

                                                                {
   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;
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void ChibaNishizekiWeighter::UpdateWeights ( const TIntV & clique )

private

Definition at line 616 of file motifcluster.cpp.

References IncrementWeight(), TVec< TVal, TSizeTy >::Len(), and weights_.

Referenced by FlushCliques().

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