SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
cascdynetinf.cpp
Go to the documentation of this file.
1 #include "stdafx.h"
2 #include "cascdynetinf.h"
3 
5  TStr Line;
6  while (!SIn.Eof()) {
7  SIn.GetNextLn(Line);
8  if (Line=="") { break; }
9  TStrV NIdV; Line.SplitOnAllCh(',', NIdV);
10  AddNodeNm(NIdV[0].GetInt(), TNodeInfo(NIdV[1], 0));
11  }
12  printf("All nodes read!\n");
13  while (!SIn.Eof()) { SIn.GetNextLn(Line); AddCasc(Line, Model); }
14 
15  printf("All cascades read!\n");
16 }
17 
19  bool verbose = false;
20  TStr Line;
21 
22  Network.Clr(); // clear network (if any)
23 
24  // add nodes
25  while (!SIn.Eof()) {
26  SIn.GetNextLn(Line);
27  if (Line=="") { break; }
28  TStrV NIdV; Line.SplitOnAllCh(',', NIdV);
29  Network.AddNode(NIdV[0].GetInt(), NIdV[1]);
30  if (!IsNodeNm(NIdV[0].GetInt())) {
31  AddNodeNm(NIdV[0].GetInt(), TNodeInfo(NIdV[1], 0));
32  DomainsIdH.AddDat(NIdV[1]) = NIdV[0].GetInt();
33  }
34  }
35 
36  // add edges
37  while (!SIn.Eof()) {
38  SIn.GetNextLn(Line);
39  TStrV FieldsV; Line.SplitOnAllCh(',', FieldsV);
40 
41  TFltFltH Alphas;
42  if (FieldsV.Len() == 3) {
43  Alphas.AddDat(0.0) = FieldsV[2].GetFlt();
44  } else {
45  for (int i=2; i<FieldsV.Len()-1; i+=2) {
46  Alphas.AddDat(FieldsV[i].GetFlt()) = FieldsV[i+1].GetFlt();
47  }
48  }
49 
50  Network.AddEdge(FieldsV[0].GetInt(), FieldsV[1].GetInt(), Alphas);
51 
52  if (verbose) {
53  printf("Edge %d -> %d: ", FieldsV[0].GetInt(), FieldsV[1].GetInt());
54  TFltFltH &AlphasE = Network.GetEDat(FieldsV[0].GetInt(), FieldsV[1].GetInt());
55  for (int i=0; i<AlphasE.Len(); i+=2) { printf("(%f, %f)", AlphasE.GetKey(i).Val, AlphasE[i].Val); }
56  printf("\n");
57  }
58  }
59 
60  printf("groundtruth nodes:%d edges:%d\n", Network.GetNodes(), Network.GetEdges());
61 }
62 
64  TStr Line;
65 
66  Network.Clr(); // clear network (if any)
67 
68  // add nodes
69  while (!SIn.Eof()) {
70  SIn.GetNextLn(Line);
71  if (Line=="") { break; }
72  TStrV NIdV; Line.SplitOnAllCh(',', NIdV);
73  Network.AddNode(NIdV[0].GetInt(), NIdV[1]);
74  if (!IsNodeNm(NIdV[0].GetInt())) {
75  AddNodeNm(NIdV[0].GetInt(), TNodeInfo(NIdV[1], 0));
76  DomainsIdH.AddDat(NIdV[1]) = NIdV[0].GetInt();
77  }
78  }
79 
80  printf("groundtruth nodes:%d\n", Network.GetNodes());
81 }
82 
84  bool verbose = false;
85  TStr Line;
86 
87  InferredNetwork.Clr(); // clear network (if any)
88 
89  // add nodes
90  while (!SIn.Eof()) {
91  SIn.GetNextLn(Line);
92  if (Line=="") { break; }
93  TStrV NIdV; Line.SplitOnAllCh(',', NIdV);
94  if (DomainsIdH.IsKey(NIdV[1])) { IAssert(NIdV[0].GetInt()==DomainsIdH.GetDat(NIdV[1])); }
95  InferredNetwork.AddNode(NIdV[0].GetInt(), NIdV[1]);
96  if (!IsNodeNm(NIdV[0].GetInt())) { AddNodeNm(NIdV[0].GetInt(), TNodeInfo(NIdV[1], 0)); }
97  if (!DomainsIdH.IsKey(NIdV[1])) { DomainsIdH.AddDat(NIdV[1]) = NIdV[0].GetInt(); }
98  if (verbose) { printf("Node:%s\n", NIdV[1].CStr()); }
99  }
100 
101  // add edges
102  while (!SIn.Eof()) {
103  SIn.GetNextLn(Line);
104  TStrV FieldsV; Line.SplitOnAllCh(',', FieldsV);
105 
106  TFltFltH Alphas;
107  if (FieldsV.Len() == 3) {
108  Alphas.AddDat(0.0) = FieldsV[2].GetFlt();
109  } else {
110  for (int i=2; i<FieldsV.Len()-1; i+=2) {
111  Alphas.AddDat(FieldsV[i].GetFlt()) = FieldsV[i+1].GetFlt();
112  }
113  }
114 
115  InferredNetwork.AddEdge(FieldsV[0].GetInt(), FieldsV[1].GetInt(), Alphas);
116 
117  if (verbose) {
118  printf("Edge %d -> %d: ", FieldsV[0].GetInt(), FieldsV[1].GetInt());
119  TFltFltH &AlphasE = InferredNetwork.GetEDat(FieldsV[0].GetInt(), FieldsV[1].GetInt());
120  for (int i=0; i<AlphasE.Len(); i+=2) { printf("(%f, %f)", AlphasE.GetKey(i).Val, AlphasE[i].Val); }
121  printf("\n");
122  }
123  }
124 
125  printf("inferred nodes:%d edges:%d\n", InferredNetwork.GetNodes(), InferredNetwork.GetEdges());
126 }
127 
129  TStr Line;
130 
131  InferredNetwork.Clr(); // clear network (if any)
132 
133  // add nodes
134  while (!SIn.Eof()) {
135  SIn.GetNextLn(Line);
136  if (Line=="") { break; }
137  TStrV NIdV; Line.SplitOnAllCh(',', NIdV);
138  if (DomainsIdH.IsKey(NIdV[1])) { IAssert(NIdV[0].GetInt()==DomainsIdH.GetDat(NIdV[1])); }
139  InferredNetwork.AddNode(NIdV[0].GetInt(), NIdV[1]);
140  if (!IsNodeNm(NIdV[0].GetInt())) { AddNodeNm(NIdV[0].GetInt(), TNodeInfo(NIdV[1], 0)); }
141  if (!DomainsIdH.IsKey(NIdV[1])) { DomainsIdH.AddDat(NIdV[1]) = NIdV[0].GetInt(); }
142  }
143 
144  printf("Nodes:%d\n", InferredNetwork.GetNodes());
145 }
146 
147 void TNIBs::AddCasc(const TStr& CascStr, const TModel& Model) {
148  int CId = CascH.Len();
149 
150  // support cascade id if any
151  TStrV FieldsV; CascStr.SplitOnAllCh(';', FieldsV);
152  if (FieldsV.Len()==2) { CId = FieldsV[0].GetInt(); }
153 
154  // read nodes
155  TStrV NIdV; FieldsV[FieldsV.Len()-1].SplitOnAllCh(',', NIdV);
156  TCascade C(CId, Model);
157  for (int i = 0; i < NIdV.Len(); i+=2) {
158  int NId;
159  double Tm;
160  NId = NIdV[i].GetInt();
161  Tm = NIdV[i+1].GetFlt();
162  GetNodeInfo(NId).Vol = GetNodeInfo(NId).Vol + 1;
163  C.Add(NId, Tm);
164  }
165  C.Sort();
166 
167  AddCasc(C);
168 }
169 
170 void TNIBs::AddCasc(const TIntFltH& Cascade, const int& CId, const TModel& Model) {
171  TCascade C(CId, Model);
172  for (TIntFltH::TIter NI = Cascade.BegI(); NI < Cascade.EndI(); NI++) {
173  GetNodeInfo(NI.GetKey()).Vol = GetNodeInfo(NI.GetKey()).Vol + 1;
174  C.Add(NI.GetKey(), NI.GetDat());
175  }
176  C.Sort();
177  AddCasc(C);
178 }
179 
181  bool verbose = false;
182  TIntFltH InfectedNIdH; TIntH InfectedBy;
183  double GlobalTime, InitTime;
184  double alpha;
185  int StartNId;
186 
187  if (Network.GetNodes() == 0)
188  return;
189 
190  // set random seed
192 
193  while (C.Len() < 2) {
194  C.Clr();
195  InfectedNIdH.Clr();
196  InfectedBy.Clr();
197 
198  InitTime = TFlt::Rnd.GetUniDev() * TotalTime; // random starting point <TotalTime
199  GlobalTime = InitTime;
200 
201  StartNId = Network.GetRndNId();
202  InfectedNIdH.AddDat(StartNId) = GlobalTime;
203 
204  while (true) {
205  // sort by time & get the oldest node that did not run infection
206  InfectedNIdH.SortByDat(true);
207  const int& NId = InfectedNIdH.BegI().GetKey();
208  GlobalTime = InfectedNIdH.BegI().GetDat();
209 
210  // all the nodes has run infection
211  if ( GlobalTime >= TFlt::GetMn(TotalTime, InitTime+Window) )
212  break;
213 
214  // add current oldest node to the network and set its time
215  C.Add(NId, GlobalTime);
216 
217  if (verbose) { printf("GlobalTime:%f, infected node:%d\n", GlobalTime, NId); }
218 
219  // run infection from the current oldest node
220  TStrFltFltHNEDNet::TNodeI NI = Network.GetNI(NId);
221  for (int e = 0; e < NI.GetOutDeg(); e++) {
222  const int DstNId = NI.GetOutNId(e);
223 
224  // choose the current tx rate (we assume the most recent tx rate)
225  TFltFltH& Alphas = Network.GetEDat(NId, DstNId);
226  for (int j=0; j<Alphas.Len() && Alphas.GetKey(j)<GlobalTime; j++) { alpha = Alphas[j]; }
227  if (verbose) { printf("GlobalTime:%f, nodes:%d->%d, alpha:%f\n", GlobalTime, NId, DstNId, alpha); }
228 
229  if (alpha<1e-9) { continue; }
230 
231  // not infecting the parent
232  if (InfectedBy.IsKey(NId) && InfectedBy.GetDat(NId).Val == DstNId)
233  continue;
234 
235  double sigmaT;
236  switch (Model) {
237  case EXP:
238  // exponential with alpha parameter
239  sigmaT = TInt::Rnd.GetExpDev(alpha);
240  break;
241  case POW:
242  // power-law with alpha parameter
243  sigmaT = TInt::Rnd.GetPowerDev(1+alpha);
244  while (sigmaT < Delta) { sigmaT = Delta*TInt::Rnd.GetPowerDev(1+alpha); }
245  break;
246  case RAY:
247  // rayleigh with alpha parameter
248  sigmaT = TInt::Rnd.GetRayleigh(1/sqrt(alpha));
249  break;
250  default:
251  sigmaT = 1;
252  break;
253  }
254 
255  IAssert(sigmaT >= 0);
256 
257  double t1 = TFlt::GetMn(GlobalTime + sigmaT, TFlt::GetMn(InitTime+Window, TotalTime));
258 
259  if (InfectedNIdH.IsKey(DstNId)) {
260  double t2 = InfectedNIdH.GetDat(DstNId);
261  if ( t2 > t1 && t2 < TFlt::GetMn(InitTime+Window, TotalTime)) {
262  InfectedNIdH.GetDat(DstNId) = t1;
263  InfectedBy.GetDat(DstNId) = NId;
264  }
265  } else {
266  InfectedNIdH.AddDat(DstNId) = t1;
267  InfectedBy.AddDat(DstNId) = NId;
268  }
269  }
270 
271  // we cannot delete key (otherwise, we cannot sort), so we assign a big time (InitTime + window cut-off)
272  InfectedNIdH.GetDat(NId) = TFlt::GetMn(InitTime+Window, TotalTime);
273  }
274  }
275 
276  C.Sort();
277 }
278 
279 void TNIBs::GetGroundTruthGraphAtT(const double& Step, PNGraph &GraphAtT) {
280  GraphAtT = TNGraph::New();
281 
282  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) { GraphAtT->AddNode(NI.GetKey()); }
283 
284  for (TStrFltFltHNEDNet::TEdgeI EI = Network.BegEI(); EI < Network.EndEI(); EI++) {
285  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
286  double Alpha = 0.0;
287  if (EI().IsKey(Step)) { Alpha = EI().GetDat(Step); }
288 
289  if (Alpha > MinAlpha) {
290  GraphAtT->AddEdge(EI.GetSrcNId(), EI.GetDstNId());
291  }
292  }
293 }
294 
295 void TNIBs::GetGroundTruthNetworkAtT(const double& Step, PStrFltNEDNet& NetworkAtT) {
296  NetworkAtT = TStrFltNEDNet::New();
297 
298  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) { NetworkAtT->AddNode(NI.GetKey(), NI.GetDat().Name); }
299 
300  for (TStrFltFltHNEDNet::TEdgeI EI = Network.BegEI(); EI < Network.EndEI(); EI++) {
301  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
302  double Alpha = 0.0;
303  if (EI().IsKey(Step)) { Alpha = EI().GetDat(Step); }
304 
305  if (Alpha > MinAlpha) {
306  NetworkAtT->AddEdge(EI.GetSrcNId(), EI.GetDstNId(), Alpha);
307  }
308  }
309 }
310 
311 void TNIBs::GetInferredGraphAtT(const double& Step, PNGraph &GraphAtT) {
312  GraphAtT = TNGraph::New();
313 
314  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) { GraphAtT->AddNode(NI.GetKey()); }
315 
316  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
317  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
318 
319  double inferredAlpha = 0.0;
320  if (EI().IsKey(Step)) { inferredAlpha = EI().GetDat(Step); }
321 
322  if (inferredAlpha > MinAlpha) {
323  GraphAtT->AddEdge(EI.GetSrcNId(), EI.GetDstNId());
324  }
325  }
326 }
327 
328 void TNIBs::GetInferredNetworkAtT(const double& Step, PStrFltNEDNet& NetworkAtT) {
329  NetworkAtT = TStrFltNEDNet::New();
330 
331  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
332  NetworkAtT->AddNode(NI.GetKey(), NI.GetDat().Name);
333  }
334 
335  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
336  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
337 
338  double inferredAlpha = 0.0;
339  if (EI().IsKey(Step)) { inferredAlpha = EI().GetDat(Step); }
340 
341  if (inferredAlpha > MinAlpha) {
342  NetworkAtT->AddEdge(EI.GetSrcNId(), EI.GetDstNId(), inferredAlpha);
343  }
344  }
345 }
346 
347 void TNIBs::Init(const TFltV& Steps) {
348  // inferred network
350 
351  // copy nodes from NodeNmH (it will be filled by loading cascades or loading groundtruth)
352  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
353  InferredNetwork.AddNode(NI.GetKey(), NI.GetDat().Name);
354  }
355 
356  // performance measures
358  Accuracy.Clr();
359  MAE.Clr();
361 
362  for (int i=0; i<Steps.Len()-1; i++) {
363  MAE.Add(TFltPr(Steps[i], 0.0));
364  MSE.Add(TFltPr(Steps[i], 0.0));
365  Accuracy.Add(TFltPr(Steps[i], 0.0));
366  PrecisionRecall.Add(TFltPr(0.0,0.0));
367  }
368 }
369 
370 void TNIBs::Reset() {
371  // reset vectors
372  for (int i=0; i<DiffAlphas.Len(); i++) {
373  DiffAlphas[i].Clr();
374  }
375  DiffAlphas.Clr();
376  AveDiffAlphas.Clr();
379 }
380 
381 void TNIBs::SG(const int& NId, const int& Iters, const TFltV& Steps, const TSampling& Sampling, const TStr& ParamSampling, const bool& PlotPerformance) {
382  bool verbose = false;
383  int currentCascade = -1;
384  TIntIntH SampledCascades;
385  TStrV ParamSamplingV; ParamSampling.SplitOnAllCh(';', ParamSamplingV);
386 
387  Reset();
388 
389  printf("Node %d\n", NId);
390 
391  // traverse through all times
392  for (int t=1; t<Steps.Len(); t++) {
393  // find cascades whose two first infections are earlier than Steps[t]
394  TIntFltH CascadesIdx;
395  int num_infections = 0;
396  for (int i=0; i<CascH.Len(); i++) {
397  if (CascH[i].LenBeforeT(Steps[t]) > 1 &&
398  ( (Sampling!=WIN_SAMPLING && Sampling!=WIN_EXP_SAMPLING) ||
399  (Sampling==WIN_SAMPLING && (Steps[t]-CascH[i].GetMinTm()) <= ParamSamplingV[0].GetFlt()) ||
400  (Sampling==WIN_EXP_SAMPLING && (Steps[t]-CascH[i].GetMinTm()) <= ParamSamplingV[0].GetFlt()) )) {
401  num_infections += CascH[i].LenBeforeT(Steps[t]);
402  CascadesIdx.AddDat(i) = CascH[i].GetMinTm();
403  }
404  }
405 
406  // if there are not recorded cascades by Steps[t], continue
407  if (CascadesIdx.Len()==0) {
408  printf("WARNING: No cascades recorded by %f!\n", Steps[t].Val);
409  if (PlotPerformance) { ComputePerformanceNId(NId, t, Steps); }
410  continue;
411  }
412 
413  // later cascades first
414  CascadesIdx.SortByDat(false);
415 
416  printf("Solving step %f: %d cascades, %d infections\n", Steps[t].Val, CascadesIdx.Len(), num_infections);
417  SampledCascades.Clr();
418 
419  // sampling cascades with no replacement
420  for (int i=0; i < Iters; i++) {
421  switch (Sampling) {
422  case UNIF_SAMPLING:
423  currentCascade = TInt::Rnd.GetUniDevInt(CascadesIdx.Len());
424  break;
425 
426  case WIN_SAMPLING:
427  currentCascade = TInt::Rnd.GetUniDevInt(CascadesIdx.Len());
428  break;
429 
430  case EXP_SAMPLING:
431  do {
432  currentCascade = (int)TFlt::Rnd.GetExpDev(ParamSamplingV[0].GetFlt());
433  } while (currentCascade > CascadesIdx.Len()-1);
434  break;
435 
436  case WIN_EXP_SAMPLING:
437  do {
438  currentCascade = (int)TFlt::Rnd.GetExpDev(ParamSamplingV[1].GetFlt());
439  } while (currentCascade > CascadesIdx.Len()-1);
440  break;
441 
442  case RAY_SAMPLING:
443  do {
444  currentCascade = (int)TFlt::Rnd.GetRayleigh(ParamSamplingV[0].GetFlt());
445  } while (currentCascade > CascadesIdx.Len()-1);
446  break;
447  }
448 
449  if (!SampledCascades.IsKey(currentCascade)) { SampledCascades.AddDat(currentCascade) = 0; }
450  SampledCascades.GetDat(currentCascade)++;
451 
452  if (verbose) { printf("Cascade %d sampled!\n", currentCascade); }
453 
454  // sampled cascade
455  TCascade &Cascade = CascH[CascadesIdx.GetKey(currentCascade)];
456 
457  // update gradient and alpha's
458  TIntPrV AlphasToUpdate;
459  UpdateDiff(OSG, NId, Cascade, AlphasToUpdate, Steps[t]);
460 
461  // update alpha's
462  for (int j=0; j<AlphasToUpdate.Len(); j++) {
463  if (InferredNetwork.IsEdge(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2) &&
464  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).IsKey(Steps[t])
465  ) {
466  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) -=
467  (Gamma * AveDiffAlphas.GetDat(AlphasToUpdate[j].Val1)
468  - (Regularizer==1? Mu*InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) : 0.0));
469 
470  // project into alpha >= 0
471  if (InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) < Tol) {
472  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) = Tol;
473  }
474 
475  // project into alpha <= MaxAlpha
476  if (InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) > MaxAlpha) {
477  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) = MaxAlpha;
478  }
479  }
480  }
481  if (verbose) { printf("%d transmission rates updated!\n", AlphasToUpdate.Len()); }
482  }
483 
484  printf("%d different cascades have been sampled for step %f!\n", SampledCascades.Len(), Steps[t].Val);
485 
486  // For alphas that did not get updated, copy last alpha value * aging factor
487  int unchanged = 0;
488  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
489  if (EI().IsKey(Steps[t]) || t == 0 || !EI().IsKey(Steps[t-1])) { continue; }
490 
491  EI().AddDat(Steps[t]) = Aging*EI().GetDat(Steps[t-1]);
492  unchanged++;
493  }
494  if (verbose) { printf("%d transmission rates that did not changed were 'aged' by %f!\n", unchanged, Aging.Val); }
495 
496  // compute performance on-the-fly
497  if (PlotPerformance) { ComputePerformanceNId(NId, t, Steps); }
498  }
499 }
500 
501 void TNIBs::BSG(const int& NId, const int& Iters, const TFltV& Steps, const int& BatchLen, const TSampling& Sampling, const TStr& ParamSampling, const bool& PlotPerformance) {
502  bool verbose = false;
503  int currentCascade = -1;
504  TIntIntH SampledCascades;
505  TStrV ParamSamplingV; ParamSampling.SplitOnAllCh(';', ParamSamplingV);
506 
507  Reset();
508 
509  printf("Node %d (|A|: %d)\n", NId, InferredNetwork.GetNodes());
510 
511  // traverse through all times (except 0.0; we use 0.0 to compute mse/mae since the inference is delayed)
512  for (int t=1; t<Steps.Len(); t++) {
513  // find cascades whose two first infections are earlier than Steps[t]
514  TIntFltH CascadesIdx;
515  int num_infections = 0;
516  for (int i = 0; i < CascH.Len(); i++) {
517  if (CascH[i].LenBeforeT(Steps[t]) > 1 &&
518  ( (Sampling!=WIN_SAMPLING && Sampling!=WIN_EXP_SAMPLING) ||
519  (Sampling==WIN_SAMPLING && (Steps[t]-CascH[i].GetMinTm()) <= ParamSamplingV[0].GetFlt()) ||
520  (Sampling==WIN_EXP_SAMPLING && (Steps[t]-CascH[i].GetMinTm()) <= ParamSamplingV[0].GetFlt()) )) {
521  num_infections += CascH[i].LenBeforeT(Steps[t]);
522  CascadesIdx.AddDat(i) = CascH[i].GetMinTm();
523  }
524  }
525 
526  // if there are not recorded cascades by Steps[t], continue
527  if (CascadesIdx.Len() == 0) {
528  printf("WARNING: No cascades recorded by %f!\n", Steps[t].Val);
529  if (PlotPerformance) { ComputePerformanceNId(NId, t, Steps); }
530  continue;
531  }
532 
533  printf("Solving step %f (%d cascades, %d infections)\n", Steps[t].Val,
534  CascadesIdx.Len(), num_infections);
535 
536  // sort cascade from most recent to least recent
537  CascadesIdx.SortByDat(false);
538 
539  // sampling cascades with no replacement
540  for (int i=0; i < Iters; i++) {
541  // alphas to update
542  TIntPrV AlphasToUpdate;
543 
544  // delete average gradients
545  AveDiffAlphas.Clr();
546 
547  // use all cascades for the average gradient
548  for (int c=0; c<BatchLen; c++) {
549  switch (Sampling) {
550  case UNIF_SAMPLING:
551  currentCascade = TInt::Rnd.GetUniDevInt(CascadesIdx.Len());
552  break;
553 
554  case WIN_SAMPLING:
555  currentCascade = TInt::Rnd.GetUniDevInt(CascadesIdx.Len());
556  break;
557 
558  case EXP_SAMPLING:
559  do {
560  currentCascade = (int)TFlt::Rnd.GetExpDev(ParamSamplingV[0].GetFlt());
561  } while (currentCascade > CascadesIdx.Len()-1);
562  break;
563 
564  case WIN_EXP_SAMPLING:
565  do {
566  currentCascade = (int)TFlt::Rnd.GetExpDev(ParamSamplingV[1].GetFlt());
567  } while (currentCascade > CascadesIdx.Len()-1);
568  break;
569 
570  case RAY_SAMPLING:
571  do {
572  currentCascade = (int)TFlt::Rnd.GetRayleigh(ParamSamplingV[0].GetFlt());
573  } while (currentCascade > CascadesIdx.Len()-1);
574  break;
575  }
576 
577  // sampled cascade
578  TCascade &Cascade = CascH[CascadesIdx.GetKey(currentCascade)];
579 
580  if (!SampledCascades.IsKey(currentCascade)) { SampledCascades.AddDat(currentCascade) = 0; }
581  SampledCascades.GetDat(currentCascade)++;
582 
583  // update gradient and alpha's
584  UpdateDiff(OBSG, NId, Cascade, AlphasToUpdate, Steps[t]);
585  }
586 
587  // update alpha's
588  for (int j=0; j<AlphasToUpdate.Len(); j++) {
589  if (InferredNetwork.IsEdge(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2) &&
590  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).IsKey(Steps[t])) {
591  switch (Regularizer) {
592  case 0:
593  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) -=
594  Gamma * (1.0/(double)BatchLen) * AveDiffAlphas.GetDat(AlphasToUpdate[j].Val1);
595  case 1:
596  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) =
597  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t])*(1.0-Mu*Gamma/(double)BatchLen)
598  - Gamma * (1.0/(double)BatchLen) * AveDiffAlphas.GetDat(AlphasToUpdate[j].Val1);
599  }
600 
601  // project into alpha >= 0
602  if (InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) < Tol) {
603  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) = Tol;
604  }
605 
606  // project into alpha <= MaxAlpha
607  if (InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) > MaxAlpha) {
608  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) = MaxAlpha;
609  }
610  }
611  }
612 
613  // for alphas that did not get updated, copy last alpha value
614  int unchanged = 0;
615  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
616  if (EI().IsKey(Steps[t]) || t == 0 || !EI().IsKey(Steps[t-1])) { continue; }
617 
618  EI().AddDat(Steps[t]) = EI().GetDat(Steps[t-1]);
619  unchanged++;
620  }
621  if (verbose) { printf("%d unchanged transmission rates updated!\n", unchanged); }
622  }
623 
624  printf("%d different cascades have been sampled for step %f!\n", SampledCascades.Len(), Steps[t].Val);
625 
626  // compute performance on-the-fly for each time step
627  if (PlotPerformance) { ComputePerformanceNId(NId, t, Steps); }
628  }
629 }
630 
631 void TNIBs::FG(const int& NId, const int& Iters, const TFltV& Steps) {
632  bool verbose = false;
633 
634  Reset();
635 
636  printf("Node %d (|A|: %d)\n", NId, InferredNetwork.GetNodes());
637 
638  // traverse through all times
639  for (int t=1; t<Steps.Len(); t++) {
640  // find cascades whose two first infections are earlier than Steps[t]
641  TIntFltH CascadesIdx;
642  int num_infections = 0;
643  for (int i=0; i<CascH.Len(); i++) {
644  if (CascH[i].LenBeforeT(Steps[t]) > 1) {
645  num_infections += CascH[i].LenBeforeT(Steps[t]);
646  CascadesIdx.AddDat(i) = CascH[i].GetMinTm();
647  }
648  }
649 
650  // if there are not recorded cascades by Steps[t], continue
651  if (CascadesIdx.Len()==0) {
652  printf("WARNING: No cascades recorded by %f!\n", Steps[t].Val);
653 // ComputePerformance(NId, Tol, t, Steps);
654  continue;
655  }
656 
657  printf("Solving step %f (%d cascades, %d infections)\n", Steps[t].Val, CascadesIdx.Len(), num_infections);
658 
659  // sort cascade from most recent to least recent
660  CascadesIdx.SortByDat(false);
661 
662  // sampling cascades with no replacement
663  for (int i=0; i < Iters; i++) {
664  // alphas to update
665  TIntPrV AlphasToUpdate;
666 
667  // delete average gradients
668  AveDiffAlphas.Clr();
669 
670  // use all cascades for the average gradient
671  for (int c=0; c<CascadesIdx.Len(); c++) {
672  // each cascade
673  TCascade &Cascade = CascH[CascadesIdx.GetKey(c)];
674 
675  // update gradient and alpha's
676  UpdateDiff(OBSG, NId, Cascade, AlphasToUpdate, Steps[t]);
677  }
678 
679  // update alpha's
680  for (int j=0; j<AlphasToUpdate.Len(); j++) {
681  if (InferredNetwork.IsEdge(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2) &&
682  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).IsKey(Steps[t])) {
683  switch (Regularizer) {
684  case 0:
685  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) -=
686  Gamma * (1.0/(double)CascadesIdx.Len()) * AveDiffAlphas.GetDat(AlphasToUpdate[j].Val1);
687  case 1:
688  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) =
689  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t])*(1.0-Mu*Gamma/(double)CascadesIdx.Len())
690  - Gamma * (1.0/(double)CascadesIdx.Len()) * AveDiffAlphas.GetDat(AlphasToUpdate[j].Val1);
691  }
692 
693  // project into alpha >= 0
694  if (InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) < Tol) {
695  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) = Tol;
696  }
697 
698  // project into alpha <= MaxAlpha
699  if (InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) > MaxAlpha) {
700  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) = MaxAlpha;
701  }
702  }
703  }
704 
705  // for alphas that did not get updated, copy last alpha value
706  int unchanged = 0;
707  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
708  if (EI().IsKey(Steps[t]) || t == 0 || !EI().IsKey(Steps[t-1])) { continue; }
709 
710  EI().AddDat(Steps[t]) = EI().GetDat(Steps[t-1]);
711  unchanged++;
712  }
713  if (verbose) { printf("%d unchanged transmission rates updated!\n", unchanged); }
714  }
715 
716  // compute performance on-the-fly for each time step
717  ComputePerformanceNId(NId, t, Steps);
718  }
719 }
720 
721 void TNIBs::UpdateDiff(const TOptMethod& OptMethod, const int& NId, TCascade& Cascade, TIntPrV& AlphasToUpdate, const double& CurrentTime) {
723 
724  double sum = 0.0;
725 
726  // we assume cascade is sorted & iterator returns in sorted order
727  if (Cascade.IsNode(NId) && Cascade.GetTm(NId) <= CurrentTime) {
728  for (THash<TInt, THitInfo>::TIter NI = Cascade.BegI(); NI < Cascade.EndI(); NI++) {
729  // consider only nodes that are earlier in time
730  if ( (Cascade.GetTm(NId)<=NI.GetDat().Tm) ||
731  (Cascade.GetTm(NId)-Delta<=NI.GetDat().Tm && Model==POW)
732  ) { break; }
733 
734  TIntPr Pair(NI.GetKey(), NId);
735 
736  // if edge/alpha doesn't exist, create
737  if (!InferredNetwork.IsEdge(Pair.Val1, Pair.Val2)) { InferredNetwork.AddEdge(Pair.Val1, Pair.Val2, TFltFltH()); }
738  if (!InferredNetwork.GetEDat(Pair.Val1, Pair.Val2).IsKey(CurrentTime)) {
739  InferredNetwork.GetEDat(Pair.Val1, Pair.Val2).AddDat(CurrentTime) = InitAlpha;
740  }
741 
742  switch(Model) {
743  case EXP: // exponential
744  sum += InferredNetwork.GetEDat(Pair.Val1, Pair.Val2).GetDat(CurrentTime).Val;
745  break;
746  case POW: // powerlaw
747  sum += InferredNetwork.GetEDat(Pair.Val1, Pair.Val2).GetDat(CurrentTime).Val/(Cascade.GetTm(NId)-NI.GetDat().Tm);
748  break;
749  case RAY: // rayleigh
750  sum += InferredNetwork.GetEDat(Pair.Val1, Pair.Val2).GetDat(CurrentTime).Val*(Cascade.GetTm(NId)-NI.GetDat().Tm);
751  break;
752  default:
753  sum = 0.0;
754  }
755  }
756  }
757 
758  // we assume cascade is sorted & iterator returns in sorted order
759  for (THash<TInt, THitInfo>::TIter NI = Cascade.BegI(); NI < Cascade.EndI(); NI++) {
760  // only consider nodes that are earlier in time if node belongs to the cascade
761  if ( Cascade.IsNode(NId) && (Cascade.GetTm(NId)<=NI.GetDat().Tm ||
762  (Cascade.GetTm(NId)-Delta<=NI.GetDat().Tm && Model==POW))
763  ) { break; }
764 
765  // consider infected nodes up to CurrentTime
766  if (NI.GetDat().Tm > CurrentTime) { break; }
767 
768  TIntPr Pair(NI.GetKey(), NId); // potential edge
769 
770  double val = 0.0;
771 
772  if (Cascade.IsNode(NId) && Cascade.GetTm(NId) <= CurrentTime) {
773  IAssert((Cascade.GetTm(NId) - NI.GetDat().Tm) > 0.0);
774 
775  switch(Model) { // compute gradients for infected
776  case EXP: // exponential
777  val = (Cascade.GetTm(NId) - NI.GetDat().Tm) - 1.0/sum;
778  break;
779  case POW: // powerlaw
780  val = log((Cascade.GetTm(NId) - NI.GetDat().Tm)/Delta) - 1.0/((Cascade.GetTm(NId)-NI.GetDat().Tm)*sum);
781  break;
782  case RAY: // rayleigh
783  val = TMath::Power(Cascade.GetTm(NId)-NI.GetDat().Tm, 2.0)/2.0 - (Cascade.GetTm(NId)-NI.GetDat().Tm)/sum;
784  break;
785  default:
786  val = 0.0;
787  }
788  } else { // compute gradients for non infected
789  IAssert((CurrentTime - NI.GetDat().Tm) >= 0.0);
790 
791  switch(Model) {
792  case EXP: // exponential
793  val = (CurrentTime-NI.GetDat().Tm);
794  // if every cascade was recorded up to a maximum Window cut-off
795  if ( (Window > -1) && (CurrentTime-Cascade.GetMinTm() > Window) ) { val = (Cascade.GetMinTm()+Window-NI.GetDat().Tm); }
796  break;
797  case POW: // power-law
798  val = TMath::Mx(log((CurrentTime-NI.GetDat().Tm)/Delta), 0.0);
799  // if every cascade was recorded up to a maximum Window cut-off
800  if ( (Window > -1) && (CurrentTime-Cascade.GetMinTm() > Window) ) { val = TMath::Mx(log((Cascade.GetMinTm()+Window-NI.GetDat().Tm)/Delta), 0.0); }
801  break;
802  case RAY: // rayleigh
803  val = TMath::Power(CurrentTime-NI.GetDat().Tm,2.0)/2.0;
804  // if every cascade was recorded up to a maximum Window cut-off
805  if ( (Window > -1) && (CurrentTime-Cascade.GetMinTm() > Window) ) { val = TMath::Power(Cascade.GetMinTm()+Window-NI.GetDat().Tm,2.0)/2.0; }
806  break;
807  default:
808  val = 0.0;
809  }
810  }
811 
812  if (!AveDiffAlphas.IsKey(Pair.Val1)) { AveDiffAlphas.AddDat(Pair.Val1) = 0.0; }
813 
814  switch (OptMethod) {
815  case OBSG:
816  case OEBSG:
817  case OFG:
818  // update stochastic average gradient (based on batch for OBSG and OEBSG and based on all cascades for FG)
819  AveDiffAlphas.GetDat(Pair.Val1) += val;
820  break;
821  case OSG:
822  case OESG:
823  // update stochastic gradient (we use a single gradient due to current cascade)
824  AveDiffAlphas.GetDat(Pair.Val1) = val;
825  default:
826  break;
827  }
828 
829  AlphasToUpdate.Add(Pair);
830  }
831 
832  return;
833 }
834 
835 void TNIBs::find_C( int t, TFltV &x, TFltVV &C, const int& k, const double& s, const double& gamma, const double& T ){
836  if ( t >= x.Len() ) return;
837  if ( t == 0 ){
838  C = TFltVV( x.Len(), k );
839  }else{
840  int n = x.Len() - 1;
841  for (int j = 0; j < k; j++){
842  double alpha = ( (x.Len() ) / T ) * pow( s, j );
843  double term_1 = -log(alpha) + alpha * x[t];
844  double term_2 = 0;
845  if ( t == 1 ){
846  term_2 = j * log((double) n) * gamma;
847  }
848  else{
849  bool first = false;
850  for (int l = 0; l < k; l++){
851  double my_val = C(t-1, l);
852  if ( j > l ) my_val += (j - l) * log((double) n) * gamma;
853  if ( !first || my_val < term_2 ){
854  term_2 = my_val;
855  first = true;
856  }
857  }
858  }
859  C( t, j ) = term_1 + term_2;
860  }
861  }
862  find_C( t + 1, x, C, k, s, gamma, T );
863 }
864 
865 void TNIBs::find_min_state( TFltVV &C, TIntV &states, const int& k, const double& s, const double& gamma, const double& T ){
866  states = TIntV( C.GetRows() );
867  states[0] = 0;
868  int n = C.GetRows() - 1;
869  for (int t = C.GetRows() - 1; t > 0; t --){
870  double best_val = 0;
871  int best_state = -1;
872  for (int j = 0; j < C.GetCols(); j++){
873  double c_state = C( t, j );
874  if ( t < C.GetRows() - 2 && states[t+1] > j ){
875  c_state += ( states[t+1] - j ) * gamma * log((double) n);
876  }
877  if ( best_state == -1 || best_val > c_state ){
878  best_state = j;
879  best_val = c_state;
880  }
881  }
882  states[t] = best_state;
883  }
884 }
885 
886 void TNIBs::LabelBurstAutomaton( const int& SrcId, const int& DstId, TIntV &state_labels, TFltV &state_times, const bool& inferred, const int& k, const double& s, const double& gamma, const TSecTm& MinTime, const TSecTm& MaxTime ){
887  TVec<TSecTm> arrival_times;
888  TFltFltH &LinksEdge = (inferred? InferredNetwork.GetEDat(SrcId, DstId) : Network.GetEDat(SrcId, DstId));
889 
890  for (int i=0; i<LinksEdge.Len(); i++) {
891  if (LinksEdge[i]>MinAlpha) {
892  TSecTm tsecs;
893  tsecs = (uint)LinksEdge.GetKey(i); // link rates is in seconds
894  if (tsecs > MaxTime || tsecs < MinTime) { continue; }
895  arrival_times.Add(tsecs);
896  }
897  }
898 
899  if ( arrival_times.Len() < 2 ) return;
900 
901  TFltV x;
902  x.Add( 0 );
903  arrival_times.Sort(true);
904  double T = ((double)arrival_times.Last().GetAbsSecs()) - ((double)arrival_times[0].GetAbsSecs());
905  for (int i = 1; i < arrival_times.Len(); i++){
906  x.Add( ((double)arrival_times[i].GetAbsSecs()) - ((double)arrival_times[i-1].GetAbsSecs()) );
907  }
908  TFltVV Cost_matrix;
909  //printf("arrivals = %d\n", x.Len() );
910  find_C( 0, x, Cost_matrix, k, s, gamma, T);
911 
912  find_min_state( Cost_matrix, state_labels, k, s, gamma, T );
913 
914  for (int i=0; i<state_labels.Len(); i++) { state_times.Add((double)arrival_times[i].GetAbsSecs()); }
915 }
916 
917 
918 void TNIBs::ComputePerformanceNId(const int& NId, const int& t, const TFltV& Steps) {
919  double CurrentMAE = 0.0;
920  double CurrentMSE = 0.0;
921  TFltPr CurrentPrecisionRecall(0.0, 0.0);
922  double CurrentAccD = 0.0;
923 
924  TStrFltFltHNEDNet::TNodeI NI = InferredNetwork.GetNI(NId);
925  for (int i=0; i<NI.GetInDeg(); i++) {
926  double inferredAlpha = InferredNetwork.GetEDat(NI.GetInNId(i), NId).GetDat(Steps[t]);
927  // we get the true alpha in the previous step (the inferred network contains delayed estimates)
928  double trueAlpha = 0.0;
929  if (Network.IsEdge(NI.GetInNId(i), NId) && Network.GetEDat(NI.GetInNId(i), NId).IsKey(Steps[t-1])) { trueAlpha = Network.GetEDat(NI.GetInNId(i), NId).GetDat(Steps[t-1]); }
930 
931  // accuracy (denominator)
932  CurrentAccD += (double) (inferredAlpha > MinAlpha);
933 
934  // precision
935  CurrentPrecisionRecall.Val2 += (double) (inferredAlpha > MinAlpha && trueAlpha<MinAlpha);
936  }
937 
938  NI = Network.GetNI(NId);
939  int NumEdges = 0;
940  for (int i=0; i<NI.GetInDeg(); i++) {
941  TIntPr Pair(NI.GetInNId(i), NId);
942 
943  // we get the inferred Alpha if any
944  double inferredAlpha = 0.0;
945  if (InferredNetwork.IsEdge(NI.GetInNId(i), NId) && InferredNetwork.GetEDat(NI.GetInNId(i), NId).IsKey(Steps[t])) {
946  inferredAlpha = InferredNetwork.GetEDat(NI.GetInNId(i), NId).GetDat(Steps[t]).Val;
947  }
948 
949  // we get the true alpha in the previous step (the inferred network contains delayed estimates)
950  double trueAlpha = 0.0;
951  if (Network.GetEDat(NI.GetInNId(i), NId).IsKey(Steps[t-1])) { trueAlpha = Network.GetEDat(NI.GetInNId(i), NId).GetDat(Steps[t-1]); }
952 
953  // mae
954  if (trueAlpha > MinAlpha) {
955  NumEdges++;
956  CurrentMAE += fabs(trueAlpha - TFlt::GetMn(inferredAlpha, MaxAlpha))/trueAlpha;
957  }
958 
959  // mse
960  CurrentMSE += pow(trueAlpha - TFlt::GetMn(inferredAlpha, MaxAlpha), 2.0);
961 
962  // recall
963  CurrentPrecisionRecall.Val1 += (double) (inferredAlpha > MinAlpha && trueAlpha > MinAlpha);
964  }
965 
966  if (NumEdges > 0) {
967  MAE[t-1].Val2 += CurrentMAE / ((double)(NumEdges*Network.GetNodes()));
968  MSE[t-1].Val2 += CurrentMSE / ((double)(NumEdges*Network.GetNodes()));
969  PrecisionRecall[t-1].Val1 += CurrentPrecisionRecall.Val1/(double)(NumEdges*Network.GetNodes());
970  }
971 
972  if (CurrentAccD > 0) {
973  PrecisionRecall[t-1].Val2 += (1.0 - CurrentPrecisionRecall.Val2 / CurrentAccD)/(double)Network.GetNodes();
974  } else {
975  PrecisionRecall[t-1].Val2 += 1.0/(double)Network.GetNodes();
976  }
977 
978  Accuracy[t-1].Val2 = 1.0 - (1.0-PrecisionRecall[t-1].Val2)/(PrecisionRecall[t-1].Val2 * (1.0/PrecisionRecall[t-1].Val2 + 1.0/PrecisionRecall[t-1].Val1)) - (1.0-PrecisionRecall[t-1].Val1)/(PrecisionRecall[t-1].Val1* (1.0/PrecisionRecall[t-1].Val2 + 1.0/PrecisionRecall[t-1].Val1));
979 }
980 
981 void TNIBs::SaveInferredPajek(const TStr& OutFNm, const double& Step, const TIntV& NIdV) {
982  TFOut FOut(OutFNm);
983  FOut.PutStr(TStr::Fmt("*Vertices %d\r\n", NodeNmH.Len()));
984  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
985  if (NIdV.Len() > 0 && !NIdV.IsIn(NI.GetKey())) { continue; }
986 
987  FOut.PutStr(TStr::Fmt("%d \"%s\" ic Blue\r\n", NI.GetKey().Val+1, NI.GetDat().Name.CStr()));
988  }
989  FOut.PutStr("*Arcs\r\n");
990  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
991  if (NIdV.Len() > 0 && (!NIdV.IsIn(EI.GetSrcNId()) || !NIdV.IsIn(EI.GetDstNId()))) { continue; }
992  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
993 
994  double inferredAlpha = 0.0;
995  if (EI().IsKey(Step)) { inferredAlpha = EI().GetDat(Step); }
996 
997  if (inferredAlpha > MinAlpha) {
998  FOut.PutStr(TStr::Fmt("%d %d %f\r\n", EI.GetSrcNId()+1, EI.GetDstNId()+1, (inferredAlpha > MaxAlpha? MaxAlpha.Val : inferredAlpha)));
999  }
1000  }
1001 }
1002 
1003 void TNIBs::SaveInferred(const TStr& OutFNm, const TIntV& NIdV) {
1004  TFOut FOut(OutFNm);
1005 
1006  // write nodes to file
1007  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
1008  if (NIdV.Len() > 0 && !NIdV.IsIn(NI.GetKey())) { continue; }
1009 
1010  FOut.PutStr(TStr::Fmt("%d,%s\r\n", NI.GetKey().Val, NI.GetDat().Name.CStr()));
1011  }
1012 
1013  FOut.PutStr("\r\n");
1014 
1015  // write edges to file (not allowing self loops in the network)
1016  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
1017  if (NIdV.Len() > 0 && (!NIdV.IsIn(EI.GetSrcNId()) || !NIdV.IsIn(EI.GetDstNId()))) { continue; }
1018  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
1019 
1020  // not allowing self loops in the Kronecker network
1021  if (EI.GetSrcNId() != EI.GetDstNId()) {
1022  if (EI().Len() > 0) {
1023  TStr Line; bool IsEdge = false;
1024  for (int i=0; i<EI().Len(); i++) {
1025  if (EI()[i]>MinAlpha) {
1026  Line += TStr::Fmt(",%f,%f", EI().GetKey(i).Val, (EI()[i] > MaxAlpha? MaxAlpha.Val : EI()[i].Val) );
1027  IsEdge = true;
1028  } else { // we write 0 explicitly
1029  Line += TStr::Fmt(",%f,0.0", EI().GetKey(i).Val);
1030  }
1031  }
1032  // if none of the alphas is bigger than 0, no edge is written
1033  if (IsEdge) {
1034  FOut.PutStr(TStr::Fmt("%d,%d", EI.GetSrcNId(), EI.GetDstNId()));
1035  FOut.PutStr(Line);
1036  FOut.PutStr("\r\n");
1037  }
1038  }
1039  else
1040  FOut.PutStr(TStr::Fmt("%d,%d,1\r\n", EI.GetSrcNId(), EI.GetDstNId()));
1041  }
1042  }
1043 }
1044 
1045 void TNIBs::SaveInferred(const TStr& OutFNm, const double& Step, const TIntV& NIdV) {
1046  TFOut FOut(OutFNm);
1047 
1048  // write nodes to file
1049  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
1050  if (NIdV.Len() > 0 && !NIdV.IsIn(NI.GetKey())) { continue; }
1051 
1052  FOut.PutStr(TStr::Fmt("%d,%s\r\n", NI.GetKey().Val, NI.GetDat().Name.CStr()));
1053  }
1054  FOut.PutStr("\r\n");
1055 
1056  // write edges to file (not allowing self loops in the network)
1057  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
1058  if (NIdV.Len() > 0 && (!NIdV.IsIn(EI.GetSrcNId()) || !NIdV.IsIn(EI.GetDstNId()))) { continue; }
1059  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
1060 
1061  // not allowing self loops in the Kronecker network
1062  if (EI.GetSrcNId() != EI.GetDstNId()) {
1063  double inferredAlpha = 0.0;
1064  if (EI().IsKey(Step)) { inferredAlpha = EI().GetDat(Step); }
1065 
1066  if (inferredAlpha > MinAlpha) {
1067  FOut.PutStr(TStr::Fmt("%d,%d,%f\r\n", EI.GetSrcNId(), EI.GetDstNId(), (inferredAlpha > MaxAlpha? MaxAlpha.Val : inferredAlpha)));
1068  }
1069  }
1070  }
1071 }
1072 
1073 void TNIBs::SaveInferredEdges(const TStr& OutFNm) {
1074  TFOut FOut(OutFNm);
1075 
1076  // write edges to file (not allowing self loops in the network)
1077  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
1078  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
1079 
1080  // not allowing self loops in the Kronecker network
1081  if (EI.GetSrcNId() != EI.GetDstNId()) {
1082  if (EI().Len() > 0) {
1083  TStr Line; bool IsEdge = false;
1084  for (int i=0; i<EI().Len(); i++) {
1085  if (EI()[i]>MinAlpha) {
1086  Line += TStr::Fmt(",%f,%f", EI().GetKey(i).Val, (EI()[i] > MaxAlpha? MaxAlpha.Val : EI()[i].Val) );
1087  IsEdge = true;
1088  } else { // we write 0 explicitly
1089  Line += TStr::Fmt(",%f,0.0", EI().GetKey(i).Val);
1090  }
1091  }
1092  // if none of the alphas is bigger than 0, no edge is written
1093  if (IsEdge) {
1094  FOut.PutStr(TStr::Fmt("%d,%d", EI.GetSrcNId(), EI.GetDstNId()));
1095  FOut.PutStr(Line);
1096  FOut.PutStr("\r\n");
1097  }
1098  }
1099  else
1100  FOut.PutStr(TStr::Fmt("%d,%d,1\r\n", EI.GetSrcNId(), EI.GetDstNId()));
1101  }
1102  }
1103 }
1104 
1105 void TNIBs::SaveGroundTruth(const TStr& OutFNm) {
1106  TFOut FOut(OutFNm);
1107 
1108  // write nodes to file
1109  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
1110  FOut.PutStr(TStr::Fmt("%d,%s\r\n", NI.GetKey().Val, NI.GetDat().Name.CStr()));
1111  }
1112 
1113  FOut.PutStr("\r\n");
1114 
1115  // write edges to file (not allowing self loops in the network)
1116  for (TStrFltFltHNEDNet::TEdgeI EI = Network.BegEI(); EI < Network.EndEI(); EI++) {
1117  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
1118 
1119  // not allowing self loops in the Kronecker network
1120  if (EI.GetSrcNId() != EI.GetDstNId()) {
1121  if (EI().Len() > 0) {
1122  FOut.PutStr(TStr::Fmt("%d,%d,", EI.GetSrcNId(), EI.GetDstNId()));
1123  for (int i=0; i<EI().Len()-1; i++) { FOut.PutStr(TStr::Fmt("%f,%f,", EI().GetKey(i).Val, EI()[i].Val)); }
1124  FOut.PutStr(TStr::Fmt("%f,%f", EI().GetKey(EI().Len()-1).Val, EI()[EI().Len()-1].Val));
1125  FOut.PutStr("\r\n");
1126  }
1127  else
1128  FOut.PutStr(TStr::Fmt("%d,%d,1\r\n", EI.GetSrcNId(), EI.GetDstNId()));
1129  }
1130  }
1131 }
1132 
1133 void TNIBs::SaveGroundTruthPajek(const TStr& OutFNm, const double& Step) {
1134  TFOut FOut(OutFNm);
1135 
1136  FOut.PutStr(TStr::Fmt("*Vertices %d\r\n", NodeNmH.Len()));
1137  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
1138  FOut.PutStr(TStr::Fmt("%d \"%s\" ic Blue\r\n", NI.GetKey().Val+1, NI.GetDat().Name.CStr()));
1139  }
1140  FOut.PutStr("*Arcs\r\n");
1141  for (TStrFltFltHNEDNet::TEdgeI EI = Network.BegEI(); EI < Network.EndEI(); EI++) {
1142  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
1143  double trueAlpha = 0.0;
1144  if (EI().IsKey(Step)) { trueAlpha = EI().GetDat(Step); }
1145  else { for (int j=0; j<EI().Len() && EI().GetKey(j)<=Step; j++) { trueAlpha = EI()[j]; } }
1146 
1147  if (trueAlpha > MinAlpha) {
1148  FOut.PutStr(TStr::Fmt("%d %d %f\r\n", EI.GetSrcNId()+1, EI.GetDstNId()+1, (trueAlpha > MaxAlpha? MaxAlpha.Val : trueAlpha)));
1149  }
1150  }
1151 }
1152 
1153 void TNIBs::SaveSites(const TStr& OutFNm, const TIntFltVH& CascadesPerNode) {
1154  TFOut FOut(OutFNm);
1155 
1156  // write nodes to file
1157  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
1158  FOut.PutStr(TStr::Fmt("%d,%s", NI.GetKey().Val, NI.GetDat().Name.CStr()));
1159  if (CascadesPerNode.IsKey(NI.GetKey().Val)) {
1160  for (int i=0; i<CascadesPerNode.GetDat(NI.GetKey().Val).Len(); i++) {
1161  FOut.PutStr(TStr::Fmt(",%f", CascadesPerNode.GetDat(NI.GetKey().Val)[i].Val));
1162  }
1163  }
1164  FOut.PutStr("\r\n");
1165  }
1166 }
1167 
1168 void TNIBs::SaveCascades(const TStr& OutFNm) {
1169  TFOut FOut(OutFNm);
1170 
1171  // write nodes to file
1172  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
1173  FOut.PutStr(TStr::Fmt("%d,%s\r\n", NI.GetKey().Val, NI.GetDat().Name.CStr()));
1174  }
1175 
1176  FOut.PutStr("\r\n");
1177 
1178  // write cascades to file
1179  for (THash<TInt, TCascade>::TIter CI = CascH.BegI(); CI < CascH.EndI(); CI++) {
1180  TCascade &C = CI.GetDat();
1181  int j = 0;
1182  for (THash<TInt, THitInfo>::TIter NI = C.NIdHitH.BegI(); NI < C.NIdHitH.EndI(); NI++) {
1183  if (!NodeNmH.IsKey(NI.GetDat().NId)) { continue; }
1184  if (j > 0) { FOut.PutStr(TStr::Fmt(",%d,%f", NI.GetDat().NId.Val, NI.GetDat().Tm.Val)); }
1185  else { FOut.PutStr(TStr::Fmt("%d;%d,%f", CI.GetKey().Val, NI.GetDat().NId.Val, NI.GetDat().Tm.Val)); }
1186  j++;
1187  }
1188 
1189  if (j >= 1)
1190  FOut.PutStr(TStr::Fmt("\r\n"));
1191  }
1192 }
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:708
#define IAssert(Cond)
Definition: bd.h:262
void BSG(const int &NId, const int &Iters, const TFltV &Steps, const int &BatchLen, const TSampling &Sampling, const TStr &ParamSampling=TStr(""), const bool &PlotPerformance=false)
void SaveGroundTruth(const TStr &OutFNm)
void SaveInferred(const TStr &OutFNm, const TIntV &NIdV=TIntV())
void Randomize()
Definition: dt.h:60
TNodeInfo GetNodeInfo(const int &NId) const
Definition: cascdynetinf.h:217
TIntIntPrH SampledCascadesH
Definition: cascdynetinf.h:166
void SaveGroundTruthPajek(const TStr &OutFNm, const double &Step)
TFlt Mu
Definition: cascdynetinf.h:153
int GetEdges() const
Returns the number of edges in the network.
Definition: network.h:898
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the network.
Definition: network.h:758
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
int Val
Definition: dt.h:1139
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:481
TFlt TotalTime
Definition: cascdynetinf.h:147
bool IsIn(const TVal &Val) const
Checks whether element Val is a member of the vector.
Definition: ds.h:828
void Init(const TFltV &Steps)
THash< TInt, TCascade > CascH
Definition: cascdynetinf.h:132
unsigned int uint
Definition: bd.h:11
THash< TInt, THitInfo >::TIter EndI() const
Definition: cascdynetinf.h:102
int Len() const
Definition: cascdynetinf.h:97
int AddNode(int NId=-1)
Adds a node of ID NId to the network.
Definition: network.h:836
TStrFltFltHNEDNet Network
Definition: cascdynetinf.h:141
TStrFltFltHNEDNet InferredNetwork
Definition: cascdynetinf.h:158
TFlt MaxAlpha
Definition: cascdynetinf.h:155
void LoadInferredNodesTxt(TSIn &SIn)
TIter BegI() const
Definition: hash.h:213
void LoadCascadesTxt(TSIn &SIn)
Definition: cascdynetinf.cpp:4
double Val
Definition: dt.h:1388
Definition: fl.h:319
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash< TInt, TNodeInfo > NodeNmH
Definition: cascdynetinf.h:133
TModel
Definition: cascdynetinf.h:7
void AddCasc(const TStr &CascStr, const TModel &Model=EXP)
TFlt Window
Definition: cascdynetinf.h:147
void LoadGroundTruthTxt(TSIn &SIn)
double GetRayleigh(const double &Sigma)
Definition: dt.h:50
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
THash< TInt, THitInfo > NIdHitH
Definition: cascdynetinf.h:87
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
bool GetEDat(const int &SrcNId, const int &DstNId, TEdgeData &EdgeDat) const
Returns edge data in Data for the edge from node IDs SrcNId to DstNId.
Definition: network.h:953
TIter EndI() const
Definition: hash.h:218
void GetInferredGraphAtT(const double &Step, PNGraph &GraphAtT)
static TRnd Rnd
Definition: dt.h:1146
TIntFltH AveDiffAlphas
Definition: cascdynetinf.h:162
const TKey & GetKey() const
Definition: hash.h:80
void SaveInferredPajek(const TStr &OutFNm, const double &Step, const TIntV &NIdV=TIntV())
double GetMinTm() const
Definition: cascdynetinf.h:106
TFlt Delta
Definition: cascdynetinf.h:150
Definition: fl.h:58
static PNet New()
Static constructor that returns a pointer to the network. Call: TPt > Net = TNodeEDatNet::New().
Definition: network.h:661
TFltPrV PrecisionRecall
Definition: cascdynetinf.h:169
double GetTm(const int &NId) const
Definition: cascdynetinf.h:104
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the network.
Definition: network.h:906
TFlt MinAlpha
Definition: cascdynetinf.h:155
TFlt Gamma
Definition: cascdynetinf.h:153
void Clr(const bool &DoDel=true, const bool &ResetDat=true)
Deletes all nodes and edges from the network.
Definition: network.h:786
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
const TDat & GetDat() const
Definition: hash.h:81
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the network.
Definition: network.h:714
double GetExpDev()
Definition: dt.cpp:83
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the network.
Definition: network.h:756
virtual bool Eof()=0
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
TOptMethod
Definition: cascdynetinf.h:27
TFltPrV MSE
Definition: cascdynetinf.h:170
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the network.
Definition: network.h:939
TVVec< TFlt > TFltVV
Definition: ds.h:2403
void SG(const int &NId, const int &Iters, const TFltV &Steps, const TSampling &Sampling, const TStr &ParamSampling=TStr(""), const bool &PlotPerformance=false)
uint GetAbsSecs() const
Definition: tm.h:150
static double Power(const double &Base, const double &Exponent)
Definition: xmath.h:25
void LoadInferredTxt(TSIn &SIn)
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
void GenCascade(TCascade &C)
void ComputePerformanceNId(const int &NId, const int &Step, const TFltV &Steps)
void FG(const int &NId, const int &Iters, const TFltV &Steps)
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the network.
Definition: network.h:777
TStrIntH DomainsIdH
Definition: cascdynetinf.h:134
TSizeTy GetRows() const
Definition: ds.h:2252
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
TFlt InitAlpha
Definition: cascdynetinf.h:155
void SaveSites(const TStr &OutFNm, const TIntFltVH &CascadesPerNode=TIntFltVH())
TFltPrV Accuracy
Definition: cascdynetinf.h:170
void SaveInferredEdges(const TStr &OutFNm)
void GetInferredNetworkAtT(const double &Step, PStrFltNEDNet &NetworkAtT)
bool IsNodeNm(const int &NId) const
Definition: cascdynetinf.h:218
void Clr()
Definition: cascdynetinf.h:95
void GetGroundTruthNetworkAtT(const double &Step, PStrFltNEDNet &NetworkAtT)
void Reset()
Definition: tm.h:81
Definition: ds.h:32
TFlt Aging
Definition: cascdynetinf.h:153
static double GetMn(const double &Flt1, const double &Flt2)
Definition: dt.h:1437
void UpdateDiff(const TOptMethod &OptMethod, const int &NId, TCascade &Cascade, TIntPrV &AlphasToUpdate, const double &CurrentTime=TFlt::Mx)
void find_C(int t, TFltV &x, TFltVV &C, const int &k, const double &s, const double &gamma, const double &T)
THash< TInt, THitInfo >::TIter BegI() const
Definition: cascdynetinf.h:101
Definition: dt.h:412
void LoadGroundTruthNodesTxt(TSIn &SIn)
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TFltPrV MAE
Definition: cascdynetinf.h:170
void Add(const int &NId, const double &HitTm)
Definition: cascdynetinf.h:107
int PutStr(const char *CStr)
Definition: fl.cpp:117
void SplitOnAllCh(const char &SplitCh, TStrV &StrV, const bool &SkipEmpty=true) const
Definition: dt.cpp:926
Definition: hash.h:97
TRegularizer Regularizer
Definition: cascdynetinf.h:154
void LabelBurstAutomaton(const int &SrcId, const int &DstId, TIntV &state_labels, TFltV &state_times, const bool &inferred=false, const int &k=5, const double &s=2.0, const double &gamma=1.0, const TSecTm &MinTime=TSecTm(), const TSecTm &MaxTime=TSecTm())
double GetUniDev()
Definition: dt.h:30
TVal1 Val1
Definition: ds.h:34
TVal2 Val2
Definition: ds.h:35
TVec< TInt > TIntV
Definition: ds.h:1594
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
void SaveCascades(const TStr &OutFNm)
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
TSampling
Definition: cascdynetinf.h:40
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
void Sort()
Definition: cascdynetinf.h:110
TSizeTy GetCols() const
Definition: ds.h:2253
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
void AddNodeNm(const int &NId, const TNodeInfo &Info)
Definition: cascdynetinf.h:215
THash< TInt, TIntFltH > DiffAlphas
Definition: cascdynetinf.h:163
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
void GetGroundTruthGraphAtT(const double &Step, PNGraph &GraphAtT)
bool IsNode(const int &NId) const
Definition: cascdynetinf.h:109
double GetPowerDev(const double &AlphaSlope)
Definition: dt.h:47
void find_min_state(TFltVV &C, TIntV &states, const int &k, const double &s, const double &gamma, const double &T)
static TRnd Rnd
Definition: dt.h:1396
TModel Model
Definition: cascdynetinf.h:144
TFlt Tol
Definition: cascdynetinf.h:155
int GetNodes() const
Returns the number of nodes in the network.
Definition: network.h:680
bool GetNextLn(TStr &LnStr)
Definition: fl.cpp:43
TIntFltH TotalCascadesAlpha
Definition: cascdynetinf.h:159
void SortByDat(const bool &Asc=true)
Definition: hash.h:292