Exact Computation of Inﬂuence Spreadby Binary Decision Diagrams

Takanori Maehara1) , Hirofumi Suzuki2) , Masakazu Ishihata2)
1) Riken Center for Advanced Intelligence Project2) Hokkaido University

August 4, 2017 @ ERATO 感謝祭

Introduction

Viral Marketing [Richardson–Domingos’02]
Viral Marketing
Marketing strategy that uses social networks to promote a
product, i.e.,
Giving products for some individuals (seeds) to propagate
information over the social network by word-of-mouth effectObjective
Estimate (and Maximize) the size of inﬂuence spread

1/35

Mathematical Model (Independent Cascade Model)A social network is modeled as a directed graph G = (V, E; p)(V: users, E: communications, p(e): activation probability)
Independent Cascade Model [Goldenberg+’01]
Information propagates from S ⊆ V (seeds):
1. At the ﬁrst step, the seeds s ∈ S become active
2. When u ∈ V becomes active, its neighbor v ∈ N(u)becomes active with probability p(u, v)
Inﬂuence spread σ(S) = expected number of activated users u⇒⇒2/35

Independent Cascade Model (Coin-Flipping ver.)In the IC model, each edge is examined once. Therefore it isequivalent to the following “pre coin-ﬂipping” model:
Independent Cascade Model (Coin-Flipping)σ(S) is the expected number of reachable vertices from Sin a random graph where e ∈ E appears with probability p(e)3/35

Inﬂuence Maximization Problem [Kempe+’03]
maximize σ(S) subject to |S| ≤ k• (Good News) σ(S) is a monotone submodular function⇒ The greedy algorithm attains 1 − 1/e approximation
by polynomial number of σ(·) evaluations• (Bad News) Evaluation of σ(·) is #P-HardExisting Work: Monte-Carlo simulation (e.g., [Borgs+’14])• Simulate the model Ω(1/ϵ2 ) times to obtain (1 ± ϵ)approximation of σ(S)• Suitable for rough estimation of σ(S) in large networks
4/35

This Study: Exact Computation of Inﬂuence Spread
Our Goal
Compute σ(S) exactly on small networks (e.g., m ≈ 100)
(Naive method cannot be used because of 2100 conﬁgurations)
Why exact computation?
• Precise analysis on small networks is important because
social networks consist from many small communities• Exact method can be used to evaluate the practicalaccuracy of Monte-Carlo simulations• Practical algorithm for #P-Hard problem is itself
interesting topic in Computer Science

5/35

Our Contributions
Our Contributions• We proposed the ﬁrst (non-trivial) algorithm forcomputing σ(S) exactly• It runs on m ≈ 100 networks in a reasonable time
• It can be used to solve another inﬂuence-spread related
problems (e.g., sampling, conditional expectation, ...)
Our Approach• Construct the binary decision diagrams (BDDs) for S-t
connected subgraphs• Perform dynamic programming to compute the inﬂuencespread
6/35

Proposed Algorithm (Outline)Reformulation of Inﬂuence Spread
Let us deﬁne∏∏• p(F) =p(e)(1 − p(e′ ))e∈Fe′ ̸∈F• R(S, t) := {F ⊆ E : G[F] has a S-t path}
Then the inﬂuence spread is given by∑σ(S) =σ(S, t)t∈V

whereσ(S, t) =∑p(F) =: p(R(S, t))

F∈R(S,t)

We compute σ(S) by using the above formulas... An efﬁcient algorithm to enumerate R(S, t) is required
7/35

Binary Decision Diagram (BDD)
We maintain R(S, t) by a binary decision diagram (BDD)
BDDA compact representation of a Boolean function- A DAG with single root and two terminals (0 and 1)- Each node has two children (0-child and 1-child)- Each node is associated with a variable e ∈ E
A path from the root to 1-child = a term of the function(descend 0-arc/1-arc ⇐⇒ exclude/include e)
A Boolean function represents a set family as
R(S, t) = {F ∈ 2E : r(F) = True}
8/35

Example

aasbcbtc
1

Left: Social Network Right Associated BDD(dotted/solid = 0-/1-arc, 0-terminal is omitted)
R(s, t) = {{c}, {a, b}, {a, c}, {b, c}, {a, b, c}},Boolean function = c + ab + ac + bc + abc = a(b + b̄c) + āc
9/35

Inﬂuence Computation via BDD
Once the BDD of R(S, t) is obtained, σ(S, t) is efﬁciently
computed by the bottom-up dynamic programming:
B(0) = 0, B(1) = 1, B(α) = (1 − p(e))B(α0 ) + p(e)B(α1 )aasbcbtc
1B(1) = 1, B(c) = p, B(b) = p + (1 − p)p,B(a) = p(p + (1 − p)p) + (1 − p)p = p + p2 − p3
10/35

