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
kronecker.h
Go to the documentation of this file.
1 #ifndef snap_kronecker_h
2 #define snap_kronecker_h
3 
4 #include "Snap.h"
5 
7 // Dense Kronecker Matrix
10 
11 class TKronMtx {
12 public:
13  static const double NInf;
14  static TRnd Rnd;
15 private:
18 public:
19  TKronMtx() : MtxDim(-1), SeedMtx() { }
20  TKronMtx(const int& Dim) : MtxDim(Dim), SeedMtx(Dim*Dim) { }
21  TKronMtx(const TFltV& SeedMatrix);
22  TKronMtx(const TKronMtx& Kronecker) : MtxDim(Kronecker.MtxDim), SeedMtx(Kronecker.SeedMtx) { }
23  void SaveTxt(const TStr& OutFNm) const;
24  TKronMtx& operator = (const TKronMtx& Kronecker);
25  bool operator == (const TKronMtx& Kronecker) const { return SeedMtx==Kronecker.SeedMtx; }
26  int GetPrimHashCd() const { return SeedMtx.GetPrimHashCd(); }
27  int GetSecHashCd() const { return SeedMtx.GetSecHashCd(); }
28 
29  // seed matrix
30  int GetDim() const { return MtxDim; }
31  int Len() const { return SeedMtx.Len(); }
32  bool Empty() const { return SeedMtx.Empty(); }
33  bool IsProbMtx() const; // probability (not log-lihelihood) matrix
34 
35  TFltV& GetMtx() { return SeedMtx; }
36  const TFltV& GetMtx() const { return SeedMtx; }
37  void SetMtx(const TFltV& ParamV) { SeedMtx = ParamV; }
38  void SetRndMtx(const int& MtxDim, const double& MinProb = 0.0);
39  void PutAllMtx(const double& Val) { SeedMtx.PutAll(Val); }
40  void GenMtx(const int& Dim) { MtxDim=Dim; SeedMtx.Gen(Dim*Dim); }
41  void SetEpsMtx(const double& Eps1, const double& Eps0, const int& Eps1Val=1, const int& Eps0Val=0);
42  void SetForEdges(const int& Nodes, const int& Edges); // scales the values to allow E edges
43  void AddRndNoise(const double& SDev);
44  TStr GetMtxStr() const;
45 
46  const double& At(const int& Row, const int& Col) const { return SeedMtx[MtxDim*Row+Col].Val; }
47  double& At(const int& Row, const int& Col) { return SeedMtx[MtxDim*Row+Col].Val; }
48  const double& At(const int& ValN) const { return SeedMtx[ValN].Val; }
49  double& At(const int& ValN) { return SeedMtx[ValN].Val; }
50 
51  int GetNodes(const int& NIter) const;
52  int GetEdges(const int& NIter) const;
53  int GetKronIter(const int& Nodes) const;
54  int GetNZeroK(const PNGraph& Graph) const; // n0^k so that > Graph->GetNodes
55  double GetEZero(const int& Edges, const int& KronIter) const;
56  double GetMtxSum() const;
57  double GetRowSum(const int& RowId) const;
58  double GetColSum(const int& ColId) const;
59 
60  void ToOneMinusMtx();
61  void GetLLMtx(TKronMtx& LLMtx);
62  void GetProbMtx(TKronMtx& ProbMtx);
63  void Swap(TKronMtx& KronMtx);
64 
65  // edge probability and log-likelihood
66  double GetEdgeProb(int NId1, int NId2, const int& NKronIters) const; // given ProbMtx
67  double GetNoEdgeProb(int NId1, int NId2, const int& NKronIters) const; // given ProbMtx
68  double GetEdgeLL(int NId1, int NId2, const int& NKronIters) const; // given LLMtx
69  double GetNoEdgeLL(int NId1, int NId2, const int& NKronIters) const; // given LLMtx
70  double GetApxNoEdgeLL(int NId1, int NId2, const int& NKronIters) const; // given LLMtx
71  bool IsEdgePlace(int NId1, int NId2, const int& NKronIters, const double& ProbTresh) const; // place an edge
72  // derivative of edge log-likelihood
73  double GetEdgeDLL(const int& ParamId, int NId1, int NId2, const int& NKronIters) const; // given LLMtx
74  double GetNoEdgeDLL(const int& ParamId, int NId1, int NId2, const int& NKronIters) const; // given LLMtx
75  double GetApxNoEdgeDLL(const int& ParamId, int NId1, int NId2, const int& NKronIters) const; // given LLMtx
76 
77  // edge prob from node signature
78  static uint GetNodeSig(const double& OneProb = 0.5);
79  double GetEdgeProb(const uint& NId1Sig, const uint& NId2Sig, const int& NIter) const;
80 
81  // from the current (probabilistic) adjacency matrix
82  PNGraph GenThreshGraph(const double& Thresh) const;
83  PNGraph GenRndGraph(const double& RndFact=1.0) const;
84 
85  static int GetKronIter(const int& GNodes, const int& SeedMtxSz);
86  // from the seed matrix
87  static PNGraph GenKronecker(const TKronMtx& SeedMtx, const int& NIter, const bool& IsDir, const int& Seed=0);
88  static PNGraph GenFastKronecker(const TKronMtx& SeedMtx, const int& NIter, const bool& IsDir, const int& Seed=0);
89  static PNGraph GenFastKronecker(const TKronMtx& SeedMtx, const int& NIter, const int& Edges, const bool& IsDir, const int& Seed=0);
90  static PNGraph GenDetKronecker(const TKronMtx& SeedMtx, const int& NIter, const bool& IsDir);
91  static void PlotCmpGraphs(const TKronMtx& SeedMtx, const PNGraph& Graph, const TStr& OutFNm, const TStr& Desc);
92  static void PlotCmpGraphs(const TKronMtx& SeedMtx1, const TKronMtx& SeedMtx2, const PNGraph& Graph, const TStr& OutFNm, const TStr& Desc);
93  static void PlotCmpGraphs(const TVec<TKronMtx>& SeedMtxV, const PNGraph& Graph, const TStr& FNmPref, const TStr& Desc);
94 
95  static void KronMul(const TKronMtx& LeftPt, const TKronMtx& RightPt, TKronMtx& OutMtx);
96  static void KronSum(const TKronMtx& LeftPt, const TKronMtx& RightPt, TKronMtx& OutMtx); // log powering
97  static void KronPwr(const TKronMtx& KronPt, const int& NIter, TKronMtx& OutMtx);
98 
99  void Dump(const TStr& MtxNm = TStr(), const bool& Sort = false) const;
100  static double GetAvgAbsErr(const TKronMtx& Kron1, const TKronMtx& Kron2); // avg L1 on (sorted) parameters
101  static double GetAvgFroErr(const TKronMtx& Kron1, const TKronMtx& Kron2); // avg L2 on (sorted) parameters
102  static TKronMtx GetMtx(TStr MatlabMtxStr);
103  static TKronMtx GetRndMtx(const int& Dim, const double& MinProb);
104  static TKronMtx GetInitMtx(const int& Dim, const int& Nodes, const int& Edges);
105  static TKronMtx GetInitMtx(const TStr& MtxStr, const int& Dim, const int& Nodes, const int& Edges);
106  static TKronMtx GetMtxFromNm(const TStr& MtxNm);
107  static TKronMtx LoadTxt(const TStr& MtxFNm);
108  static void PutRndSeed(const int& Seed) { TKronMtx::Rnd.PutSeed(Seed); }
109 };
110 
112 // Kronecker Log Likelihood
113 
115 
117 public:
118 private:
120  PNGraph Graph; // graph to fit
122 
123  TFlt PermSwapNodeProb; // permutation proposal distribution (swap edge endpoins vs. swap random nodes)
124 // TIntPrV GEdgeV; // edge vector (for swap edge permutation proposal)
125  TIntTrV GEdgeV; // edge vector (for swap edge permutation proposal) /// !!!!! MYUNGHWAN, CHECK!
126  TIntTrV LEdgeV; // latent edge vector
127  TInt LSelfEdge; // latent self edges
128  TIntV NodePerm; // current permutation
129  TIntV InvertPerm; // current invert permutation
130 
131  TInt RealNodes; // # of observed nodes (for KronEM)
132  TInt RealEdges; // # of observed edges (for link prediction)
133 
134  TKronMtx ProbMtx, LLMtx; // Prob and LL matrices (parameters)
135  TFlt LogLike; // LL at ProbMtx
136  TFltV GradV; // DLL at ProbMtx (gradient)
137 
138  TKronEMType EMType; // Latent setting type for EM
139  TInt MissEdges; // # of missing edges (if unknown, -1)
140 
141  TBool DebugMode; // Debug mode flag
142  TFltV LLV; // Log-likelihood (per EM iteration)
143  TVec<TKronMtx> MtxV; // Kronecker initiator matrix (per EM iteration)
144 
145 public:
146  // RS 07/03/12, changed the order in the constructor initializer list
147  // so that it matches the declaration order. This changes also
148  // got rid of the compilation warnings. This is the old order:
149  // TKroneckerLL() : Nodes(-1), KronIters(-1), PermSwapNodeProb(0.2), LogLike(TKronMtx::NInf), EMType(kronNodeMiss), RealNodes(-1), RealEdges(-1), MissEdges(-1), DebugMode(false) { }
150  TKroneckerLL() : Nodes(-1), KronIters(-1), PermSwapNodeProb(0.2), RealNodes(-1), RealEdges(-1), LogLike(TKronMtx::NInf), EMType(kronNodeMiss), MissEdges(-1), DebugMode(false) { }
151  TKroneckerLL(const PNGraph& GraphPt, const TFltV& ParamV, const double& PermPSwapNd=0.2);
152  TKroneckerLL(const PNGraph& GraphPt, const TKronMtx& ParamMtx, const double& PermPSwapNd=0.2);
153  TKroneckerLL(const PNGraph& GraphPt, const TKronMtx& ParamMtx, const TIntV& NodeIdPermV, const double& PermPSwapNd=0.2);
154  static PKroneckerLL New() { return new TKroneckerLL(); }
155  static PKroneckerLL New(const PNGraph& GraphPt, const TKronMtx& ParamMtx, const double& PermPSwapNd=0.1);
156  static PKroneckerLL New(const PNGraph& GraphPt, const TKronMtx& ParamMtx, const TIntV& NodeIdPermV, const double& PermPSwapNd=0.2);
157 
158  int GetNodes() const { return Nodes; }
159  int GetKronIters() const { return KronIters; }
160  PNGraph GetGraph() const { return Graph; }
161  void SetGraph(const PNGraph& GraphPt);
162  const TKronMtx& GetProbMtx() const { return ProbMtx; }
163  const TKronMtx& GetLLMtx() const { return LLMtx; }
164  int GetParams() const { return ProbMtx.Len(); }
165  int GetDim() const { return ProbMtx.GetDim(); }
166 
167  void SetDebug(const bool Debug) { DebugMode = Debug; }
168  const TFltV& GetLLHist() const { return LLV; }
169  const TVec<TKronMtx>& GetParamHist() const { return MtxV; }
170 
171  // check actual nodes and edges (for KronEM)
172  bool IsObsNode(const int& NId) const { IAssert(RealNodes > 0); return (NId < RealNodes); }
173  bool IsObsEdge(const int& NId1, const int& NId2) const { IAssert(RealNodes > 0); return ((NId1 < RealNodes) && (NId2 < RealNodes)); }
174  bool IsLatentNode(const int& NId) const { return !IsObsNode(NId); }
175  bool IsLatentEdge(const int& NId1, const int& NId2) const { return !IsObsEdge(NId1, NId2); }
176 
177  // node permutation
178  void SetPerm(const char& PermId);
179  void SetOrderPerm(); // identity
180  void SetRndPerm(); // random
181  void SetDegPerm(); // node degrees
182  void SetBestDegPerm(); // best matched degrees
183  void SetPerm(const TIntV& NodePermV) { NodePerm = NodePermV; SetIPerm(NodePerm); }
184  void SetIPerm(const TIntV& Perm); // construct invert permutation
185  const TIntV& GetPermV() const { return NodePerm; }
186 
187  // handling isolated nodes to fit # of nodes to Kronecker graphs model
188  void AppendIsoNodes();
189  void RestoreGraph(const bool RestoreNodes = true);
190 
191  // full graph LL
192  double GetFullGraphLL() const;
193  double GetFullRowLL(int RowId) const;
194  double GetFullColLL(int ColId) const;
195  // empty graph LL
196  double GetEmptyGraphLL() const;
197  double GetApxEmptyGraphLL() const;
198  // graph LL
199  void InitLL(const TFltV& ParamV);
200  void InitLL(const TKronMtx& ParamMtx);
201  void InitLL(const PNGraph& GraphPt, const TKronMtx& ParamMtx);
202  double CalcGraphLL();
203  double CalcApxGraphLL();
204  double GetLL() const { return LogLike; }
205  double GetAbsErr() const { return fabs(pow((double)Graph->GetEdges(), 1.0/double(KronIters)) - ProbMtx.GetMtxSum()); }
206  double NodeLLDelta(const int& NId) const;
207  double SwapNodesLL(const int& NId1, const int& NId2);
208  bool SampleNextPerm(int& NId1, int& NId2); // sampling from P(perm|graph)
209 
210  // derivative of the log-likelihood
211  double GetEmptyGraphDLL(const int& ParamId) const;
212  double GetApxEmptyGraphDLL(const int& ParamId) const;
213  const TFltV& CalcGraphDLL();
214  const TFltV& CalcFullApxGraphDLL();
215  const TFltV& CalcApxGraphDLL();
216  double NodeDLLDelta(const int ParamId, const int& NId) const;
217  void UpdateGraphDLL(const int& SwapNId1, const int& SwapNId2);
218  const TFltV& GetDLL() const { return GradV; }
219  double GetDLL(const int& ParamId) const { return GradV[ParamId]; }
220 
221  // gradient
222  void SampleGradient(const int& WarmUp, const int& NSamples, double& AvgLL, TFltV& GradV);
223  double GradDescent(const int& NIter, const double& LrnRate, double MnStep, double MxStep, const int& WarmUp, const int& NSamples);
224  double GradDescent2(const int& NIter, const double& LrnRate, double MnStep, double MxStep, const int& WarmUp, const int& NSamples);
225 
226  // KronEM
227  void SetRandomEdges(const int& NEdges, const bool isDir = true);
228  void MetroGibbsSampleSetup(const int& WarmUp);
229  void MetroGibbsSampleNext(const int& WarmUp, const bool DLLUpdate = false);
230  void RunEStep(const int& GibbsWarmUp, const int& WarmUp, const int& NSamples, TFltV& LLV, TVec<TFltV>& DLLV);
231  double RunMStep(const TFltV& LLV, const TVec<TFltV>& DLLV, const int& GradIter, const double& LrnRate, double MnStep, double MxStep);
232  void RunKronEM(const int& EMIter, const int& GradIter, double LrnRate, double MnStep, double MxStep, const int& GibbsWarmUp, const int& WarmUp, const int& NSamples, const TKronEMType& Type = kronNodeMiss, const int& NMissing = -1);
233 
234 
235 
236  TFltV TestSamplePerm(const TStr& OutFNm, const int& WarmUp, const int& NSamples, const TKronMtx& TrueMtx, const bool& DoPlot=true);
237  static double CalcChainR2(const TVec<TFltV>& ChainLLV);
238  static void ChainGelmapRubinPlot(const TVec<TFltV>& ChainLLV, const TStr& OutFNm, const TStr& Desc);
239  TFltQu TestKronDescent(const bool& DoExact, const bool& TruePerm, double LearnRate, const int& WarmUp, const int& NSamples, const TKronMtx& TrueParam);
240  void GradDescentConvergence(const TStr& OutFNm, const TStr& Desc1, const bool& SamplePerm, const int& NIters,
241  double LearnRate, const int& WarmUp, const int& NSamples, const int& AvgKGraphs, const TKronMtx& TrueParam);
242  static void TestBicCriterion(const TStr& OutFNm, const TStr& Desc1, const PNGraph& G, const int& GradIters,
243  double LearnRate, const int& WarmUp, const int& NSamples, const int& TrueN0);
244  static void TestGradDescent(const int& KronIters, const int& KiloSamples, const TStr& Permutation);
245  friend class TPt<TKroneckerLL>;
246 };
247 
248 
250 // Add Noise to Graph
251 class TKronNoise {
252 public:
254  static int RemoveNodeNoise(PNGraph& Graph, const int& NNodes, const bool Random = true);
255  static int RemoveNodeNoise(PNGraph& Graph, const double& Rate, const bool Random = true);
256  static int FlipEdgeNoise(PNGraph& Graph, const int& NEdges, const bool Random = true);
257  static int FlipEdgeNoise(PNGraph& Graph, const double& Rate, const bool Random = true);
258  static int RemoveEdgeNoise(PNGraph& Graph, const int& NEdges);
259  static int RemoveEdgeNoise(PNGraph& Graph, const double& Rate);
260 };
261 
262 
264 // Kronecker Log Likelihood Maximization
265 class TKronMaxLL {
266 public:
267  class TFEval {
268  public:
271  public:
272  TFEval() : LogLike(0), GradV() { }
273  TFEval(const TFlt& LL, const TFltV& DLL) : LogLike(LL), GradV(DLL) { }
274  TFEval(const TFEval& FEval) : LogLike(FEval.LogLike), GradV(FEval.GradV) { }
275  TFEval& operator = (const TFEval& FEval) { if (this!=&FEval) {
276  LogLike=FEval.LogLike; GradV=FEval.GradV; } return *this; }
277  };
278 private:
279  //TInt WarmUp, NSamples;
280  THash<TKronMtx, TFEval> FEvalH; // cached gradients
282 public:
283  TKronMaxLL(const PNGraph& GraphPt, const TKronMtx& StartParam) : KronLL(GraphPt, StartParam) { }
284  void SetPerm(const char& PermId);
285 
286  void GradDescent(const int& NIter, const double& LrnRate, const double& MnStep, const double& MxStep,
287  const double& WarmUp, const double& NSamples);
288 
289  /*void EvalNewEdgeP(const TKronMtx& ProbMtx);
290  double GetLL(const TFltV& ThetaV);
291  void GetDLL(const TFltV& ThetaV, TFltV& DerivV);
292  double GetDLL(const TFltV& ThetaV, const int& ParamId);
293  //void MaximizeLL(const int& NWarmUp, const int& Samples);//*/
294 
295  static void RoundTheta(const TFltV& ThetaV, TFltV& NewThetaV);
296  static void RoundTheta(const TFltV& ThetaV, TKronMtx& Kronecker);
297 
298  static void Test();
299 };
300 
302 // Kronecker Fitting using Metrod of Moments (by Art Owen)
304 public:
306 public:
308  Edges=0; Hairpins=0; Tripins=0; Triads=0;
309  for (TUNGraph::TNodeI NI = G->BegNI(); NI < G->EndNI(); NI++) {
310  const int d = NI.GetOutDeg();
311  Edges += d;
312  Hairpins += d*(d-1.0);
313  Tripins += d*(d-1.0)*(d-2.0);
314  }
315  Edges /= 2.0;
316  Hairpins /= 2.0;
317  Tripins /= 6.0;
318  int64 ot,ct;
319  Triads = (int) TSnap::GetTriads(G, ot, ct)/3.0;
320  printf("E:%g\tH:%g\tT:%g\tD:%g\n", Edges, Hairpins, Tripins, Triads);
321  }
322 
323  TFltQu EstABC(const int& R) {
324  const double Step = 0.01;
325  double MinScore=TFlt::Mx;
326  double A=0, B=0, C=0;
327  //Edges=log(Edges); Hairpins=log(Hairpins); Tripins=log(Tripins); Triads=log(Triads);
328  for (double a = 1.0; a > Step; a-=Step) {
329  for (double b = Step; b <= 1.0; b+=Step) {
330  for (double c = Step; c <= a; c+=Step) {
331  double EE = ( pow(a+2*b+c, R) - pow(a+c, R) ) / 2.0;
332  double EH = ( pow(pow(a+b,2) + pow(b+c,2), R)
333  -2*pow(a*(a+b)+c*(c+b), R)
334  -pow(a*a + 2*b*b + c*c, R)
335  +2*pow(a*a + c*c, R) ) / 2.0;
336  double ET = ( pow(pow(a+b,3)+pow(b+c,3), R)
337  -3*pow(a*pow(a+b,2)+c*pow(b+c,2), R)
338  -3*pow(a*a*a + c*c*c + b*(a*a+c*c) + b*b*(a+c) + 2*b*b*b ,R)
339  +2*pow(a*a*a + 2*b*b*b + c*c*c, R)
340  +5*pow(a*a*a + c*c*c + b*b*(a+c), R)
341  +4*pow(a*a*a + c*c*c + b*(a*a+c*c), R)
342  -6*pow(a*a*a + c*c*c, R) ) / 6.0;
343  double ED = ( pow(a*a*a + 3*b*b*(a+c) + c*c*c, R)
344  -3*pow(a*(a*a+b*b) + c*(b*b+c*c), R)
345  +2*pow(a*a*a+c*c*c, R) ) / 6.0;
346  if (EE < 0) { EE = 1; }
347  if (EH < 0) { EH = 1; }
348  if (ET < 0) { ET = 1; }
349  if (ED < 0) { ED = 1; }
350  //EE=log(EE); EH=log(EH); ET=log(ET); ED=log(ED);
351  double Score = pow(Edges-EE,2)/EE + pow(Hairpins-EH ,2)/EH + pow(Tripins-ET, 2)/ET + pow(Triads-ED, 2)/ED;
352  //double Score = fabs(Edges-EE)/EE + fabs(Hairpins-EH)/EH + fabs(Tripins-ET)/ET + fabs(Triads-ED)/ED;
353  //double Score = log(pow(Edges-EE,2)/EE) + log(pow(Hairpins-EH,2)/EH) + log(pow(Tripins-ET, 2)/ET) + log(pow(Triads-ED, 2)/ED);
354  if (MinScore > Score || (a==0.9 && b==0.6 && c==0.2) || (TMath::IsInEps(a-0.99,1e-6) && TMath::IsInEps(b-0.57,1e-6) && TMath::IsInEps(c-0.05,1e-6)))
355  {
356  printf("%.03f %.03f %0.03f %10.4f %10.10g\t%10.10g\t%10.10g\t%10.10g\n", a,b,c, log10(Score), EE, EH, ET, ED);
357  //printf("%.03f %.03f %0.03f %g\n", a,b,c, log(Score));
358  A=a; B=b; C=c; MinScore=Score;
359  }
360  }
361  }
362  }
363  printf("\t\t\t %10.10g\t%10.10g\t%10.10g\t%10.10g\n", Edges, Hairpins, Tripins, Triads);
364  return TFltQu(A,B,C,MinScore);
365  }
366 
367  static void Test() {
368  TFIn FIn("as20.ngraph");
369  PUNGraph G = TSnap::ConvertGraph<PUNGraph>(TNGraph::Load(FIn));
370  //PUNGraph G = TKronMtx::GenFastKronecker(TKronMtx::GetMtx("0.9, 0.6; 0.6, 0.2"), 14, false, 0)->GetUNGraph();
371  //PUNGraph G = TUNGraph::GetSmallGraph();
372  TSnap::PrintInfo(G);
374  TSnap::PrintInfo(G);
375  TKronMomentsFit Fit(G);
376  printf("iter %d\n", TKronMtx::GetKronIter(G->GetNodes(), 2));
377  Fit.EstABC(TKronMtx::GetKronIter(G->GetNodes(), 2)); //*/
378  }
379 };
380 
381 
383 // Kronecker Phase Plot
384 /*class TKronPhasePlot {
385 public:
386  class TPhasePoint {
387  public:
388  TFlt Alpha, Beta;
389  TGrowthStat GrowthStat;
390  public:
391  TPhasePoint() { }
392  TPhasePoint(const double& A, const double& B, const TGrowthStat& GS) : Alpha(A), Beta(B), GrowthStat(GS) { }
393  TPhasePoint(TSIn& SIn) : Alpha(SIn), Beta(SIn), GrowthStat(SIn) { }
394  void Save(TSOut& SOut) const { Alpha.Save(SOut); Beta.Save(SOut); GrowthStat.Save(SOut); }
395  };
396  typedef TVec<TPhasePoint> TPhasePointV;
397 public:
398  TPhasePointV PhaseV;
399 public:
400  TKronPhasePlot() { }
401  TKronPhasePlot(const TKronPhasePlot& Phase) : PhaseV(Phase.PhaseV) { }
402  TKronPhasePlot(TSIn& SIn) : PhaseV(SIn) { }
403  void Save(TSOut& SOut) const { PhaseV.Save(SOut); }
404  void SaveMatlab(const TStr& OutFNm) const;
405 
406  static void KroneckerPhase(const TStr& MtxId, const int& MxIter,
407  const double& MnAlpha, const double& MxAlpha, const double& AlphaStep,
408  const double& MnBeta, const double& MxBeta, const double& BetaStep,
409  const TStr& FNmPref);
410 };*/
411 
412 /*// for conjugate gradient
413  class TFunc {
414  private:
415  TKronMaxLL* CallBack;
416  public:
417  TFunc(TKronMaxLL* CallBackPt) : CallBack(CallBackPt) { }
418  TFunc(const TFunc& Func) : CallBack(Func.CallBack) { }
419  TFunc& operator = (const TFunc& Func) { CallBack=Func.CallBack; return *this; }
420  double FVal(const TFltV& Point) { return -CallBack->GetLL(Point); }
421  void FDeriv(const TFltV& Point, TFltV& DerivV);
422  };
423 public:
424  // log barier
425  class TLogBarFunc {
426  private:
427  TKronMaxLL* CallBack;
428  double T;
429  public:
430  TLogBarFunc(TKronMaxLL* CallBackPt, const double& t=0.5) : CallBack(CallBackPt), T(t) { }
431  TLogBarFunc(const TLogBarFunc& Func) : CallBack(Func.CallBack), T(Func.T) { }
432  TLogBarFunc& operator = (const TLogBarFunc& Func) { CallBack=Func.CallBack; T=Func.T; return *this; }
433  double FVal(const TFltV& Point);
434  void FDeriv(const TFltV& Point, TFltV& DerivV);
435  };*/
436 
437 #endif
const TFltV & GetDLL() const
Definition: kronecker.h:218
Definition: bd.h:440
#define IAssert(Cond)
Definition: bd.h:262
void SetRndMtx(const int &MtxDim, const double &MinProb=0.0)
Definition: kronecker.cpp:40
TKronMomentsFit(const PUNGraph &G)
Definition: kronecker.h:307
TKronMtx & operator=(const TKronMtx &Kronecker)
Definition: kronecker.cpp:25
int64 GetTriads(const PGraph &Graph, int64 &ClosedTriads, int64 &OpenTriads, int SampleNodes=-1)
Computes the number of Closed and Open triads.
Definition: triad.h:246
const double & At(const int &ValN) const
Definition: kronecker.h:48
static int RemoveNodeNoise(PNGraph &Graph, const int &NNodes, const bool Random=true)
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.cpp:2204
static PNGraph GenKronecker(const TKronMtx &SeedMtx, const int &NIter, const bool &IsDir, const int &Seed=0)
Definition: kronecker.cpp:312
static PKroneckerLL New()
Definition: kronecker.h:154
double GetEdgeProb(int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:161
static TRnd Rnd
Definition: kronecker.h:14
int GetPrimHashCd() const
Returns primary hash code of the vector. Used by THash.
Definition: ds.h:999
TFEval(const TFlt &LL, const TFltV &DLL)
Definition: kronecker.h:273
int GetParams() const
Definition: kronecker.h:164
int GetEdges(const int &NIter) const
Definition: kronecker.cpp:123
static void TestBicCriterion(const TStr &OutFNm, const TStr &Desc1, const PNGraph &G, const int &GradIters, double LearnRate, const int &WarmUp, const int &NSamples, const int &TrueN0)
Definition: kronecker.cpp:2109
double GetMtxSum() const
Definition: kronecker.cpp:140
static void KronMul(const TKronMtx &LeftPt, const TKronMtx &RightPt, TKronMtx &OutMtx)
Definition: kronecker.cpp:591
TFltV TestSamplePerm(const TStr &OutFNm, const int &WarmUp, const int &NSamples, const TKronMtx &TrueMtx, const bool &DoPlot=true)
Definition: kronecker.cpp:1795
static TKronMtx LoadTxt(const TStr &MtxFNm)
Definition: kronecker.cpp:768
const TKronMtx & GetLLMtx() const
Definition: kronecker.h:163
TFltV & GetMtx()
Definition: kronecker.h:35
Definition: dt.h:11
void SetRandomEdges(const int &NEdges, const bool isDir=true)
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.cpp:1417
int GetKronIter(const int &Nodes) const
Definition: kronecker.cpp:127
TKronEMType
Definition: kronecker.h:114
void RunEStep(const int &GibbsWarmUp, const int &WarmUp, const int &NSamples, TFltV &LLV, TVec< TFltV > &DLLV)
Definition: kronecker.cpp:1567
void UpdateGraphDLL(const int &SwapNId1, const int &SwapNId2)
Definition: kronecker.cpp:1241
unsigned int uint
Definition: bd.h:11
static double CalcChainR2(const TVec< TFltV > &ChainLLV)
Definition: kronecker.cpp:1895
void SetOrderPerm()
Definition: kronecker.cpp:813
double GetApxNoEdgeLL(int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:191
double & At(const int &Row, const int &Col)
Definition: kronecker.h:47
double GetFullGraphLL() const
Definition: kronecker.cpp:943
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
void GradDescent(const int &NIter, const double &LrnRate, const double &MnStep, const double &MxStep, const double &WarmUp, const double &NSamples)
bool IsEdgePlace(int NId1, int NId2, const int &NKronIters, const double &ProbTresh) const
Definition: kronecker.cpp:196
void Swap(TKronMtx &KronMtx)
Definition: kronecker.cpp:114
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
int Len() const
Definition: kronecker.h:31
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
const TFltV & GetLLHist() const
Definition: kronecker.h:168
int GetSecHashCd() const
Returns secondary hash code of the vector. Used by THash.
Definition: ds.h:1011
void Dump(const TStr &MtxNm=TStr(), const bool &Sort=false) const
Definition: kronecker.cpp:636
TPt< TKroneckerLL > PKroneckerLL
Definition: kronecker.h:8
double NodeDLLDelta(const int ParamId, const int &NId) const
Definition: kronecker.cpp:1214
double GetFullRowLL(int RowId) const
Definition: kronecker.cpp:956
double Tripins
Definition: kronecker.h:305
void SetPerm(const char &PermId)
Definition: kronecker.cpp:2297
double GetEdgeLL(int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:175
double GetEmptyGraphDLL(const int &ParamId) const
Definition: kronecker.cpp:1136
double GetEmptyGraphLL() const
Definition: kronecker.cpp:976
static const double NInf
Definition: kronecker.h:13
static uint GetNodeSig(const double &OneProb=0.5)
Definition: kronecker.cpp:262
bool SampleNextPerm(int &NId1, int &NId2)
Definition: kronecker.cpp:1111
static TKronMtx GetInitMtx(const int &Dim, const int &Nodes, const int &Edges)
Definition: kronecker.cpp:705
TStr GetMtxStr() const
Definition: kronecker.cpp:80
void RunKronEM(const int &EMIter, const int &GradIter, double LrnRate, double MnStep, double MxStep, const int &GibbsWarmUp, const int &WarmUp, const int &NSamples, const TKronEMType &Type=kronNodeMiss, const int &NMissing=-1)
Definition: kronecker.cpp:1692
void SetIPerm(const TIntV &Perm)
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.cpp:875
void SetForEdges(const int &Nodes, const int &Edges)
Definition: kronecker.cpp:59
TKroneckerLL KronLL
Definition: kronecker.h:281
Definition: fl.h:275
static void KronPwr(const TKronMtx &KronPt, const int &NIter, TKronMtx &OutMtx)
Definition: kronecker.cpp:626
static const double Mx
Definition: dt.h:1391
TFlt LogLike
Definition: kronecker.h:135
TFlt PermSwapNodeProb
Definition: kronecker.h:123
const double & At(const int &Row, const int &Col) const
Definition: kronecker.h:46
void SetEpsMtx(const double &Eps1, const double &Eps0, const int &Eps1Val=1, const int &Eps0Val=0)
Definition: kronecker.cpp:50
double CalcGraphLL()
Definition: kronecker.cpp:1022
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:192
double GetEdgeDLL(const int &ParamId, int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:207
Definition: dt.h:1386
void RestoreGraph(const bool RestoreNodes=true)
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.cpp:923
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
TFEval(const TFEval &FEval)
Definition: kronecker.h:274
static void TestGradDescent(const int &KronIters, const int &KiloSamples, const TStr &Permutation)
Definition: kronecker.cpp:2138
bool IsProbMtx() const
Definition: kronecker.cpp:33
bool IsObsEdge(const int &NId1, const int &NId2) const
Definition: kronecker.h:173
TIntV NodePerm
Definition: kronecker.h:128
TInt MtxDim
Definition: kronecker.h:16
double CalcApxGraphLL()
Definition: kronecker.cpp:1037
void GetProbMtx(TKronMtx &ProbMtx)
Definition: kronecker.cpp:106
int GetNodes() const
Definition: kronecker.h:158
void SetBestDegPerm()
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.cpp:842
void SetDegPerm()
Definition: kronecker.cpp:828
TVec< TKronMtx > MtxV
Definition: kronecker.h:143
void SetPerm(const char &PermId)
Definition: kronecker.cpp:805
static int FlipEdgeNoise(PNGraph &Graph, const int &NEdges, const bool Random=true)
Definition: kronecker.cpp:2229
int GetSecHashCd() const
Definition: kronecker.h:27
double GetApxEmptyGraphLL() const
Definition: kronecker.cpp:987
static void PutRndSeed(const int &Seed)
Definition: kronecker.h:108
double GetApxNoEdgeDLL(const int &ParamId, int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:240
static TKronMtx GetMtxFromNm(const TStr &MtxNm)
Definition: kronecker.cpp:753
void SetRndPerm()
Definition: kronecker.cpp:820
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
void SampleGradient(const int &WarmUp, const int &NSamples, double &AvgLL, TFltV &GradV)
Definition: kronecker.cpp:1271
static PNGraph Load(TSIn &SIn)
Static constructor that loads the graph from a stream SIn and returns a pointer to it...
Definition: graph.h:487
PNGraph GenRndGraph(const double &RndFact=1.0) const
Definition: kronecker.cpp:295
double NodeLLDelta(const int &NId) const
Definition: kronecker.cpp:1055
TKronMaxLL(const PNGraph &GraphPt, const TKronMtx &StartParam)
Definition: kronecker.h:283
static void Test()
Definition: kronecker.h:367
double GetApxEmptyGraphDLL(const int &ParamId) const
Definition: kronecker.cpp:1147
!!!!! MYUNGHWAN, CHECK!
Definition: kronecker.h:116
double RunMStep(const TFltV &LLV, const TVec< TFltV > &DLLV, const int &GradIter, const double &LrnRate, double MnStep, double MxStep)
Definition: kronecker.cpp:1597
bool IsObsNode(const int &NId) const
Definition: kronecker.h:172
int GetKronIters() const
Definition: kronecker.h:159
TBool DebugMode
Definition: kronecker.h:141
bool IsLatentNode(const int &NId) const
Definition: kronecker.h:174
double GetDLL(const int &ParamId) const
Definition: kronecker.h:219
double & At(const int &ValN)
Definition: kronecker.h:49
bool Empty() const
Definition: kronecker.h:32
TInt RealEdges
Definition: kronecker.h:132
void SetMtx(const TFltV &ParamV)
Definition: kronecker.h:37
void AddRndNoise(const double &SDev)
Definition: kronecker.cpp:69
static double GetAvgFroErr(const TKronMtx &Kron1, const TKronMtx &Kron2)
Definition: kronecker.cpp:668
static void Test()
Definition: kronecker.cpp:2367
void ToOneMinusMtx()
Definition: kronecker.cpp:91
void GradDescentConvergence(const TStr &OutFNm, const TStr &Desc1, const bool &SamplePerm, const int &NIters, double LearnRate, const int &WarmUp, const int &NSamples, const int &AvgKGraphs, const TKronMtx &TrueParam)
Definition: kronecker.cpp:2017
static void ChainGelmapRubinPlot(const TVec< TFltV > &ChainLLV, const TStr &OutFNm, const TStr &Desc)
Definition: kronecker.cpp:1924
TQuad< TFlt, TFlt, TFlt, TFlt > TFltQu
Definition: ds.h:264
double GetFullColLL(int ColId) const
Definition: kronecker.cpp:966
void PutAllMtx(const double &Val)
Definition: kronecker.h:39
void InitLL(const TFltV &ParamV)
Definition: kronecker.cpp:996
const TKronMtx & GetProbMtx() const
Definition: kronecker.h:162
double GetEZero(const int &Edges, const int &KronIter) const
Definition: kronecker.cpp:136
double GetNoEdgeProb(int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:171
int GetNZeroK(const PNGraph &Graph) const
Definition: kronecker.cpp:132
void GetLLMtx(TKronMtx &LLMtx)
Definition: kronecker.cpp:98
const TFltV & CalcGraphDLL()
Definition: kronecker.cpp:1158
void MetroGibbsSampleSetup(const int &WarmUp)
Definition: kronecker.cpp:1476
const TFltV & CalcFullApxGraphDLL()
Definition: kronecker.cpp:1176
Definition: dt.h:1137
void MetroGibbsSampleNext(const int &WarmUp, const bool DLLUpdate=false)
Definition: kronecker.cpp:1503
const TVec< TKronMtx > & GetParamHist() const
Definition: kronecker.h:169
static bool IsInEps(const T &Val, const T &Eps)
Definition: xmath.h:83
double GradDescent2(const int &NIter, const double &LrnRate, double MnStep, double MxStep, const int &WarmUp, const int &NSamples)
Definition: kronecker.cpp:1355
static PNGraph GenDetKronecker(const TKronMtx &SeedMtx, const int &NIter, const bool &IsDir)
Definition: kronecker.cpp:458
double Hairpins
Definition: kronecker.h:305
void GenMtx(const int &Dim)
Definition: kronecker.h:40
void PutSeed(const int &_Seed)
Definition: dt.cpp:18
void AppendIsoNodes()
Definition: kronecker.cpp:914
TIntTrV GEdgeV
Definition: kronecker.h:125
double GetColSum(const int &ColId) const
Definition: kronecker.cpp:154
void SetPerm(const TIntV &NodePermV)
Definition: kronecker.h:183
TInt LSelfEdge
Definition: kronecker.h:127
TIntTrV LEdgeV
Definition: kronecker.h:126
TCRef CRef
Definition: kronecker.h:119
TInt KronIters
Definition: kronecker.h:121
TKronMtx ProbMtx
Definition: kronecker.h:134
long long int64
Definition: bd.h:27
TInt MissEdges
Definition: kronecker.h:139
int GetDim() const
Definition: kronecker.h:30
const TFltV & CalcApxGraphDLL()
Definition: kronecker.cpp:1194
double GetNoEdgeLL(int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:186
static TKronMtx GetRndMtx(const int &Dim, const double &MinProb)
Definition: kronecker.cpp:699
Definition: dt.h:412
Definition: ds.h:219
void SaveTxt(const TStr &OutFNm) const
Definition: kronecker.cpp:14
double SwapNodesLL(const int &NId1, const int &NId2)
Definition: kronecker.cpp:1083
THash< TKronMtx, TFEval > FEvalH
Definition: kronecker.h:280
TKronMtx LLMtx
Definition: kronecker.h:134
Definition: hash.h:97
TFEval & operator=(const TFEval &FEval)
Definition: kronecker.h:275
TInt RealNodes
Definition: kronecker.h:131
PNGraph GetGraph() const
Definition: kronecker.h:160
TKronMtx(const int &Dim)
Definition: kronecker.h:20
PNGraph Graph
Definition: kronecker.h:120
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
TFltV GradV
Definition: kronecker.h:136
bool IsLatentEdge(const int &NId1, const int &NId2) const
Definition: kronecker.h:175
static void KronSum(const TKronMtx &LeftPt, const TKronMtx &RightPt, TKronMtx &OutMtx)
Definition: kronecker.cpp:607
const TFltV & GetMtx() const
Definition: kronecker.h:36
Definition: bd.h:196
const TIntV & GetPermV() const
Definition: kronecker.h:185
double GetRowSum(const int &RowId) const
Definition: kronecker.cpp:147
int GetNodes(const int &NIter) const
Definition: kronecker.cpp:119
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
double GetAbsErr() const
Definition: kronecker.h:205
TFltQu EstABC(const int &R)
Definition: kronecker.h:323
PNGraph GenThreshGraph(const double &Thresh) const
Definition: kronecker.cpp:283
double GetNoEdgeDLL(const int &ParamId, int NId1, int NId2, const int &NKronIters) const
Definition: kronecker.cpp:220
void SetGraph(const PNGraph &GraphPt)
Definition: kronecker.cpp:882
TKronEMType EMType
Definition: kronecker.h:138
TFltV SeedMtx
Definition: kronecker.h:17
TKronMtx()
Definition: kronecker.h:19
TFltQu TestKronDescent(const bool &DoExact, const bool &TruePerm, double LearnRate, const int &WarmUp, const int &NSamples, const TKronMtx &TrueParam)
Definition: kronecker.cpp:1942
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:237
Definition: dt.h:974
void DelSelfEdges(const PGraph &Graph)
Removes all the self-edges from the graph.
Definition: alg.h:419
void SetDebug(const bool Debug)
Definition: kronecker.h:167
TKronMtx(const TKronMtx &Kronecker)
Definition: kronecker.h:22
TIntV InvertPerm
Definition: kronecker.h:129
double GetLL() const
Definition: kronecker.h:204
static double GetAvgAbsErr(const TKronMtx &Kron1, const TKronMtx &Kron2)
Definition: kronecker.cpp:655
static void PlotCmpGraphs(const TKronMtx &SeedMtx, const PNGraph &Graph, const TStr &OutFNm, const TStr &Desc)
Definition: kronecker.cpp:479
static void RoundTheta(const TFltV &ThetaV, TFltV &NewThetaV)
Definition: kronecker.cpp:2354
double GradDescent(const int &NIter, const double &LrnRate, double MnStep, double MxStep, const int &WarmUp, const int &NSamples)
Definition: kronecker.cpp:1299
int GetDim() const
Definition: kronecker.h:165
int GetPrimHashCd() const
Definition: kronecker.h:26
bool operator==(const TKronMtx &Kronecker) const
Definition: kronecker.h:25
static int RemoveEdgeNoise(PNGraph &Graph, const int &NEdges)
Definition: kronecker.cpp:2268
static PNGraph GenFastKronecker(const TKronMtx &SeedMtx, const int &NIter, const bool &IsDir, const int &Seed=0)
Definition: kronecker.cpp:349
void PrintInfo(const PGraph &Graph, const TStr &Desc="", const TStr &OutFNm="", const bool &Fast=true)
Prints basic graph statistics.
Definition: gbase.h:87