現代の広告活動では、SNS上で影響力の大きいアカウント（いわゆるインフルエンサー）を活用することが一般的に行われています。 例えば、新製品を販売する際にはインフルエンサーに商品サンプルを配布し、その商品サンプルについて投稿してもらうという広告活動です。
インフルエンサーの影響力の大きさは、Facebookなら友達(friend)の数で測ります。 しかし、複数のインフルエンサーに広告投稿を依頼する場合、 インフルエンサー間で友達(friend)の集合の重なりが大きいと、 同じフォロワーに繰り返し広告投稿を見せることになり、あまり効果的ではありません。 そのため、なるべく友達(friend)の集合の重なりの小さいインフルエンサーの組合せを探す必要があります。
このペーパーでは、 依頼する人数を固定してソーシャルグラフのなるべく広い範囲に広告投稿を見せるために、 どのインフルエンサーに広告投稿を依頼すればよいかをSBMにより分析する一連の手順を説明します。 まず、Stanford大学SNAPグループの公開しているデータセット[1]から Facebookアカウントの友達(friend)関係のソーシャルグラフを抽出します。 次に、ソーシャルグラフから各アカウントの影響範囲と影響力を抽出し、 影響力の大きいアカウントをインフルエンサーとみなして広告投稿を依頼するか検討することにします。 最後に、SBMへの入力となるQUBO行列を構築して分析し、 どのインフルエンサーに広告投稿を依頼すればよいかを決定します。
import networkx as nx
import numpy as np
import requests
import os
import scipy.sparse
from scipy.sparse import csr_matrix, lil_matrix, coo_matrix
from scipy.sparse.base import spmatrix
import h5py
from gmpy2 import mpz, popcount
def writeHDF5(M, quboFileName):
'''
SBMに入力する用のHDF5ファイルを生成する
'''
# QUBOを三角行列にしてから疎行列CSR形式に変換する
MM = csr_matrix(M)
# 圧縮形式はgzipのoption=1（圧縮率と速度のため）
comp = 'gzip'
opts = 1
# 以下のレイアウトで保存すること
with h5py.File(quboFileName, mode='w') as hf:
group = hf.create_group('/qubo')
# dataの型はnp.float32
temp = group.create_dataset(name='data',
shape=MM.data.shape,
dtype=np.float32,
compression=comp,
compression_opts=opts)
temp[:] = MM.data[:]
temp.attrs['format'] = 'csr'
temp.attrs['cols'] = M.shape[0]
temp.attrs['rows'] = M.shape[1]
# indicesの型はnp.uint32
temp = group.create_dataset(name='indices',
shape=MM.indices.shape,
dtype=np.uint32,
compression=comp,
compression_opts=opts)
temp[:] = MM.indices[:]
# indptrの型はnp.uint32
temp = group.create_dataset(name='indptr',
shape=MM.indptr.shape,
dtype=np.uint32,
compression=comp,
compression_opts=opts)
temp[:] = MM.indptr[:]
hf.close()
Stanford大学SNAPグループの公開しているデータセット[1]から Facebookアカウントの友達(friend)関係のソーシャルグラフを抽出します。 友達(friend)関係は双方向的なので、ソーシャルグラフは無向グラフになります。
本データセットは複数のファイルで構成されており、 ファイル「facebook_combined.txt」に友達(friend)関係が記載されています。 ファイル「facebook_combined.txt」の書式は、 一行ごとに匿名化されたID二つが記載されているというものです。
G = nx.Graph()
with open("facebook_combined.txt") as fin:
for line in fin.readlines():
i, j = (v for v in line.split())
G.add_edge(i, j)
ソーシャルグラフから各アカウントの影響範囲と影響力を抽出します。
N = len(G)
Nodes = sorted(G, key=int)
IdToIdx = {
c:n
for (n,c) in enumerate(Nodes)
}
Cover = []
Influence = []
for c in Nodes:
v = mpz()
v = v.bit_set(IdToIdx[c])
for d in G[c]:
v = v.bit_set(IdToIdx[d])
Cover.append(v)
Influence.append(len(G[c]))
影響力の大きいアカウントをインフルエンサーとみなして広告投稿を依頼するか検討することにします。 インフルエンサーの基準は $$ Influence[n] \ge Threshold $$ とします。
Threshold = 50
# インフルエンサーのそれぞれに広告投稿を依頼するかどうかにスピン変数を割り当てます。
Spins = [n for n in range(N) if Threshold <= Influence[n]]
M = len(Spins)
Budget = 5
なるべく少ない人数への依頼でソーシャルグラフ全域に広告投稿を見せるという問題であり、 アンテナ配置問題の一種として扱うことができます。 集合被覆問題は多項式時間アルゴリズムが存在しておらず、 通常の逐次計算よりもSBMを使った方が高速に解ける可能性があります。
アンテナ配置問題を厳密に解くには、混合整数線形計画問題としての定式化があります。
しかし、混合整数線形計画問題としての定式化は制約項を扱うための補助変数が多く、短い処理時間で良い解を得ることができません。 このペーパーでは、 制約項を近似して扱うことで短い処理時間で良い解を得られるようにします。
SBMへの入力となるQUBO行列を構築します。
インフルエンサーに広告投稿を依頼するとき、 そのインフルエンサーの影響力を一次項とします。 同様に、インフルエンサー同士の影響範囲の重なる分を二次項として加えます。
近似精度を高めるためには、 SBMソルバーのPUBO形式を用いて、 インフルエンサー三人の影響範囲の重なる分を三次項、四人の影響力の重なる分を四次項、 ……といったように高次項を加えることが効果的です。 今回はそこまでしなくても十分な近似精度を得られたため、三次以上の高次項を加えていません。
具体的にはQUBO行列の係数を以下のように定式化します。
目的項
制約項
最後にHDF5形式のファイルを出力したのち、メモリに読み込みます。
%%time
print("SBMの準備")
Alpha = np.max(Influence)
Q1 = np.zeros((M, M))
for m1 in range(M):
# そのインフルエンサーの影響力を一次項とします。
Q1[m1, m1] += -Influence[Spins[m1]]
for m2 in range(m1):
# インフルエンサー同士の影響範囲の重なる分を二次項として加えます。
Q1[m1, m2] += popcount(Cover[Spins[m1]] & Cover[Spins[m2]])
Q2 = np.zeros((M, M))
for m1 in range(M):
Q2[m1, m1] += -2 * Budget + 1
for m2 in range(m1):
Q2[m1, m2] += +2
# HDF5形式のファイルを出力したのち、メモリに読み込みます。
filename = "temp.h5"
if os.path.exists(filename):
os.remove(filename)
writeHDF5(Q1 + Alpha * Q2, filename)
with open(filename, "rb") as f:
data = f.read()
SBMの準備 CPU times: total: 859 ms Wall time: 858 ms
SBMにより分析し、 どのインフルエンサーに広告投稿を依頼すればよいかを決定します。
%%time
print("SBMの求解")
headers = {'content-type': 'application/octet-stream'}
params = {
"loops": 0,
"timeout": 0.05,
}
ret = requests.post(
"http://aa.bb.cc.dd:8000/solver/ising",
#"http://localhost:51842/solver/qubo",
headers=headers,
data=data,
params=params)
SBMの求解 CPU times: total: 0 ns Wall time: 1.01 s
X = ret.json()["result"]
done = mpz()
for m in np.where(X)[0]:
done |= Cover[Spins[m]]
print(f"SBMの結果")
print(f"\t依頼数={sum(X)}")
print(f"\t合計の影響力={popcount(done)}")
print(f"\t依頼先のID={[Spins[m] for m in np.where(X)[0]]}")
SBMの結果 依頼数=5 合計の影響力=3463 依頼先のID=[0, 107, 1684, 1912, 3437]
同じ問題を線形計画法ソルバーでも解き、SBMで解いた場合と処理時間を比較します。 結果は以下のようになり、SBMの方が高速となりました。
| SBM v1.6 | Python MIP 1.13.0 / CBC | |
|---|---|---|
| 最適解までの処理時間 | 1.87 秒 | 2.63 秒 |
| SBM v1.6 (client) | SBM v1.6 (server) | Python MIP 1.13.0 / CBC | |
|---|---|---|---|
| CPU | Core-i7 8700 (3.20 GHz, 6 Core) | AWS EC2 p3.2xlarge (vCPU 8) | Core-i7 8700 (3.20 GHz, 6 Core) |
| GPU | on board | AWS EC2 p3.2xlarge (vCPU 8) | on board |
| RAM | 16 GB | 61 GB + 16 GB | 16 GB |
比較のため、線形計画法ソルバーで同じ問題を解きます。 アンテナ配置問題を混合整数線形計画問題として定式化したものをそのまま解きます。
%%time
print("線形計画法の準備")
import mip
model = mip.Model()
x = model.add_var_tensor((M, ), 'x', var_type=mip.BINARY)
y = model.add_var_tensor((N, ), 'y', var_type=mip.BINARY)
model.objective = mip.maximize(mip.xsum(y))
for n in range(N):
model += (y[n] <= sum(x[m] for m in range(M) if Cover[n].bit_test(Spins[m])))
model += (mip.xsum(x) <= Budget)
線形計画法の準備 CPU times: total: 1.02 s Wall time: 1.04 s
%%time
print("線形計画法の求解")
model.optimize()
線形計画法の求解 CPU times: total: 1.53 s Wall time: 1.59 s
<OptimizationStatus.OPTIMAL: 0>
done = mpz()
for m in range(M):
if x[m].x >= 1:
done |= Cover[Spins[m]]
print(f"線形計画法の結果")
print(f"\t依頼数={sum([int(x[m].x) for m in range(M)])}")
print(f"\t合計の影響力={popcount(done)}")
print(f"\t依頼先のID={[Spins[m] for m in range(M) if x[m].x == 1]}")
線形計画法の結果 依頼数=5 合計の影響力=3463 依頼先のID=[0, 107, 1684, 1912, 3437]
