SNAP Library , Developer Reference  2013-01-07 14:03:36
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
cliques.h
Go to the documentation of this file.
00001 #ifndef Snap_Cliques
00002 #define Snap_Cliques
00003 
00004 #include "Snap.h"
00005 
00007 // Clique Percolation Method for Overlapping community detection
00008 class TCliqueOverlap {
00009 private: //Recursion variables only
00010         PUNGraph m_G;
00011         TIntV m_Q;
00012         TVec<TIntV> *m_maxCliques;
00013         int m_minMaxCliqueSize;
00014 private:
00015         void GetNbrs(int NId, THashSet<TInt>& Nbrs) const;
00016         int GetNodeIdWithMaxDeg(const THashSet<TInt>& Set) const;
00017         int MaxNbrsInCANDNodeId(const THashSet<TInt>& SUBG, const THashSet<TInt>& CAND) const;
00018 private:
00019         void Expand(const THashSet<TInt>& SUBG, THashSet<TInt>& CAND);
00020 public:
00021         static void GetRelativeComplement(const THashSet<TInt>& A, const THashSet<TInt>& B, THashSet<TInt>& Complement);
00022         static void GetIntersection(const THashSet<TInt>& A, const THashSet<TInt>& B, THashSet<TInt>& C);
00023         static int Intersection(const THashSet<TInt>& A, const THashSet<TInt>& B);
00024   static void CalculateOverlapMtx(const TVec<TIntV>& MaxCliques, int MinNodeOverlap, TVec<TIntV>& OverlapMtx);
00025   static PUNGraph CalculateOverlapMtx(const TVec<TIntV>& MaxCliques, int MinNodeOverlap);
00026         static void GetOverlapCliques(const TVec<TIntV>& OverlapMtx, int MinNodeOverlap, TVec<TIntV>& CliqueIdVV);
00027         static void GetOverlapCliques(const TVec<TIntV>& OverlapMtx, const TVec<TIntV>& MaxCliques, double MinOverlapFrac, TVec<TIntV>& CliqueIdVV);
00028 public:
00029   TCliqueOverlap() : m_G(), m_Q(), m_maxCliques(NULL), m_minMaxCliqueSize(3) { }
00030         void GetMaximalCliques(const PUNGraph& G, int MinMaxCliqueSize, TVec<TIntV>& MaxCliques);
00032   static void GetMaxCliques(const PUNGraph& G, int MinMaxCliqueSize, TVec<TIntV>& MaxCliques);
00034   static void GetCPMCommunities(const PUNGraph& G, int MinMaxCliqueSize, TVec<TIntV>& Communities);
00035 };
00036 
00037 #endif