Short-Fat-Tree#
- cosasi.source_inference.single_source.short_fat_tree.short_fat_tree(I, G, infection_rate=0.1)#
Implements the Short-Fat-Tree (SFT) algorithm to score all nodes in G.
- 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.
infection_rate (float (optional)) – Inter-node infection efficiency from the original contagion process must be in [0, 1]
Examples
>>> result = cosasi.single_source.short_fat_tree(I, G)
Notes
Algorithm attempts to find infection center by identifying the vertex with largest weighted boundary node degree. The algorithm was introduced in [1].
Nodes outside the infection subgraph receive a score of negative infinity.
References
- 1
K. Zhu and L. Ying, “Information source detection in the SIR model: A sample-path-based approach.” IEEE/ACM Transactions on Networking, 2014 https://ieeexplore.ieee.org/document/6962907
- cosasi.source_inference.single_source.short_fat_tree.weighted_boundary_node_degree(I, G, v, infection_rate=0.01, return_boundary=False)#
Computes the weighted boundary node degree (WBND) with respect to node v and the set of infected nodes I.
- 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.
infection_rate (float (optional)) – Inter-node infection efficiency from the original contagion process must be in [0, 1]
return_boundary (bool) – if True, you get both the weighted boundary node degree and the involved boundary nodes if False, you only get the weighted boundary node degree
Notes
This implementation is based on the WBND Algorithm, described in Algorithm 2.2 on p. 10 of [1].
References
- 1
L. Ying and K. Zhu, “Diffusion Source Localization in Large Networks” Synthesis Lectures on Communication Networks, 2018