Construction of BDD: Two stage method
Base Case: BDD of R(s, t) (s, t ∈ V)
Constructed by new frontier-based search procedure
General Case: BDD of R(S, t) (S ⊆ V, t ∈ V)
Constructed by the union of base-case BDDs:∪R(S, t) =R(s, t)s∈S

If the set families are represented by BDDs,
these union/intersection/... are efﬁciently obtained
Note: The 1st step in the greedy algorithm computes all R(s, t)
Therefore this method is always faster than the naive method
11/35

Frontier-Based Search— Main Procedure —Exhaustive enumeration then node merging
1: N0 = ∅2: for k = 1, 2, . . . , m do

Generate Nk from Nk−1 by including/excluding ek
4: end for
3:asbct

N1 = {{a}, ∅}N2 = {{a, b}, {a}, {b}, ∅}N3 = {{a, b, c}, {a, b}, {a, c}, {a}, {b, c}, {b}, {c}, ∅}...
12/35

Exhaustive enumeration then node merging
aaabbbcbcaccabbbccccc
11
13/35

Issue in exhaustive enumeration

IssueIt enumerates 2m nodes (too expensive)
We do not want to enumerate the nodes that• ... must reach to the terminals (1 or 0)• ... are “equivalent” to some other node
Frontier-Based search solves these issues!

14/35

Frontier-Based Search
Exhaustive enumeration with node sharing
1: N0 = ∅2: for k = 1, 2, . . . , m do

Generate Nk from Nk−1 by including/excluding ek
4:
Terminality check5:
Merge the equivalent nodes if possible
6: end for3:

Each node α ∈ Nk represents a family of equivalent sets R(α)• F, F′ ⊆ {e1 , . . . , ek } are equivalent iff ∀H ⊆ {ek+1 , . . . , em },reachability of G[F ∪ H] and G[F′ ∪ H] are the same
• α, α′ are equivalent iff for all elements represented bythese nodes are equivalent
15/35

Conﬁguration (aka. Mate Array)
A conﬁguration ϕ is used to check the equivalence:ϕ(α) = ϕ(α′ ) ⇒ α ≡ α′
Our conﬁguration for s-t connected subgraphs
Let W ⊆ V be the frontier vertices, which is the set of vertices
incident to both processed and unprocessed edges
Then we deﬁneϕ(α) = reachability matrix from (W ∪ {s}) to (W ∪ {t})on G[F] for some F ∈ R(α)• ϕ(α) = ϕ(α′ ) then the feature reachabilities are the same.
This also proves the well-deﬁnedness• The size is O(|W|2 ). Therefore the number nodes having
2
distinct conﬁgurations is 2O(|W| )16/35

Terminality Check• The included edges contains s-t path ⇒ Merge α to 1... Efﬁciently checked by the conﬁguration: O(1)• The excluded edges forms s-t cut ⇒ Merge α to 0... Checked by the BFS: O(m2 ) preproc. + O(|W|2 ) time
“Performing BFS in the frontier-based search” is expensive,
but necessarily to deal with larger networks

17/35

Frontier-Based Search— Additional Techniques —Pruning Redundant Edges

We remove all edges that do not contribute s-t connectivity• Checking existence of s-t path containing e ∈ E is NP-hard(equivalent with the two commodity ﬂow)
• However, since the network is small, we can solve thisproblem by the enumeration by frontier-based search!
(Knuth’s SimPath algorithm)“Using frontier-based search as a preprocessing for thefrontier-based search” seems a technically interesting idea

18/35

Edge Ordering

The complexity of the frontier-based search depends on theedge ordering (∵ W ⇒ fast enumeration)
The same ordering should be used for all R(s, t) because we
perform set family manipulations⇒ We used path decomposition + beam-search heuristics
proposed by [Inoue and Minato’16]

19/35

Node Sharing among Different BDDs

The algorithm construct O(n2 ) BDDs R(s, t) for all s, t ∈ V,
which may have many similar sub-structures⇒ Share them to reduce the total number of nodes [Minato’90](reduced about factor 2 in practice)

20/35

Other Inﬂuence-Spread RelatedProblems

Other Inﬂuence-Spread Related Problems

Our algorithm constructs the BDDs for inﬂuence spread⇒ many other problems can be solved using the BDDs
1. Random Sampling without Rejection
2. Conditional Inﬂuence Spread
3. Dynamic Probability Update
4. Optimization (Computing ∂σ(S)/∂p(e))
Details are omitted (perhaps well-known in BDD community)
These are important in viral marketing

21/35

Experiments

Experimental Setting• C++ (g++5.4.0 with -O3 option)• BDD implementation: TdZdd libraryhttps://github.com/kunisura/TdZdd• 64-bit Ubuntu 16.04 LTS with an Intel Core i7-3930K 3.2 GHz
CPU and 64 GB RAM• Real Networks: Koblenz Network Collection
http://konect.uni-koblenz.de/

