SNAP Library, User Reference  2012-10-15 15:06:59
SNAP, a general purpose network analysis and graph mining library
 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