SNAP Library 4.1, User Reference  2018-07-26 16:30:42
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
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) { }
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:234
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:1388
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:1383
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:483
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:1134
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:971
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