This paper develops deterministic upper and lower bounds on the influence measure in a network, more precisely, the expected number of nodes that a seed set can influence in the independent cascade model. In particular, our bounds exploit r-nonbacktracking walks and Fortuin-Kasteleyn-Ginibre (FKG) type inequalities, and are computed by message passing algorithms. Further, we provide parameterized versions of the bounds that control the trade-off between efficiency and accuracy. Finally, the tightness of the bounds is illustrated on various network models.

This paper develops upper and lower bounds on the influence measure in a network, more precisely, the expected number of nodes that a seed set can influence in the independent cascade model. In particular, our bounds exploit nonbacktracking walks, Fortuin-Kasteleyn-Ginibre type inequalities, and are computed by message passing algorithms. Nonbacktracking walks have recently allowed for headways in community detection, and this paper shows that their use can also impact the influence computation. Further, we provide parameterized versions of the bounds that control the trade-off between the efficiency and the accuracy. Finally, the tightness of the bounds is illustrated with simulations on various network models.

In this paper, we investigate the impact of a single edge on the capacity region of a network of error-free, point-to-point links. A family of networks and edges is said to exhibit the “edge removal property” if for any network and edge in the family, removing a δ-capacity edge changes the capacity region by at most δ in each dimension. We derive a sufficient condition on network coding functions to guarantee that the edge removal property holds when the network is operated using functions satisfying the condition. Also, we extend the family of network capacity bounds for which it is known that removing a single edge of capacity δ changes the capacity bound by at most f(δ) in each dimension. Specifically, we show that removing a single δ-capacity edge changes the Generalized Network Sharing outer bound by at most δ in each dimension and the Linear Programming outer bound by at most a constant times δ in each dimension.