22/35

Basic Results on Typical Networks

Networkn m Time [ms] BDD Size Shared Size Cardinality
South-African-Companies 11 26
0.1
12.1472 2.2e+07
Southern-women-2 20 280.3
54.7
2,266 1.3e+08
Taro-exchange 22 78
4.1 1,119.2
277,756 1.6e+23
Zachary-karate-club 34 156
24.9 7,321.8 4,988,148 6.4e+46
Contiguous-USA 49 214
117.9 30,599.8 41,261,047 1.6e+64
American-Revolution 141 320
2.2
120.0 1,530,677 5.7e+95
Southern-women-1 50 178————
Club-membership 65 190————
Corporate-Leadership 64 198————• Fast in solvable instances• Very slow in unsolvable instances

23/35

Experiments on Grid/Random Network• Construct the following networks
1. n × 5 grid network
2. random network with the same n, m• Compute the exact inﬂuence spread from the corner

24/35

Results on Grid/Random Network (1/3)(a) Inﬂuence Probability

Inﬂuence probability

100
10−510−1010−15
GridRandom

10−20020406080
Number of vertices n10025/35

Results on Grid/Random Network (2/3)(b) BDD Size

BDD Size

107105103
Grid
Random101
020406080
Number of vertices n10026/35

Results on Grid/Random Network (3/3)(c) Time [s]102Time101100
10−110−2
Grid
Random10−310−4020406080
Number of vertices n

100
27/35

Example 3: Greedy Algorithm• We used the Contiguous USA Network• We performed the greedy algorithm to seek the mostinﬂuencial seeds of size k = 10.

28/35

Results on Greedy Algorithm (1/3)(a) Inﬂuence spread

Inﬂuence spread

15

105
ContUSA
Zachary
02468
Number of steps

1029/35

Results on Greedy Algorithm (2/3)(b) Shared Size

Shared Size

108107

106
ContUSA
Zachary105

2468
Number of steps

1030/35

Results on Greedy Algorithm (3/3)(c) Time [s]Time [s]

102

101

100
ContUSA
Zachary
10−12468Number of steps

1031/35

Experiment 4: Exact vs Monte-Carlo• We used the Contiguous USA Network• Fix a set and compute inﬂuence spread by exact method
and Monte-Carlo method• Compare the results for various number of MC samples

32/35

Error of the estimated inﬂuence

Results for Exact vs Monte-Carlo·10−3
1 · 100
0 · 100−1 · 100−2 · 100010.2 0.4 0.6 0.8
Number of samples ·107

• Fluctuates in 10−3 , which is consistent with the theory
33/35

Related Work

Related Work• This is the ﬁrst attempt for exact inﬂuence spreadcomputation• No existing method for enumerating s-t connected
subgraphs efﬁciently(An algorithms for undirected case is known in theliterature of “Network Reliability” (e.g., [Valiant’79]),
but it cannot be extend to our directed case)

34/35

Conclusion

Conclusion / Future WorkConclusion
1. We proposed the ﬁrst algorithm to compute the inﬂuencespread exactly
2. It constructs the BDDs of S-u connected subgraphs by new
frontier-based search and set family manipulations
3. Real networks with m ≈ 100 were solved
Future Work
1. We want to solve m ≈ 200 networks
2. Exact inﬂuence maximization
NP-hard problem with #P-hard function evaluation
This slide is available at:
http://www.prefield.com/slide/maehara2017exact_slide.pdf

35/35

Christian Borgs, Michael Brautbar, Jennifer Chayes, andBrendan Lucier.
Maximizing social inﬂuence in nearly optimal time.
In SODA, pages 946–957, 2014.
Jacob Goldenberg, Barak Libai, and Eitan Muller.
Talk of the network: A complex systems look at theunderlying process of word-of-mouth.
Marketing Letters, 12(3):211–223, 2001.
Yuma Inoue and Shinichi Minato.
Acceleration of ZDD construction for subgraphenumeration via path-width optimization.
TCS-TR-A-16-80. Hokkaido University, 2016.
David Kempe, Jon Kleinberg, and Éva Tardos.

35/35

Maximizing the spread of inﬂuence through a socialnetwork.
In KDD, pages 137–146, 2003.
Shinichi Minato, Nagisa Ishiura, and Shuzo Yajima.
Shared binary decision diagram with attributed edges for
efﬁcient boolean function manipulation.
In DAC, pages 52–57, 1990.
Matthew Richardson and Pedro Domingos.
Mining knowledge-sharing sites for viral marketing.
In KDD, pages 61–70, 2002.
Leslie G Valiant.
The complexity of enumeration and reliability problems.
SIAM Journal on Computing, 8(3):410–421, 1979.

35/35