SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
ncp.h
Go to the documentation of this file.
1 #ifndef snap_network_community_profile_h
2 #define snap_network_community_profile_h
3 
4 #include "Snap.h"
5 
6 class TLocClust;
7 class TLocClustStat;
8 class TNcpGraphsBase;
9 
10 //#///////////////////////////////////////////////
12 
24 class TLocClust {
25 public:
26  static bool Verbose;
27 private:
29  int Nodes, Edges2; // Nodes, 2*edges in Graph
32  double Alpha; // PageRank jump probability (smaller Alpha diffuses the mass farther away)
33  int SeedNId; // Seed node
34  // volume, cut size, node ids, conductances
35  TIntV NIdV, VolV, CutV; // Vol=2*edges_inside+cut (vol = sum of the degrees)
36  TFltV PhiV; // Conductance
37  int BestCutIdx; // Index K to vectors where the conductance of the bounding cut (PhiV[K]) achieves its minimum
38 public:
39  TLocClust(const PUNGraph& GraphPt, const double& AlphaVal) :
40  Graph(GraphPt), Nodes(GraphPt->GetNodes()), Edges2(2*GraphPt->GetEdges()), Alpha(AlphaVal) { }
42  int Len() const { return GetRndWalkSup(); }
44  int GetRndWalkSup() const { return VolV.Len(); }
45 
47  int GetNId(const int& NodeN) const { return NIdV[NodeN]; }
49 
51  int GetVol(const int& Nodes) const { return VolV[Nodes]; }
53 
55  int GetCut(const int& Nodes) const { return CutV[Nodes]; }
57 
59  double GetPhi(const int& ValId) const { return PhiV[ValId]; }
60 
62  const TIntV& GetNIdV() const { return NIdV; }
64  const TIntV& GetVolV() const { return VolV; }
66  const TIntV& GetCutV() const { return CutV; }
68  const TFltV& GetPhiV() const { return PhiV; }
69 
71 
73  int BestCut() const { return BestCutIdx; }
75  int BestCutNodes() const { return BestCutIdx+1; }
77  int GetCutEdges() const { return GetCut(BestCut()); }
79  int GetCutVol() const { return GetVol(BestCut()); }
81  double GetCutPhi() const { return GetPhi(BestCut()); }
82 
84 
86  int ApproxPageRank(const int& SeedNode, const double& Eps);
88  void SupportSweep();
90 
93  void FindBestCut(const int& SeedNode, const int& ClustSz, const double& MinSizeFrac=0.2);
94 
96  void PlotVolDistr(const TStr& OutFNm, TStr Desc=TStr()) const;
98  void PlotCutDistr(const TStr& OutFNm, TStr Desc=TStr()) const;
100  void PlotPhiDistr(const TStr& OutFNm, TStr Desc=TStr()) const;
102  void SavePajek(const TStr& OutFNm) const;
103 
105  static void DrawWhiskers(const PUNGraph& Graph, TStr FNmPref, const int& PlotN);
107  static void GetCutStat(const PUNGraph& Graph, const TIntV& NIdV, int& Vol, int& Cut, double& Phi, int GraphEdges=-1);
109  static void GetCutStat(const PUNGraph& Graph, const TIntSet& NIdSet, int& Vol, int& Cut, double& Phi, int GraphEdges=-1);
112 
117  static void PlotNCP(const PUNGraph& Graph, const TStr& FNm, const TStr Desc="", const bool& BagOfWhiskers=true, const bool& RewireNet=false,
118  const int& KMin=10, const int& KMax=Mega(100), const int& Coverage=10, const bool& SaveTxtStat=false, const bool& PlotBoltzman=false);
119 
120  friend class TLocClustStat;
121 };
122 
123 //#///////////////////////////////////////////////
126 public:
127  static double BinFactor;
128  static int TakeValAt;
129 public:
130  class TNodeSweep {
131  public:
133  TIntV SweepV; // nodes inside the cut: cut of size k has node ids CutV[0...k-1]
134  TFltV PhiV; // conductance at the cut
135  public:
137  TNodeSweep(const int& SeedNode, const TIntV& SweepNIdV, const TFltV& PhiNIdV) :
138  SeedNId(SeedNode), SweepV(SweepNIdV), PhiV(PhiNIdV) { IAssert(SweepV.Len()==PhiV.Len()); }
139  TNodeSweep(const TNodeSweep& NS) : SeedNId(NS.SeedNId), SweepV(NS.SweepV), PhiV(NS.PhiV) { }
140  int Len() const { return SweepV.Len(); }
141  int GetSeed() const { return SeedNId; }
142  int NId(const int i) const { return SweepV[i]; }
143  double Phi(const int i) const { return PhiV[i]; }
144  bool operator < (const TNodeSweep& CS) const { return Len() < CS.Len(); }
145  };
146 
147  class TCutInfo {
148  public:
149  TInt Nodes, Edges, CutSz; // nodes inside, edges inside, edges cut
150  TIntV CutNIdV; // node ids inside the cluster
151  public:
152  TCutInfo() : Nodes(0), Edges(0), CutSz(0), CutNIdV() { }
153  TCutInfo(const int& ClustNodes, const int& EdgesInside, const int& CutSize) : Nodes(ClustNodes), Edges(EdgesInside), CutSz(CutSize) { }
154  TCutInfo(const int& ClustNodes, const int& EdgesInside, const int& CutSize, const TIntV& NIdV) :
155  Nodes(ClustNodes), Edges(EdgesInside), CutSz(CutSize), CutNIdV(NIdV) { }
156  TCutInfo(const PUNGraph& G, const TIntV& ClustNIdV, bool TakeNIdV=false) : Nodes(ClustNIdV.Len()) {
157  TSnap::GetEdgesInOut(G, ClustNIdV, Edges.Val, CutSz.Val); if(TakeNIdV){CutNIdV=ClustNIdV;} }
158  TCutInfo(const TCutInfo& CS) : Nodes(CS.Nodes), Edges(CS.Edges), CutSz(CS.CutSz), CutNIdV(CS.CutNIdV) { }
159  int GetNodes() const { return Nodes; }
160  int GetEdges() const { return Edges; }
161  int GetVol() const { return 2*Edges+CutSz; }
162  int GetCutSz() const { return CutSz; }
163  // community score measures (lower is better)
164  double GetPhi() const { return double(CutSz)/double(2*Edges+CutSz); } // conductance
165  double GetExpansion() const { return Nodes<2 ? 1.0 : double(CutSz)/double(Nodes); } // expansion
166  double GetIntDens() const { return 1.0 - ((Nodes<2) ? 0 : 2.0*double(Edges)/double(Nodes*(Nodes-1))); } // internal density
167  double GetCutRatio(const int& GNodes) const { return double(CutSz)/double(Nodes*(GNodes-Nodes)); } // cut ratio (external density)
168  double GetNormCut(const int& GEdges) const { return GetPhi() + double(CutSz)/double(2*GEdges-GetVol()); } // normalized cut
169  double GetFracDegOut(const PUNGraph& Graph, double& MxFrac, double& AvgFrac, double& MedianFrac, double& Pct9Frac, double& Flake) const; // fraction of node's edges pointing outside the cluster
170  double GetModular(const int& GEdges) const { return (2.0*Edges - GetExpEdgesIn(GEdges)) / (2.0*GEdges); } // modularity
171  double GetModRat(const int& GEdges) const { return (2.0*Edges) / GetExpEdgesIn(GEdges); } // modularity ratio
172  double GetExpEdgesIn(const int& GEdges) const { return TMath::Sqr(2.0*Edges+CutSz)/(2.0*GEdges); } // expected edges inside (sum of degrees on nodes inside)^2/(2*E)
173  bool operator < (const TCutInfo& CS) const { return GetPhi() < CS.GetPhi(); }
174  };
175 
176 private:
177  // parameters
180  PUNGraph Graph; // set at ::Run()
181 //private:
182 public:
183  TVec<TNodeSweep> SweepsV; // node ids and conductances for each run of local clustering
184  THash<TInt, TFltV> SizePhiH; // all conductances at cluster size K
185  THash<TInt, TCutInfo> BestCutH; // best cut (min conductance) at size K (edges inside, edges cut)
186  TFltPrV BagOfWhiskerV; // (size, conductance) for bag of whiskers
187  TFltPr BestWhisk; // best whisker (whisker with largest volume), (size, conductance)
188  TCutInfo BestCut; // best over-all cut
189  TIntSet SizeBucketSet; // for exponential bucketing (only indexes BestCutH at positions in BucketSet have CutNIdV filled)
190 public:
191  TLocClustStat(const double& _Alpha, const int& _KMin, const int& _KMax, const double& _KFac, const int& _Coverage, const double& _SizeFrac);
192  void Save(TSOut& SOut) const;
193  void Clr();
194  void SetGraph(const PUNGraph& GraphPt) { Graph=GraphPt; }
195  void Run(const PUNGraph& Graph, const bool& SaveAllSweeps=false, const bool& SaveAllCond=false, const bool& SaveBestNodesAtK=false);
196  void AddBagOfWhiskers();
197  void AddCut(const TIntV& NIdV);
198  void AddCut(const int& ClustSz, const double& Phi);
199  void AddToBestCutH(const PUNGraph& Graph, const TIntV& NIdV, const bool& AddBestCond=true);
200 
201  double FindBestCut(const int& Nodes, const TIntSet& TabuNIdSet, int& BestCutId) const;
202  const TCutInfo& FindBestCut(const int& Nodes=-1) const;
203  double FindBestCut(const int& Nodes, TIntV& ClustNIdV) const;
204  int FindBestCut(const int& Nodes, int& Vol, int& Cut, double& Phi) const;
205 
206  const TCutInfo& GetBestCut() const { return BestCut; } // overall best cut
207  int GetCuts() const { return BestCutH.Len(); }
208  const TCutInfo& GetKNodeCut(const int& Nodes) const { return BestCutH.GetDat(Nodes); }
209  const TCutInfo& GetCutN(const int& N) const { return BestCutH[N]; }
210 
211  int BestWhiskNodes() const { return int(BestWhisk.Val1.Val); }
212  int BestWhiskEdges() const { return (int)TMath::Round(1.0/BestWhisk.Val2.Val)/2-1; }
213  double BestWhiskPhi() const { return BestWhisk.Val2; }
214  TFltPr GetBestWhisk() const { return BestWhisk; }
215  const TFltPrV& GetBagOfWhiskersV() const { return BagOfWhiskerV; }
216  void GetCurveStat(TFltPrV& MeanV, TFltPrV& MedV, TFltPrV& Dec1V, TFltPrV& MinV, TFltPrV& MaxV) const;
217  void GetBoltzmanCurveStat(const TFltV& TempV, TVec<TFltPrV>& NcpV) const;
218 
219  TStr ParamStr() const;
220  void PlotNCP(const TStr& OutFNm, TStr Desc=TStr()) const; // lower-envelope of conductance
221  void PlotNCPModul(const TStr& OutFNm, TStr Desc=TStr()) const; // NCP but with modularity on Y-axis
222  void PlotNcpTop10(const TStr& OutFNm, TStr Desc, const int& TakeMinN) const;
223  void PlotPhiInOut(const TStr& OutFNm, TStr Desc=TStr()) const; // conductance on the boundary / counductance inside
224  void PlotBestClustDens(TStr OutFNm, TStr Desc=TStr()) const; // plot edges inside, cut size, conductance
225  void PlotNCPScatter(const TStr& OutFNm, TStr Desc=TStr()) const; // all different conducances of all sizes (not just min)
226  void PlotPhiDistr(const int& CmtySz, const TStr& OutFNm, TStr Desc=TStr()) const; // histogram of conductances for a fixed CmtySz
227  void PlotBoltzmanCurve(const TStr& OutFNm, TStr Desc=TStr()) const;
228 
229  void ImposeNCP(const TLocClustStat& LcStat2, TStr OutFNm, TStr Desc, TStr Desc1, TStr Desc2) const;
230  void ImposeNCP(const TLocClustStat& LcStat2, const TLocClustStat& LcStat3, TStr OutFNm, TStr Desc, TStr Desc1, TStr Desc2, TStr Desc3) const;
231  void SaveTxtInfo(const TStr& OutFNmPref, const TStr& Desc, const bool& SetMaxAt1) const;
232 
233  static void BagOfWhiskers(const PUNGraph& Graph, TFltPrV& SizePhiV, TFltPr& BestWhisk);
234  static void BagOfWhiskers2(const PUNGraph& Graph, TFltPrV& SizePhiV);
235  static void MakeExpBins(const TFltPrV& ValV, TFltPrV& NewV);
236  static void MakeExpBins(const TFltV& ValV, TFltV& NewV);
237 };
238 
239 //#///////////////////////////////////////////////
242 private:
246  TFltPrV WhiskerV, RewWhiskerV; // (size, conductance)
250 public:
251  TNcpGraphsBase(const TStr& FNmWc);
252  TNcpGraphsBase(TSIn& SIn);
253  void Save(TSOut& SOut) const;
254  void Impose(const TStr& OutFNm, const int& TopN, const bool& Smooth);
255  double GetXAtMinY(const TFltPrV& Ncp, const int& NNodes);
256  TFltPr GetXYAtMinY(const TFltPrV& Ncp, const int& NNodes);
257  void PlotNcpMin(const TStr& OutFNm, const bool& VsGraphN=false);
258  void SaveTxtNcpMin(const TStr& OutFNm, const bool& VsGraphN=false);
259  void PlotRewNcpMin(const TStr& OutFNm, const bool& VsGraphN=false);
260  void PlotBestWhisker(const TStr& OutFNm, const bool& VsGraphN=false);
261  void PlotRewBestWhisker(const TStr& OutFNm, const bool& VsGraphN=false);
262  void PlotAvgNcp(const TStr& OutFNm, const TVec<TFltPrV>& NcpVec, const int& MinSz, const double& MaxMinY);
263  void SaveTxt(const TStr& OutFNm);
264  static void PlotDataset(const TStr& InFNmWc, const TStr& OutFNm, const bool& ImposeNcp=false, const bool& VsGraphN=false);
265 };
266 
267 #endif
double GetModRat(const int &GEdges) const
Definition: ncp.h:171
#define IAssert(Cond)
Definition: bd.h:262
TFlt SizeFrac
Definition: ncp.h:178
TFltPrV RewWhiskerV
Definition: ncp.h:246
void SavePajek(const TStr &OutFNm) const
Saves the network in the Pajek format so it can be visualized. Red node represents the seed and color...
Definition: ncp.cpp:139
TVec< TNodeSweep > SweepsV
Definition: ncp.h:183
static void PlotDataset(const TStr &InFNmWc, const TStr &OutFNm, const bool &ImposeNcp=false, const bool &VsGraphN=false)
Definition: ncp.cpp:1281
void PlotAvgNcp(const TStr &OutFNm, const TVec< TFltPrV > &NcpVec, const int &MinSz, const double &MaxMinY)
Definition: ncp.cpp:1247
static int TakeValAt
Definition: ncp.h:128
static void BagOfWhiskers2(const PUNGraph &Graph, TFltPrV &SizePhiV)
Definition: ncp.cpp:977
int BestCutIdx
Definition: ncp.h:37
TIntFltH ResH
Definition: ncp.h:30
static void DrawWhiskers(const PUNGraph &Graph, TStr FNmPref, const int &PlotN)
Draws the 'whiskers' of the graph. Whiskers are small sub-graphs that are attached to the rest of the...
Definition: ncp.cpp:172
int GetVol(const int &Nodes) const
Returns the volume of the set of first NodeN nodes in the sweep vector.
Definition: ncp.h:51
void SupportSweep()
After the function ApproxPageRank() has been run the SupportSweep() computes the volume, cut size, node ids, conductance vectors.
Definition: ncp.cpp:52
TInt KMax
Definition: ncp.h:179
TVec< TFltPrV > NcpV
Definition: ncp.h:247
TFltV PhiV
Definition: ncp.h:36
static void GetCutStat(const PUNGraph &Graph, const TIntV &NIdV, int &Vol, int &Cut, double &Phi, int GraphEdges=-1)
For a given Graph and a set of nodes NIdV the function returns the Volume, CutSize and the Conductanc...
Definition: ncp.cpp:192
int GetCut(const int &Nodes) const
Returns the size of the cut of the first Nodes nodes in the sweep vector.
Definition: ncp.h:55
const TIntV & GetNIdV() const
Vector of node IDs sorted in the random walk order.
Definition: ncp.h:62
void Run(const PUNGraph &Graph, const bool &SaveAllSweeps=false, const bool &SaveAllCond=false, const bool &SaveBestNodesAtK=false)
Definition: ncp.cpp:300
int Val
Definition: dt.h:1136
TVec< TFltPrV > WhiskNcpV
Definition: ncp.h:249
TFlt KFac
Definition: ncp.h:178
int ApproxPageRank(const int &SeedNode, const double &Eps)
Computes Approximate PageRank from the seed node SeedNId and with tolerance Eps.
Definition: ncp.cpp:9
double GetPhi() const
Definition: ncp.h:164
TInt Coverage
Definition: ncp.h:179
TStr ParamStr() const
Definition: ncp.cpp:555
TFltPr GetXYAtMinY(const TFltPrV &Ncp, const int &NNodes)
Definition: ncp.cpp:1166
void PlotNcpMin(const TStr &OutFNm, const bool &VsGraphN=false)
Definition: ncp.cpp:1173
void PlotPhiDistr(const int &CmtySz, const TStr &OutFNm, TStr Desc=TStr()) const
Definition: ncp.cpp:735
void FindBestCut(const int &SeedNode, const int &ClustSz, const double &MinSizeFrac=0.2)
Finds minimum conductance cut in the graph around the seed node.
Definition: ncp.cpp:81
double Val
Definition: dt.h:1385
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void PlotPhiDistr(const TStr &OutFNm, TStr Desc=TStr()) const
Plots the cluster conductance vs. cluster size K (cluster is composed of nodes NIdV[1...K]).
Definition: ncp.cpp:126
PUNGraph Graph
Definition: ncp.h:180
double GetExpEdgesIn(const int &GEdges) const
Definition: ncp.h:172
void PlotCutDistr(const TStr &OutFNm, TStr Desc=TStr()) const
Plots the cluster cut size vs. cluster size K (cluster is composed of nodes NIdV[1...K]).
Definition: ncp.cpp:113
void GetBoltzmanCurveStat(const TFltV &TempV, TVec< TFltPrV > &NcpV) const
Definition: ncp.cpp:529
static bool Verbose
Definition: ncp.h:26
const TCutInfo & GetKNodeCut(const int &Nodes) const
Definition: ncp.h:208
int Len() const
Returns the support of the approximate random walk, the number of nodes with non-zero PageRank score...
Definition: ncp.h:42
void PlotNCP(const TStr &OutFNm, TStr Desc=TStr()) const
Definition: ncp.cpp:564
TInt KMin
Definition: ncp.h:179
int GetVol() const
Definition: ncp.h:161
static double BinFactor
Definition: ncp.h:127
int GetCutEdges() const
Number of edges in the 'best' (minimum conductance) cut.
Definition: ncp.h:77
double GetNormCut(const int &GEdges) const
Definition: ncp.h:168
static double Sqr(const double &x)
Definition: xmath.h:12
void GetEdgesInOut(const PGraph &Graph, const TIntV &NIdV, int &EdgesInX, int &EdgesOutX)
Definition: cmty.h:76
int BestWhiskNodes() const
Definition: ncp.h:211
double GetCutPhi() const
Conductance of the 'best' (minimum conductance) cut.
Definition: ncp.h:81
void PlotRewBestWhisker(const TStr &OutFNm, const bool &VsGraphN=false)
Definition: ncp.cpp:1232
Definition: dt.h:1383
TCutInfo BestCut
Definition: ncp.h:188
int GetCutSz() const
Definition: ncp.h:162
Definition: fl.h:58
const TCutInfo & GetBestCut() const
Definition: ncp.h:206
void PlotNCPModul(const TStr &OutFNm, TStr Desc=TStr()) const
Definition: ncp.cpp:589
int BestWhiskEdges() const
Definition: ncp.h:212
double GetExpansion() const
Definition: ncp.h:165
Local-Spectral-Clustering statistics of a given Graph.
Definition: ncp.h:125
TFltPrV WhiskerV
Definition: ncp.h:246
static void BagOfWhiskers(const PUNGraph &Graph, TFltPrV &SizePhiV, TFltPr &BestWhisk)
Definition: ncp.cpp:901
void AddToBestCutH(const PUNGraph &Graph, const TIntV &NIdV, const bool &AddBestCond=true)
Definition: ncp.cpp:422
Local Spectral Clustering algorithm.
Definition: ncp.h:24
void SaveTxtNcpMin(const TStr &OutFNm, const bool &VsGraphN=false)
Definition: ncp.cpp:1187
int GetRndWalkSup() const
Returns the support of the approximate random walk, the number of nodes with non-zero PageRank score...
Definition: ncp.h:44
TStrV GNmV
Definition: ncp.h:243
void PlotBestWhisker(const TStr &OutFNm, const bool &VsGraphN=false)
Definition: ncp.cpp:1217
double GetCutRatio(const int &GNodes) const
Definition: ncp.h:167
int Edges2
Definition: ncp.h:29
void Save(TSOut &SOut) const
Definition: ncp.cpp:1118
const TFltV & GetPhiV() const
Conducatance of the cut separating first K-nodes in the node-id vector (GetNIdV()) from the rest of t...
Definition: ncp.h:68
void PlotRewNcpMin(const TStr &OutFNm, const bool &VsGraphN=false)
Definition: ncp.cpp:1203
TVec< TFltPrV > RewNcpV
Definition: ncp.h:248
double GetIntDens() const
Definition: ncp.h:166
double FindBestCut(const int &Nodes, const TIntSet &TabuNIdSet, int &BestCutId) const
Definition: ncp.cpp:469
static double Round(const double &Val)
Definition: xmath.h:16
const TFltPrV & GetBagOfWhiskersV() const
Definition: ncp.h:215
#define Mega(n)
Definition: gbase.h:4
TIntV VolV
Definition: ncp.h:35
int Nodes
Definition: ncp.h:29
int GetCuts() const
Definition: ncp.h:207
int GetNodes() const
Definition: ncp.h:159
static void MakeExpBins(const TFltPrV &ValV, TFltPrV &NewV)
Definition: ncp.cpp:1020
void Clr()
Definition: ncp.cpp:293
Definition: fl.h:128
int GetSeed() const
Definition: ncp.h:141
double Phi(const int i) const
Definition: ncp.h:143
double GetPhi(const int &ValId) const
Returns the conductance of the cut separating the first Nodes nodes in the sweep vector from the rest...
Definition: ncp.h:59
int GetCutVol() const
Volume of the 'best' (minimum conductance) cut.
Definition: ncp.h:79
THash< TInt, TFltV > SizePhiH
Definition: ncp.h:184
void PlotNCPScatter(const TStr &OutFNm, TStr Desc=TStr()) const
Definition: ncp.cpp:715
void PlotPhiInOut(const TStr &OutFNm, TStr Desc=TStr()) const
Definition: ncp.cpp:643
TCutInfo(const TCutInfo &CS)
Definition: ncp.h:158
double Alpha
Definition: ncp.h:32
void GetCurveStat(TFltPrV &MeanV, TFltPrV &MedV, TFltPrV &Dec1V, TFltPrV &MinV, TFltPrV &MaxV) const
Definition: ncp.cpp:490
double GetFracDegOut(const PUNGraph &Graph, double &MxFrac, double &AvgFrac, double &MedianFrac, double &Pct9Frac, double &Flake) const
Definition: ncp.cpp:245
Definition: dt.h:1134
THash< TInt, TCutInfo > BestCutH
Definition: ncp.h:185
TFltPr GetBestWhisk() const
Definition: ncp.h:214
void SaveTxt(const TStr &OutFNm)
Definition: ncp.cpp:1267
double GetModular(const int &GEdges) const
Definition: ncp.h:170
TIntPrV GSizeV
Definition: ncp.h:245
int GetEdges() const
Definition: ncp.h:160
TIntV CutV
Definition: ncp.h:35
void ImposeNCP(const TLocClustStat &LcStat2, TStr OutFNm, TStr Desc, TStr Desc1, TStr Desc2) const
Definition: ncp.cpp:786
const TIntV & GetCutV() const
Edges cut to separate the first K-nodes in the node-id vector (GetNIdV()) from the rest of the graph...
Definition: ncp.h:66
TFlt Alpha
Definition: ncp.h:178
TCutInfo(const int &ClustNodes, const int &EdgesInside, const int &CutSize, const TIntV &NIdV)
Definition: ncp.h:154
const TIntV & GetVolV() const
Volume (sum of the degrees) of first K-nodes in the node-id vector (GetNIdV()).
Definition: ncp.h:64
void PlotNcpTop10(const TStr &OutFNm, TStr Desc, const int &TakeMinN) const
Definition: ncp.cpp:607
TFltPr BestWhisk
Definition: ncp.h:187
TIntV NIdV
Definition: ncp.h:35
Definition: dt.h:412
const TCutInfo & GetCutN(const int &N) const
Definition: ncp.h:209
void PlotBestClustDens(TStr OutFNm, TStr Desc=TStr()) const
Definition: ncp.cpp:689
bool operator<(const TNodeSweep &CS) const
Definition: ncp.h:144
PUNGraph Graph
Definition: ncp.h:28
TIntQ NodeQ
Definition: ncp.h:31
TNcpGraphsBase(const TStr &FNmWc)
Definition: ncp.cpp:1064
TVal1 Val1
Definition: ds.h:34
bool operator<(const TCutInfo &CS) const
Definition: ncp.h:173
TVal2 Val2
Definition: ds.h:35
int BestCut() const
Index K of the cut of the minimum conductance around the seed node.
Definition: ncp.h:73
int GetNId(const int &NodeN) const
Returns the ID of the NodeN-th node in the sweep vector.
Definition: ncp.h:47
TIntSet SizeBucketSet
Definition: ncp.h:189
TFltPrV BagOfWhiskerV
Definition: ncp.h:186
int SeedNId
Definition: ncp.h:33
TCutInfo(const PUNGraph &G, const TIntV &ClustNIdV, bool TakeNIdV=false)
Definition: ncp.h:156
TNodeSweep(const TNodeSweep &NS)
Definition: ncp.h:139
void PlotBoltzmanCurve(const TStr &OutFNm, TStr Desc=TStr()) const
Definition: ncp.cpp:747
void PlotVolDistr(const TStr &OutFNm, TStr Desc=TStr()) const
Plots the cluster volume vs. cluster size K (cluster is composed of nodes NIdV[1...K]).
Definition: ncp.cpp:100
void AddCut(const TIntV &NIdV)
Definition: ncp.cpp:410
TNodeSweep(const int &SeedNode, const TIntV &SweepNIdV, const TFltV &PhiNIdV)
Definition: ncp.h:137
void Save(TSOut &SOut) const
Definition: ncp.cpp:280
void AddBagOfWhiskers()
Definition: ncp.cpp:404
TFltV ParamValV
Definition: ncp.h:244
double BestWhiskPhi() const
Definition: ncp.h:213
void SetGraph(const PUNGraph &GraphPt)
Definition: ncp.h:194
void SaveTxtInfo(const TStr &OutFNmPref, const TStr &Desc, const bool &SetMaxAt1) const
Definition: ncp.cpp:841
int BestCutNodes() const
Number of nodes inside the 'best' (minimum conductance) cut.
Definition: ncp.h:75
int Len() const
Definition: ncp.h:140
double GetXAtMinY(const TFltPrV &Ncp, const int &NNodes)
Definition: ncp.cpp:1133
void Impose(const TStr &OutFNm, const int &TopN, const bool &Smooth)
Definition: ncp.cpp:1124
static void PlotNCP(const PUNGraph &Graph, const TStr &FNm, const TStr Desc="", const bool &BagOfWhiskers=true, const bool &RewireNet=false, const int &KMin=10, const int &KMax=Mega(100), const int &Coverage=10, const bool &SaveTxtStat=false, const bool &PlotBoltzman=false)
Definition: ncp.cpp:219
Local-Spectral-Clustering for a set of graphs (loads ncp-*.tab files)
Definition: ncp.h:241
TLocClust(const PUNGraph &GraphPt, const double &AlphaVal)
Definition: ncp.h:39
int NId(const int i) const
Definition: ncp.h:142
TCutInfo(const int &ClustNodes, const int &EdgesInside, const int &CutSize)
Definition: ncp.h:153
TLocClustStat(const double &_Alpha, const int &_KMin, const int &_KMax, const double &_KFac, const int &_Coverage, const double &_SizeFrac)
Definition: ncp.cpp:275
TIntFltH ProbH
Definition: ncp.h:30