This repository has been archived by the owner on Jul 7, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
influence.py
52 lines (45 loc) · 1.98 KB
/
influence.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
"""
Module defining influence functions not belonging elsewhere.
This module defines functions relating to influence which do not
fit either the independence cascade or the correlation robust models.
"""
# Python Standard library
from collections import deque
from typing import Hashable
# packages
from igraph import Graph
def det_inf_func(input_seed_set: list[Hashable], input_graph: Graph) -> set[Hashable]:
"""
Calculate influence of seed set on input graph.
Output and inputs are deterministic.
"""
total_num_nodes: int = input_graph.vcount()
influenced: set[Hashable] = set()
to_be_processed = deque(input_seed_set)
already_processed: set[Hashable] = set()
while to_be_processed: # if this set is non-empty, then
zeroth_index_node = to_be_processed.popleft()
influenced.add(zeroth_index_node)
already_processed.add(zeroth_index_node)
# get immediate out-neighbours of specified node
# they will be set to be influenced
for succ_of_proc_node in input_graph.successors(zeroth_index_node):
influenced.add(succ_of_proc_node)
if len(influenced) == total_num_nodes:
return set(v.index for v in input_graph.vs())
if succ_of_proc_node not in already_processed:
to_be_processed.append(succ_of_proc_node)
# position of thing to be processed
return influenced
def calc_comonotone_inf(input_graph: Graph, input_seed_set: list[Hashable]) -> float:
"""Calculate exact comonotone expected influence."""
sorted_edges = sorted(input_graph.es, key=lambda x: x["p"])
cur_graph = input_graph.copy()
cur_prob: float = 0
cur_est: float = 0
for edge in sorted_edges:
cur_est += (edge["p"] - cur_prob) * len(det_inf_func(input_seed_set, cur_graph))
cur_graph.delete_edges([(edge.source, edge.target)])
cur_prob = edge["p"]
cur_est += (1 - cur_prob) * len(det_inf_func(input_seed_set, cur_graph))
return cur_est