TCliqueOverlap Class Reference

#include <cliques.h>

Collaboration diagram for TCliqueOverlap:

Public Member Functions
	TCliqueOverlap ()
void	GetMaximalCliques (const PUNGraph &G, int MinMaxCliqueSize, TVec< TIntV > &MaxCliques)

Static Public Member Functions
static void	GetRelativeComplement (const THashSet< TInt > &A, const THashSet< TInt > &B, THashSet< TInt > &Complement)
static void	GetIntersection (const THashSet< TInt > &A, const THashSet< TInt > &B, THashSet< TInt > &C)
static int	Intersection (const THashSet< TInt > &A, const THashSet< TInt > &B)
static void	CalculateOverlapMtx (const TVec< TIntV > &MaxCliques, int MinNodeOverlap, TVec< TIntV > &OverlapMtx)
static PUNGraph	CalculateOverlapMtx (const TVec< TIntV > &MaxCliques, int MinNodeOverlap)
static void	GetOverlapCliques (const TVec< TIntV > &OverlapMtx, int MinNodeOverlap, TVec< TIntV > &CliqueIdVV)
static void	GetOverlapCliques (const TVec< TIntV > &OverlapMtx, const TVec< TIntV > &MaxCliques, double MinOverlapFrac, TVec< TIntV > &CliqueIdVV)
static void	GetMaxCliques (const PUNGraph &G, int MinMaxCliqueSize, TVec< TIntV > &MaxCliques)
	Enumerate maximal cliques of the network on more than MinMaxCliqueSize nodes. More...
static void	GetCPMCommunities (const PUNGraph &G, int MinMaxCliqueSize, TVec< TIntV > &Communities)
	Clique Percolation method communities. More...

Private Member Functions
void	GetNbrs (int NId, THashSet< TInt > &Nbrs) const
int	GetNodeIdWithMaxDeg (const THashSet< TInt > &Set) const
int	MaxNbrsInCANDNodeId (const THashSet< TInt > &SUBG, const THashSet< TInt > &CAND) const
void	Expand (const THashSet< TInt > &SUBG, THashSet< TInt > &CAND)

Private Attributes
PUNGraph	m_G
TIntV	m_Q
TVec< TIntV > *	m_maxCliques
int	m_minMaxCliqueSize

Detailed Description

Definition at line 8 of file cliques.h.

Constructor & Destructor Documentation

TCliqueOverlap::TCliqueOverlap ( )

inline

Definition at line 29 of file cliques.h.

: m_G(), m_Q(), m_maxCliques(NULL), m_minMaxCliqueSize(3) { }

Member Function Documentation

void TCliqueOverlap::CalculateOverlapMtx ( const TVec< TIntV > &  MaxCliques, int  MinNodeOverlap, TVec< TIntV > &  OverlapMtx  )

static

Definition at line 127 of file cliques.cpp.

References TVec< TVal, TSizeTy >::Add(), THashSet< TKey, THashFunc >::AddKey(), TVec< TVal, TSizeTy >::Clr(), TVec< TVal, TSizeTy >::Gen(), THashSet< TKey, THashFunc >::Gen(), Intersection(), TVec< TVal, TSizeTy >::Last(), and TVec< TVal, TSizeTy >::Len().

