We study cascades in social networks with the independent cascade (IC) model and the Susceptible-Infected-recovered (SIR) model. The well-studied IC model fails to capture the feature of node recovery, and the SIR model is a variant of the IC model with the node recovery feature. In the SIR model, by computing the probability that a node successfully infects another before its recovery and viewing this probability as the corresponding IC parameter, an equivalence between the two models is established, except that the events of the infections along different out-going edges of a node become dependent in the SIR model, whereas these events are independent in the IC model. In this paper, we thoroughly compare the two models and examine the effect of this extra dependency in the SIR model. By a carefully designed coupling argument, we show that the seeds in the IC model have a stronger influence spread than their counterparts in the SIR model, and sometimes it can be significantly stronger. Specifically, we prove that, given the same network, the same seed sets, and the parameters of the two models being set based on the above-mentioned equivalence, the expected number of infected nodes at the end of the cascade for the IC model is weakly larger than that for the SIR model, and there are instances where this dominance is significant. We also study the influence maximization problem (the optimization problem of selecting a set of nodes as initial seeds in a social network to maximize their influence) with the SIR model. We show that the above-mentioned difference in the two models yields different seed-selection strategies, which motivates the design of influence maximization algorithms specifically for the SIR model. We design efficient approximation algorithms with theoretical guarantees by adapting the reverse-reachable-set-based algorithms, commonly used for the IC model, to the SIR model.

For an integer b ≥ 0, a b-matching in a graph G = (V, E ) is a set S ⊆ E such that each vertex v ∈ V is incident to at most b edges in S. We design a fully polynomial-time approximation scheme (FPTAS) for counting the number of b-matchings in graphs with bounded degrees. Our FPTAS also applies to a broader family of counting problems, namely Holant problems with log-concave signatures.

It is shown in this note that approximating the number of independent sets in a k-uniform linear hypergraph with maximum degree at most Δ is NP-hard if Δ≥5⋅2k−1+1. This confirms that for the relevant sampling and approximate counting problems, the regimes on the maximum degree where the state-of-the-art algorithms work are tight, up to some small factors. These algorithms include: the approximate sampler and randomised approximation scheme by Hermon, Sly and Zhang (RSA, 2019), the perfect sampler by Qiu, Wang and Zhang (ICALP, 2022), and the deterministic approximation scheme by Feng, Guo, Wang, Wang and Yin (FOCS, 2023).