SNAP Library , Developer Reference  2013-01-07 14:03:36
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
cascnetinf.h
Go to the documentation of this file.
00001 #ifndef snap_cascnetinf_h
00002 #define snap_cascnetinf_h
00003 
00004 #include "Snap.h"
00005 
00006 // Hit info (timestamp, candidate parent) about a node in a cascade
00007 class THitInfo {
00008 public:
00009   TInt NId, Parent;
00010   TFlt Tm;
00011 public:
00012   THitInfo(const int& NodeId=-1, const double& HitTime=0) : NId(NodeId), Parent(-1), Tm(HitTime) { }
00013   THitInfo(TSIn& SIn) : NId(SIn), Parent(SIn), Tm(SIn) { }
00014   void Save(TSOut& SOut) const { NId.Save(SOut); Parent.Save(SOut); Tm.Save(SOut); }
00015   bool operator < (const THitInfo& Hit) const {
00016     return Tm < Hit.Tm; }
00017 };
00018 
00019 // Cascade
00020 class TCascade {
00021 public:
00022   THash<TInt, THitInfo> NIdHitH;
00023   TFlt CurProb, Alpha, Eps;
00024   TInt Model;
00025 public:
00026   TCascade() : NIdHitH(), CurProb(0), Alpha(1.0), Eps(1e-64), Model(0) { }
00027   TCascade(const double &alpha) : NIdHitH(), CurProb(0), Alpha(alpha), Eps(1e-64), Model(0) { }
00028   TCascade(const double &alpha, const int &model) : NIdHitH(), CurProb(0), Alpha(alpha), Eps(1e-64), Model(model) { }
00029   TCascade(const double &alpha, const double &eps) : NIdHitH(), CurProb(0), Alpha(alpha), Eps(eps), Model(0) { }
00030   TCascade(const double &alpha, const int &model, const double &eps) : NIdHitH(), CurProb(0), Alpha(alpha), Eps(eps), Model(model) { }
00031   TCascade(TSIn& SIn) : NIdHitH(SIn), CurProb(SIn), Alpha(SIn) { }
00032   void Save(TSOut& SOut) const  { NIdHitH.Save(SOut); CurProb.Save(SOut); Alpha.Save(SOut); }
00033   void Clr() { NIdHitH.Clr(); CurProb = 0; Alpha = 1.0; }
00034   int Len() const { return NIdHitH.Len(); }
00035   int GetNode(const int& i) const { return NIdHitH.GetKey(i); }
00036   int GetParent(const int NId) const { return NIdHitH.GetDat(NId).Parent; }
00037   double GetAlpha() const { return Alpha; }
00038   double GetTm(const int& NId) const { return NIdHitH.GetDat(NId).Tm; }
00039   void Add(const int& NId, const double& HitTm) { NIdHitH.AddDat(NId, THitInfo(NId, HitTm)); }
00040   void Del(const int& NId) { NIdHitH.DelKey(NId); }
00041   bool IsNode(const int& NId) const { return NIdHitH.IsKey(NId); }
00042   void Sort() { NIdHitH.SortByDat(true); }
00043   double TransProb(const int& NId1, const int& NId2) const;
00044   double GetProb(const PNGraph& G);
00045   void InitProb();
00046   double UpdateProb(const int& N1, const int& N2, const bool& UpdateProb=false);
00047 };
00048 
00049 // Node info (name and number of cascades)
00050 class TNodeInfo {
00051 public:
00052   TStr Name;
00053   TInt Vol;
00054 public:
00055   TNodeInfo() { }
00056   TNodeInfo(const TStr& NodeNm, const int& Volume) : Name(NodeNm), Vol(Volume) { }
00057   TNodeInfo(TSIn& SIn) : Name(SIn), Vol(SIn) { }
00058   void Save(TSOut& SOut) const { Name.Save(SOut); Vol.Save(SOut); }
00059 };
00060 
00061 // Edge info (name and number of cascades)
00062 class TEdgeInfo {
00063 public:
00064   TInt Vol;
00065   TFlt MarginalGain, MarginalBound, MedianTimeDiff, AverageTimeDiff; // we can skip MarginalBound for efficiency if not explicitly required
00066 public:
00067   TEdgeInfo() { }
00068   TEdgeInfo(const int& v,
00069         const double& mg,
00070         const double& mb,
00071         const double& mt,
00072       const double& at) : Vol(v), MarginalGain(mg), MarginalBound(mb), MedianTimeDiff(mt), AverageTimeDiff(at) { }
00073   TEdgeInfo(const int& v,
00074         const double& mg,
00075         const double& mt,
00076       const double& at) : Vol(v), MarginalGain(mg), MarginalBound(0), MedianTimeDiff(mt), AverageTimeDiff(at) { }
00077   TEdgeInfo(TSIn& SIn) : Vol(SIn), MarginalGain(SIn), MarginalBound(SIn), MedianTimeDiff(SIn), AverageTimeDiff(SIn) { }
00078   void Save(TSOut& SOut) const { Vol.Save(SOut); SOut.Save(MarginalGain); SOut.Save(MarginalBound); SOut.Save(MedianTimeDiff); SOut.Save(AverageTimeDiff); } //
00079 };
00080 
00081 // NETINF algorithm class
00082 class TNetInfBs {
00083 public:
00084   TVec<TCascade> CascV;
00085   THash<TInt, TNodeInfo> NodeNmH;
00086   THash<TIntPr, TEdgeInfo> EdgeInfoH;
00087   TVec<TPair<TFlt, TIntPr> > EdgeGainV;
00088 
00089   THash<TIntPr, TIntV> CascPerEdge; // To implement localized update
00090   PNGraph Graph, GroundTruth;
00091   bool BoundOn, CompareGroundTruth;
00092   TFltPrV PrecisionRecall;
00093 
00094   TIntPrFltH Alphas, Betas;
00095 
00096 public:
00097   TNetInfBs( ) { BoundOn = false; CompareGroundTruth=false; }
00098   TNetInfBs(bool bo, bool cgt) { BoundOn=bo; CompareGroundTruth=cgt; }
00099   TNetInfBs(TSIn& SIn) : CascV(SIn), NodeNmH(SIn) { }
00100   void Save(TSOut& SOut) const { CascV.Save(SOut); NodeNmH.Save(SOut); }
00101 
00102   void LoadCascadesTxt(TSIn& SIn, const int& Model, const double& alpha);
00103   void LoadGroundTruthTxt(TSIn& SIn);
00104 
00105   void AddGroundTruth(PNGraph& gt) { GroundTruth = gt; }
00106   
00107   void AddCasc(const TStr& CascStr, const int& Model=0, const double& alpha=1.0);
00108   void AddCasc(const TCascade& Cascade) { CascV.Add(Cascade); }
00109   void GenCascade(TCascade& C, const int& TModel, const double &window, TIntPrIntH& EdgesUsed, const double& delta,
00110                  const double& std_waiting_time=0, const double& std_beta=0);
00111   TCascade & GetCasc(int c) { return CascV[c]; }
00112   int GetCascs() { return CascV.Len(); }
00113 
00114   int GetNodes() { return Graph->GetNodes(); }
00115   void AddNodeNm(const int& NId, const TNodeInfo& Info) { NodeNmH.AddDat(NId, Info); }
00116   TStr GetNodeNm(const int& NId) const { return NodeNmH.GetDat(NId).Name; }
00117   TNodeInfo GetNodeInfo(const int& NId) const { return NodeNmH.GetDat(NId); }
00118   bool IsNodeNm(const int& NId) const { return NodeNmH.IsKey(NId); }
00119 
00120   void Init();
00121   double GetAllCascProb(const int& EdgeN1, const int& EdgeN2);
00122   TIntPr GetBestEdge(double& CurProb, double& LastGain, bool& msort, int &attempts);
00123   double GetBound(const TIntPr& Edge, double& CurProb);
00124   void GreedyOpt(const int& MxEdges);
00125 
00126   void SavePajek(const TStr& OutFNm);
00127   void SavePlaneTextNet(const TStr& OutFNm);
00128   void SaveEdgeInfo(const TStr& OutFNm);
00129   void SaveObjInfo(const TStr& OutFNm);
00130 
00131   void SaveGroundTruth(const TStr& OutFNm);
00132   void SaveCascades(const TStr& OutFNm);
00133 };
00134 
00135 #endif