Referenced by GetCPMCommunities().

                                                                                                                   {
        OverlapMtx.Clr();
        //
        int n = MaxCliques.Len();
        //Convert max cliques to HashSets
                TVec<THashSet<TInt> > cliques;
        for (int i=0; i<n; i++) {
                const int len = MaxCliques[i].Len();
    cliques.Add();
    if (len < MinNodeOverlap) { continue; }
                THashSet<TInt>& set = cliques.Last();  set.Gen(len);
    for (int j=0; j<len; j++) { set.AddKey(MaxCliques[i][j]); }
        }
        //Init clique clique overlap matrix
        n = cliques.Len();
        OverlapMtx.Gen(n);
        for (int i=0; i<n; i++) OverlapMtx[i].Gen(n);
        //Calculate clique clique overlap matrix
  for (int i=0; i<n; i++) {
    OverlapMtx[i][i] = cliques[i].Len();
    for (int j=i+1; j<n; j++) {
      OverlapMtx[i][j] = Intersection(cliques[i], cliques[j]); }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

PUNGraph TCliqueOverlap::CalculateOverlapMtx ( const TVec< TIntV > &  MaxCliques, int  MinNodeOverlap  )

static

Definition at line 152 of file cliques.cpp.

References TVec< TVal, TSizeTy >::Add(), TUNGraph::AddEdge(), THashSet< TKey, THashFunc >::AddKey(), TUNGraph::AddNode(), THashSet< TKey, THashFunc >::Gen(), Intersection(), TVec< TVal, TSizeTy >::Last(), TVec< TVal, TSizeTy >::Len(), and TUNGraph::New().

                                                                                              {
        const int n = MaxCliques.Len();
  //Convert max cliques to HashSets
        TVec<THashSet<TInt> > cliques;
        for (int i=0; i<n; i++) {
                const int len = MaxCliques[i].Len();
    cliques.Add();
    if (len < MinNodeOverlap) { continue; }
                THashSet<TInt>& set = cliques.Last();  set.Gen(len);
    for (int j=0; j<len; j++) { set.AddKey(MaxCliques[i][j]); }
        }
        //Init clique clique overlap matrix
        PUNGraph OverlapMtx = TUNGraph::New();
  for (int i=0; i < n; i++) {
    OverlapMtx->AddNode(i); }
        //Calculate clique clique overlap matrix
  for (int i=0; i<n; i++) {
    for (int j=i+1; j<n; j++) {
      if (Intersection(cliques[i], cliques[j]) >= MinNodeOverlap) {
        OverlapMtx->AddEdge(i,j); }
    }
  }
  return OverlapMtx;
}

Here is the call graph for this function:

void TCliqueOverlap::Expand ( const THashSet< TInt > &  SUBG, THashSet< TInt > &  CAND  )

private

Definition at line 73 of file cliques.cpp.

References TVec< TVal, TSizeTy >::Add(), THashSet< TKey, THashFunc >::Clr(), THashSet< TKey, THashFunc >::DelKey(), TVec< TVal, TSizeTy >::DelLast(), GetIntersection(), GetNbrs(), GetNodeIdWithMaxDeg(), GetRelativeComplement(), TVec< TVal, TSizeTy >::Len(), THashSet< TKey, THashFunc >::Len(), m_maxCliques, m_minMaxCliqueSize, m_Q, MaxNbrsInCANDNodeId(), and TVec< TVal, TSizeTy >::Pack().

Referenced by GetMaximalCliques().

                                                                            {
        if (SUBG.Len()==0) { if (m_Q.Len() >= m_minMaxCliqueSize) { m_Q.Pack(); m_maxCliques->Add(m_Q); } return; }
        if (CAND.Len()==0) return;
        //Get u that maximaze CAND intersection with neighbours of vertex u
        int u = MaxNbrsInCANDNodeId(SUBG, CAND);
        //Get neighbours of node u
        THashSet<TInt> nbrsU;
        GetNbrs(u, nbrsU);
        //Get relative complement of nbrsU in CAND
        THashSet<TInt> EXT;
        GetRelativeComplement(CAND, nbrsU, EXT);
        while(EXT.Len() != 0) {
                int q = GetNodeIdWithMaxDeg(EXT);
                //
                m_Q.Add(q);
                //
                THashSet<TInt> nbrsQ;
                GetNbrs(q, nbrsQ);
                //
                THashSet<TInt> SUBGq;
                GetIntersection(SUBG, nbrsQ, SUBGq);
                //
                THashSet<TInt> CANDq;
                GetIntersection(CAND, nbrsQ, CANDq);
                //
                Expand(SUBGq, CANDq);
                //
                CAND.DelKey(q);
                m_Q.DelLast();
                //
                EXT.Clr();
                GetRelativeComplement(CAND, nbrsU, EXT);
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TCliqueOverlap::GetCPMCommunities ( const PUNGraph &  G, int  MinMaxCliqueSize, TVec< TIntV > &  Communities  )

static

Clique Percolation method communities.

Definition at line 224 of file cliques.cpp.

References TVec< TVal, TSizeTy >::Add(), THashSet< TKey, THashFunc >::AddKeyV(), CalculateOverlapMtx(), TVec< TVal, TSizeTy >::Clr(), THashSet< TKey, THashFunc >::Clr(), TUNGraph::GetEdges(), THashSet< TKey, THashFunc >::GetKeyV(), GetMaxCliques(), TUNGraph::GetNodes(), TExeTm::GetStr(), TSnap::GetWccs(), TVec< TVal, TSizeTy >::Last(), and TVec< TVal, TSizeTy >::Sort().

                                                                                                      {
  printf("Clique Percolation Method\n");
  TExeTm ExeTm;
  TVec<TIntV> MaxCliques;
  TCliqueOverlap::GetMaxCliques(G, MinMaxCliqueSize, MaxCliques);
  // op RS 2012/05/15, commented out next line, a parameter is missing,
  //   creating a warning on OS X
  // printf("...%d cliques found\n");
  // get clique overlap matrix (graph)
  PUNGraph OverlapGraph = TCliqueOverlap::CalculateOverlapMtx(MaxCliques, MinMaxCliqueSize-1);
  printf("...overlap matrix (%d, %d)\n", G->GetNodes(), G->GetEdges());
  // connected components are communities
  TCnComV CnComV;
  TSnap::GetWccs(OverlapGraph, CnComV);
  NIdCmtyVV.Clr(false);
  TIntSet CmtySet;
  for (int c = 0; c < CnComV.Len(); c++) {
    CmtySet.Clr(false);
    for (int i = 0; i <CnComV[c].Len(); i++) {
      const TIntV& CliqueNIdV = MaxCliques[CnComV[c][i]];
      CmtySet.AddKeyV(CliqueNIdV);
    }
    NIdCmtyVV.Add();
    CmtySet.GetKeyV(NIdCmtyVV.Last());
    NIdCmtyVV.Last().Sort();
  }
  printf("done [%s].\n", ExeTm.GetStr());
}

Here is the call graph for this function:

void TCliqueOverlap::GetIntersection ( const THashSet< TInt > &  A, const THashSet< TInt > &  B, THashSet< TInt > &  C  )

static

Definition at line 13 of file cliques.cpp.

References THashSet< TKey, THashFunc >::AddKey(), THashSet< TKey, THashFunc >::BegI(), THashSet< TKey, THashFunc >::EndI(), THashSet< TKey, THashFunc >::IsKey(), and THashSet< TKey, THashFunc >::Len().

Referenced by Expand().

                                                                                                        {
        if (A.Len() < B.Len()) {
                for (THashSetKeyI<TInt> it=A.BegI(); it<A.EndI(); it++) 
                        if (B.IsKey(it.GetKey())) C.AddKey(it.GetKey());
        } else {
                for (THashSetKeyI<TInt> it=B.BegI(); it<B.EndI(); it++) 
                        if (A.IsKey(it.GetKey())) C.AddKey(it.GetKey());
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TCliqueOverlap::GetMaxCliques ( const PUNGraph &  G, int  MinMaxCliqueSize, TVec< TIntV > &  MaxCliques  )

static

Enumerate maximal cliques of the network on more than MinMaxCliqueSize nodes.

Definition at line 217 of file cliques.cpp.

References TVec< TVal, TSizeTy >::Clr(), and GetMaximalCliques().

Referenced by GetCPMCommunities().

                                                                                                   {
  TCliqueOverlap CO;
  MaxCliques.Clr(false);
  CO.GetMaximalCliques(G, MinMaxCliqueSize, MaxCliques);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TCliqueOverlap::GetMaximalCliques	(	const PUNGraph &	G,
		int	MinMaxCliqueSize,
		TVec< TIntV > &	MaxCliques
	)

Definition at line 108 of file cliques.cpp.

References THashSet< TKey, THashFunc >::AddKey(), TUNGraph::BegNI(), TVec< TVal, TSizeTy >::Clr(), TUNGraph::EndNI(), Expand(), TUNGraph::GetNodes(), m_G, m_maxCliques, m_minMaxCliqueSize, and m_Q.

Referenced by GetMaxCliques().

                                                                                                       {
        if (G->GetNodes() == 0) return;
        //
        m_G = G;
        m_minMaxCliqueSize = MinMaxCliqueSize;
        m_maxCliques =& MaxCliques;
        m_Q.Clr();
        //
        THashSet<TInt> SUBG;
        THashSet<TInt> CAND;
        for (TUNGraph::TNodeI NI=m_G->BegNI(); NI<m_G->EndNI(); NI++) {
                TInt nId = NI.GetId();
                SUBG.AddKey(nId);
                CAND.AddKey(nId);
        }
        //
        Expand(SUBG, CAND);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TCliqueOverlap::GetNbrs ( int  NId, THashSet< TInt > &  Nbrs  ) const

private

Definition at line 35 of file cliques.cpp.

References THashSet< TKey, THashFunc >::AddKey(), TUNGraph::TNodeI::GetDeg(), TUNGraph::TNodeI::GetNbrNId(), TUNGraph::GetNI(), and m_G.

Referenced by Expand().

                                                               {
        TUNGraph::TNodeI node = m_G->GetNI(NId);
        int deg = node.GetDeg();
        for (int i=0; i<deg; i++) Nbrs.AddKey(node.GetNbrNId(i));
}

Here is the call graph for this function:

Here is the caller graph for this function:

int TCliqueOverlap::GetNodeIdWithMaxDeg ( const THashSet< TInt > &  Set ) const

private

Definition at line 41 of file cliques.cpp.

References THashSet< TKey, THashFunc >::BegI(), THashSet< TKey, THashFunc >::EndI(), TUNGraph::TNodeI::GetDeg(), TUNGraph::GetNI(), and m_G.

Referenced by Expand().

                                                                      {
        int id = -1;
        int maxDeg = -1;
        //
        for (THashSetKeyI<TInt> it=Set.BegI(); it<Set.EndI(); it++) {
                int nId = it.GetKey();
                int deg = m_G->GetNI(nId).GetDeg();
                if (maxDeg < deg) { maxDeg=deg; id=nId; }
        }
        return id;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TCliqueOverlap::GetOverlapCliques ( const TVec< TIntV > &  OverlapMtx, int  MinNodeOverlap, TVec< TIntV > &  CliqueIdVV  )

static

Definition at line 177 of file cliques.cpp.

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

                                                                                                                 {
        int n = OverlapMtx.Len();
        for (int i=0; i<n; i++) {
                bool isCommunity = false;
                for (int j=i+1; j<n; j++) {
                        if (OverlapMtx[i][j] >= MinNodeOverlap) {
                                if (! isCommunity) {
                                        TIntV v; v.Add(i);
                                        CliqueIdVV.Add(v);
                                        isCommunity=true;
                                }
                                CliqueIdVV.Last().Add(j);
                        }
                }
        }
}

Here is the call graph for this function:

void TCliqueOverlap::GetOverlapCliques ( const TVec< TIntV > &  OverlapMtx, const TVec< TIntV > &  MaxCliques, double  MinOverlapFrac, TVec< TIntV > &  CliqueIdVV  )

static

Definition at line 194 of file cliques.cpp.

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

                                                                                                                                                   {
        int n = OverlapMtx.Len();
        for(int i=0; i<n; i++){
                bool isCommunity = false;
                int size1 = MaxCliques[i].Len();
                for(int j=i+1; j<n; j++){
                        int size2 = MaxCliques[j].Len();
                        double ratio = OverlapMtx[i][j];
                        if(size1 < size2) ratio /= size1;
                        else ratio /= size2;
                        if(ratio >= MinOverlapFrac){
                                if(!isCommunity){
                                        TIntV v; v.Add(i);
                                        CliqueIdVV.Add(v);
                                        isCommunity=true;
                                }
                                CliqueIdVV.Last().Add(j);
                        }
                }
        }
}

Here is the call graph for this function:

void TCliqueOverlap::GetRelativeComplement ( const THashSet< TInt > &  A, const THashSet< TInt > &  B, THashSet< TInt > &  Complement  )

static

Definition at line 6 of file cliques.cpp.

References THashSet< TKey, THashFunc >::AddKey(), THashSet< TKey, THashFunc >::BegI(), THashSet< TKey, THashFunc >::EndI(), and THashSet< TKey, THashFunc >::IsKey().

Referenced by Expand().

                                                                                                                       {
  for (THashSet<TInt>::TIter it=A.BegI(); it<A.EndI(); it++) {
                const int nId = it.GetKey();
                if (!B.IsKey(nId)) Complement.AddKey(nId);
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

int TCliqueOverlap::Intersection ( const THashSet< TInt > &  A, const THashSet< TInt > &  B  )

static

Definition at line 23 of file cliques.cpp.

References THashSet< TKey, THashFunc >::BegI(), THashSet< TKey, THashFunc >::EndI(), THashSet< TKey, THashFunc >::IsKey(), and THashSet< TKey, THashFunc >::Len().

Referenced by CalculateOverlapMtx().

                                                                                 {
        int n = 0;
        if (A.Len() < B.Len()) {
                for (THashSetKeyI<TInt> it=A.BegI(); it<A.EndI(); it++) 
                        if (B.IsKey(it.GetKey())) n++;
        } else {
                for (THashSetKeyI<TInt> it=B.BegI(); it<B.EndI(); it++) 
                        if (A.IsKey(it.GetKey())) n++;
        }
        return n;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int TCliqueOverlap::MaxNbrsInCANDNodeId ( const THashSet< TInt > &  SUBG, const THashSet< TInt > &  CAND  ) const

private

Definition at line 53 of file cliques.cpp.

References THashSet< TKey, THashFunc >::BegI(), THashSet< TKey, THashFunc >::EndI(), TUNGraph::TNodeI::GetDeg(), TUNGraph::TNodeI::GetNbrNId(), TUNGraph::GetNI(), THashSet< TKey, THashFunc >::IsKey(), and m_G.

Referenced by Expand().

                                                                                                   {
        int id = -1;
        int maxIntersection = -1;
        //
        for (THashSetKeyI<TInt> it=SUBG.BegI(); it<SUBG.EndI(); it++) {
                int nId = it.GetKey();
                TUNGraph::TNodeI nIt = m_G->GetNI(nId);
                int deg = nIt.GetDeg();
                //
                int curIntersection = 0;
                for (int i=0; i<deg; i++) {
                        int nbrId = nIt.GetNbrNId(i);
                        if (CAND.IsKey(nbrId)) curIntersection++;
                }
                //
                if (maxIntersection < curIntersection) { maxIntersection=curIntersection; id=nId; }
        }
        return id;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

PUNGraph TCliqueOverlap::m_G

private

Definition at line 10 of file cliques.h.

Referenced by GetMaximalCliques(), GetNbrs(), GetNodeIdWithMaxDeg(), and MaxNbrsInCANDNodeId().

TVec<TIntV>* TCliqueOverlap::m_maxCliques

private

Definition at line 12 of file cliques.h.

Referenced by Expand(), and GetMaximalCliques().

int TCliqueOverlap::m_minMaxCliqueSize

private

Definition at line 13 of file cliques.h.

Referenced by Expand(), and GetMaximalCliques().

TIntV TCliqueOverlap::m_Q

private

Definition at line 11 of file cliques.h.

Referenced by Expand(), and GetMaximalCliques().

---

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

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