# Bridge width and threshold heterogeneity (extending volume 13, Chapter 5).
# Community A has fully adopted a costly behaviour. Community B is a ring of
# 200 people, each tied to 2 neighbours on each side (4 contacts). w bridge
# ties run from A to B. A person in B adopts once at least THETA of his or her
# contacts have adopted (Centola & Macy 2007). Bridges are either
#   "wide": the w ties land two per person on adjacent people in B, or
#   "scattered": each tie lands on a person in B chosen at random.
# Optionally a share f of people in B has threshold 1 instead of 2.
import random
rng = random.Random(6)
NB, REPS = 200, 2000

def spread_in_b(bridge_count, theta):
    # bridge_count[i] = number of A-adopters tied to person i of B
    adopted = [False] * NB
    changed = True
    while changed:
        changed = False
        for i in range(NB):
            if adopted[i]:
                continue
            ring = sum(adopted[(i + d) % NB] for d in (-2, -1, 1, 2))
            if ring + bridge_count[i] >= theta[i]:
                adopted[i] = changed = True
    return sum(adopted) / NB

def trial(w, kind, f=0.0):
    count = [0] * NB
    if kind == "wide":
        start = rng.randrange(NB)
        for t in range(w):
            count[(start + t // 2) % NB] += 1
    else:
        for _ in range(w):
            count[rng.randrange(NB)] += 1
    theta = [1 if rng.random() < f else 2 for _ in range(NB)]
    return spread_in_b(count, theta)

def p_cross(w, kind, f=0.0, reps=REPS):
    return sum(trial(w, kind, f) > 0.9 for _ in range(reps)) / reps

print("threshold 2 for everyone in B: chance that B is taken over (> 90 % adopt)")
print(" bridge width w   wide bridge   scattered ties")
for w in (1, 2, 3, 4, 8, 16, 32):
    wide, scat = p_cross(w, "wide", reps=50), p_cross(w, "scattered")
    print(f"   {w:5d}         {wide:8.2f}     {scat:10.3f}")
print("scattered ties, w = 4, with a share f of B at threshold 1:")
for f in (0.0, 0.02, 0.05, 0.1, 0.2):
    print(f"   f = {f:4.2f}: chance of take-over {p_cross(4, 'scattered', f):.3f}")
# threshold 2 for everyone in B: chance that B is taken over (> 90 % adopt)
#  bridge width w   wide bridge   scattered ties
#        1             0.00          0.000
#        2             0.00          0.000
#        3             1.00          0.000
#        4             1.00          0.002
#        8             1.00          0.018
#       16             1.00          0.136
#       32             1.00          0.698
# scattered ties, w = 4, with a share f of B at threshold 1:
#    f = 0.00: chance of take-over 0.002
#    f = 0.02: chance of take-over 0.011
#    f = 0.05: chance of take-over 0.043
#    f = 0.10: chance of take-over 0.152
#    f = 0.20: chance of take-over 0.412

# Noisy threshold contagion (after Eckles, Mossel, Rahimian & Sen 2024).
# Ring of N people; everyone is tied to the neighbours 1 step away (the
# "cycle") and 2 steps away (the "short ties"). A share r of the short ties is
# rewired to random people (long ties). Threshold 2: adopt once 2 contacts have
# adopted. Noise: someone with exactly 1 adopting contact still adopts with
# probability q in each round. Start: two adjacent adopters. We count rounds
# until 90 % have adopted (cap 3000). Parameters are illustrative.
import random
N, CAP, RUNS = 400, 3000, 11

def network(r, rng):
    nb = [set() for _ in range(N)]
    for i in range(N):
        for d in (1, 2):
            j = (i + d) % N
            if d == 2 and rng.random() < r:
                j = rng.randrange(N)
                while j == i or j in nb[i]:
                    j = rng.randrange(N)
            nb[i].add(j); nb[j].add(i)
    return nb

def rounds_to_90(r, q, rng, theta=2):
    nb = network(r, rng)
    adopted = {0, 1}
    for t in range(1, CAP + 1):
        new = []
        for i in {j for a in adopted for j in nb[a]} - adopted:
            k = len(nb[i] & adopted)
            if k >= theta or (k >= 1 and rng.random() < q):
                new.append(i)
        adopted.update(new)
        if len(adopted) >= 0.9 * N:
            return t
    return None

def median_rounds(r, q, theta=2, seed=7):
    rng = random.Random(seed)
    res = sorted((rounds_to_90(r, q, rng, theta) or CAP + 1) for _ in range(RUNS))
    m = res[RUNS // 2]
    return "never" if m > CAP else str(m)

if __name__ == "__main__":
    print(f"median rounds to 90 % adoption ({RUNS} runs, N = {N};"
          f" 'never' = not within {CAP})")
    print(" share of short ties rewired r:      0      0.05     0.2     1.0")
    print(" simple contagion (threshold 1) " + "".join(
          f"{median_rounds(r, 0, theta=1):>8s}" for r in (0, 0.05, 0.2, 1.0)))
    for q in (0, 0.005, 0.02, 0.1):
        print(f" threshold 2, noise q = {q:<6}   " + "".join(
              f"{median_rounds(r, q):>8s}" for r in (0, 0.05, 0.2, 1.0)))
# median rounds to 90 % adoption (11 runs, N = 400; 'never' = not within 3000)
#  share of short ties rewired r:      0      0.05     0.2     1.0
#  simple contagion (threshold 1)       90      20       9       6
#  threshold 2, noise q = 0             179   never   never   never
#  threshold 2, noise q = 0.005         178     282     327     286
#  threshold 2, noise q = 0.02          175     123     101      82
#  threshold 2, noise q = 0.1           163      58      34      23