Earliest Infection First#
- cosasi.source_inference.single_source.earliest_infection_first.earliest_infection_first(I, G, observer_dict)#
Implements the Earliest Infection First algorithm to score all nodes in I.
This algorithm is useful if some infection timestamp information is available.
- Parameters
I (NetworkX Graph) – The infection subgraph observed at a particular time step
G (NetworkX Graph) – The original graph the infection process was run on. I is a subgraph of G induced by infected vertices at observation time.
observer_dict (dict) – observers dictionary, a la contagion.get_observers()
Notes
This is the greedy algorithm outlined in Section 3 of [1]. We iterate over rooting schemes and score each source hypothesis by the cost of their corresponding EIF spreading tree. In particular, we implement the “cost-based ranking” approach described in Section 4 of [1].
References
- 1(1,2)
K. Zhu, Z. Chen, L. Ying, “Locating Contagion Sources in Networks with Partial Timestamps” Data Mining and Knowledge Discovery, 2016 https://link.springer.com/article/10.1007/s10618-015-0435-9
- cosasi.source_inference.single_source.earliest_infection_first.eif_root(root, I, G, observers, mu, alpha, only_return_cost=True)#
Computes the cost of a greedy EIF spreading tree whose “patient zero” is root.
- Parameters
root (graph index - str, int, etc.) – The vertex rooting
I (NetworkX Graph) – The infection subgraph observed at a particular time step
G (NetworkX Graph) – The original graph the infection process was run on. I is a subgraph of G induced by infected vertices at observation time.
observers (dict) – observers dictionary, a la contagion.get_observers()
mu (float) – a constant, estimated by _estimate_mu()
alpha (list) – list of vertices in observers dictionary, sorted from earliest to latest timestamp-wise
only_return_cost (bool) – if True, only returns the calculated spreading tree’s cost
Notes
This is the greedy algorithm outlined in Section 3 of [1].
References
- 1
K. Zhu, Z. Chen, L. Ying, “Locating Contagion Sources in Networks with Partial Timestamps” Data Mining and Knowledge Discovery, 2016 https://link.springer.com/article/10.1007/s10618-015-0435-9