Path Graph Submodularity

path_graph.py

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt


# Bidrectional path graph: nodes labelled 0 to 7.
# 0 <-> 1 <-> .... 6 <-> 7
dig = nx.path_graph(8).to_directed()
weights = {}

# Assign a series of decreasing probabilities to each edge starting from (0, 1)
# upto (6, 7) and then from (7, 6) to (1, 0).
prob_ctr = 1
for index, e in enumerate(dig.edges):
    if index % 2 == 1:
        continue
    weights[e] = prob_ctr
    prob_ctr = prob_ctr - 1/14

for index, e in enumerate(sorted(dig.edges, reverse=True)):
    if index % 2 == 1:
        continue
    weights[e] = prob_ctr
    prob_ctr = prob_ctr - 1/14

nx.set_edge_attributes(dig, values=weights, name='weight')

S = {0} # left end
T = {0, 7} # left end + right end
v = 3 # middle
# Gamma dictionaries contain the probabilities of activation of each node given
# that seed set. In case the node is *not* a v-node (i.e. competing influence from
# both directions, for e.g. in case of T all nodes in between are v-nodes),
# then a node's gamma score is just the path probability from the seed node.
# In case it is a v-node, we use the 1 - (1 - )(1 - ) formula for "atleast one"
# semantics.
S_gamma = {0: 1}
S_v_gamma = {0: 1, 3: 1}
T_gamma = {0: 1, 7: 1}
T_v_gamma = {0: 1, 3: 1, 7: 1}

# S = {0} seed set case.
# gamma values will just be path probabilities, straightforward.
prev_node = 0
prob_acc = 1
for node in dig.nodes:
    if node == 0:
        continue
    prob_acc *= weights[(prev_node, node)]
    S_gamma[node] = prob_acc
    prev_node = node

# T = {0, 7} seed set case.
# Here all nodes are v-nodes with competition from S and T\S on either side.
# We start iterating from the T-end and for each node derive the probability
# as atleast one of S or T influencing it.
prev_node = 7
prob_acc = 1
for node in range(6, 0, -1):
    prob_acc *= weights[(prev_node, node)]
    T_gamma[node] = 1 - (1 - prob_acc)*(1 - S_gamma[node])
    prev_node = node


# S U v case.
# On the left of v, all nodes are v-nodes as competing influence between S and
# v ("v" has nothing to do with a "v-node", just terminology).
prev_node = 3
prob_acc = 1
for node in range(2, 0, -1):
    prob_acc *= weights[(prev_node, node)]
    S_v_gamma[node] = 1 - (1 - prob_acc)*(1 - S_gamma[node])
    prev_node = node

# On the right of v, it's just path probabilities starting from v.
prev_node = 3
prob_acc = 1
for node in range(4, 8):
    prob_acc *= weights[(prev_node, node)]
    S_v_gamma[node] = prob_acc
    prev_node = node


# T U v case.
# On the left of v, the competition is between S and v. So just set the scores
# from S_gamma.
for node in range(1, 3):
    T_v_gamma[node] = S_v_gamma[node]

# On the right of v, the competition is between T and v. Calculate.
prev_node = 7
prob_acc = 1
for node in range(6, 3, -1):
    prob_acc *= weights[(prev_node, node)]
    T_v_gamma[node] = 1 - (1 - prob_acc)*(1 - S_v_gamma[node])
    prev_node = node

# Calculate F for each seed set, top-3.
F_S = sum(sorted(S_gamma.values(), reverse=True)[:3])
F_S_v = sum(sorted(S_v_gamma.values(), reverse=True)[:3])
F_T = sum(sorted(T_gamma.values(), reverse=True)[:3])
F_T_v = sum(sorted(T_v_gamma.values(), reverse=True)[:3])

print("Top-3")
print(f"F(S): {F_S}, F(S U v): {F_S_v}, F(delta S): {F_S_v - F_S}")
print(f"F(T): {F_T}, F(T U v): {F_T_v}, F(delta T): {F_T_v - F_T}\n")

# Bottom-3.
F_S = sum(sorted(S_gamma.values())[:3])
F_S_v = sum(sorted(S_v_gamma.values())[:3])
F_T = sum(sorted(T_gamma.values())[:3])
F_T_v = sum(sorted(T_v_gamma.values())[:3])

print("Bottom-3")
print(f"F(S): {F_S}, F(S U v): {F_S_v}, F(delta S): {F_S_v - F_S}")
print(f"F(T): {F_T}, F(T U v): {F_T_v}, F(delta T): {F_T_v - F_T}\n")

# Top-7
F_S = sum(sorted(S_gamma.values(), reverse=True)[:7])
F_S_v = sum(sorted(S_v_gamma.values(), reverse=True)[:7])
F_T = sum(sorted(T_gamma.values(), reverse=True)[:7])
F_T_v = sum(sorted(T_v_gamma.values(), reverse=True)[:7])

print("Top-7")
print(f"F(S): {F_S}, F(S U v): {F_S_v}, F(delta S): {F_S_v - F_S}")
print(f"F(T): {F_T}, F(T U v): {F_T_v}, F(delta T): {F_T_v - F_T}\n")

print(S_gamma)
print("\n")
print(S_v_gamma)
print("\n")
print(T_gamma)
print("\n")
print(T_v_gamma)