SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
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:1139
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:1388
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
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
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:1386
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:1137
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
int Len() const
Definition: hash.h:228
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