2nd European Conference on Social Networks, June 14-17, 2016, Paris (http://eusn2016.sciencesconf.org/)

Contributed paper at Session 23: Modelling networks (June 15, 9h25 - 13h05)

SOCIAL INFLUENCE NETWORKS

By Moses Boudourides and Sergios Lenis

University of Patras, Greece

Graphs Assumptions & Notation

  • Let $G = (V, E)$ be a simple undirected graph with n vertices, i.e., $n = |V|$, so that, without any loss of generality,
\begin{equation} V = [n], \end{equation}\begin{equation} E = \{(i,j)\!: i \sim j, i, j \in V, i \neq j\}. \end{equation}
  • For any finite set $X$, $|X|$ denotes the number of elements of $X$.
  • For any positive integer $k$, $[k]$ denotes the set of integers from 1 to $k,$ i.e., $[k] = \{1, 2, \ldots, k\}$.
  • If vertices $i$ and $j$ are adjacent, we write $i \sim j$.
  • $\deg(i)$ denotes the degree of $i$.
  • $G$ is assumed to be connected (i.e., for any $i, \deg(i) \neq 0$).
  • $A = \{A_{ij}\}_{i, j \in [n]}$ denotes the adjacency matrix of $G$.
  • $N = \{N_{ij}\}_{i, j \in [n]}$ denotes the walk matrix (or the adjacent averaging operator) of $G$, which is defined as
\begin{equation} N = D^{-1} \, A, \end{equation}

where $D$ is the diagonal degree matrix with entries equal to the degree $\deg(i)$ of vertex $i$. Notice that

\begin{equation} N_{ij} = \left\{ \begin{array}{lr} \frac{1}{\deg(i)}, & {\mbox{ whenever }} i \sim j, \\ 0, & {\mbox{ otherwise, }} \end{array} \right. \end{equation}
  • Finally, $L = \{L_{ij}\}_{i, j \in [n]}$ denotes the (combinatorial) Laplacian matrix of $G$, which is defined as
\begin{eqnarray} L &=& D - A \\ \nonumber &=& D(I - N), \end{eqnarray}

where $I$ is the unit matrix, i.e., as \begin{equation} L_{ij} = \left{ \begin{array}{lr} \deg(i), & {\mbox{ whenever }} i = j, \ -1, & {\mbox{ whenever }} i \sim j, \ 0, & {\mbox{ otherwise. }} \end{array} \right. \end{equation}

The DeGroot-Friedkin-Johnsen Model of Social Influence

  • $G$ is a graph of persons, i.e., vertices $\equiv$ persons.
  • For each person $i \in V$ and time $t = 0, 1, 2, \ldots$ (in the discrete case considered here), $v^t(i) \in \mathbb{R}$ denotes $i$'s opinion at time $t$.
  • Person's $i$ opinion at time $t$ is updated at next instance $t + 1$ as follows:
\begin{equation} v^{t + 1}(i) = s_i \, N \, v^t(i) + (1 - s_i) \, v^0(i), \end{equation}
  • where $N \, v^t(i)$ is the average opinion of $i$'s neighbors
  • and $s_{i}$ is person's $i$ susceptibility coefficient, a scalar parameter in the interval $[0, 1]$. Moreover, $s = \{s_i\}_{i \in [n]} \in [0,1]^{n}$ denotes the vector of susceptibility coefficients of all persons (vertices) in $G$ and $S$ is the $n \times n$ diagonal matrix with its diagonal entries equal to the $s_i$'s.
  • If $s_i = 0$, then $i$'s opinion does not change ($v^{t + 1}(i) = v^0(i)$). Such a person is called stubborn or persistent in her opinion.
  • If $s_i = 1$, then $i$ adopts the average opinion of her neighbors $N \, v^t(i)$. Such a person is called malleable or fully compliant in adopting her neighbor's influence.
  • If $0 < s_i < 1$, then $i$'s opinion is inserted in-between $N \, v^t(i)$ and $v^0(i)$, where the exact inserted position is weighted by $s_i$.

A PDEs-Based Formulation

Persons with zero susceptibilities form the "boundary" of persons with positive susceptibilities.

  • Decomposition of the set $V$ of persons-vertices:
\begin{equation} V = \Omega \cup \delta \Omega, \end{equation}\begin{equation} \Omega = \{i \in V\!: s_i > 0\}, \end{equation}\begin{equation} \delta \Omega = \{i \in V\!: s_i = 0\}, \end{equation}
  • Assumptions: \begin{equation} \delta = |\delta \Omega| < n, \end{equation} \begin{equation} \forall j \in \delta \Omega, \exists i \in \Omega, i \sim j. \end{equation}

The (Evolutionary) Initial Boundary Value Problem (IBVP)

\begin{eqnarray} v^{t + 1} &=& S \, N \, v^t + (I - S) \, \phi, {\mbox{ in }} \Omega, t > 0 \\ v^t &=& 1, {\mbox{ on }} \delta \Omega, t > 0 \\ v^0 &=& \left\{ \begin{array}{lr} \phi, & {\mbox{ in }} \Omega, \\ 1, & {\mbox{ on }} \delta \Omega. \end{array} \right. \end{eqnarray}

To solve this problem one needs to first consider the problem for the rate of opinion change at the unit time step, i.e.,

\begin{equation} u^t = v^t - v^{t - 1}, \end{equation}

which can be easily transformed to the following linear parabolic IBVP with Dirichlet boundary conditions:

\begin{eqnarray} w^{t + 1} &=& S \, (I - \mathcal{L}) \, w^t, {\mbox{ in }} \Omega, t > 0, \\ w^t &=& 0, {\mbox{ on }} \delta \Omega, t > 0, \\ w^1 &=& \left\{ \begin{array}{lr} D^{1/2} \, S \, (N - I) \, \phi, & {\mbox{ in }} \Omega, \\ 0, & {\mbox{ on }} \delta \Omega, \end{array} \right. \end{eqnarray}

where $\mathcal{L}$ is the symmetric normalized Laplacian operator.

Thus, spectral graph theory implies the existence of a unique solution $v^t = v^t(s,\phi)$, which may be expressed in terms of the $s$-dependent Dirichlet heat kernel:

\begin{equation} \mathcal{H}_t^s = (S \, (I - \mathcal{L}))^{t - 1}, t > 1. \end{equation}

Apparently, $S = I$ reduces the IBVP of social influence to the difusion/heat equation.

The (Stationary) Boundary Value Problem (BVP)

After some standard transformations, the corresponsing stationary problem is easily seen to be (of the form):

\begin{eqnarray} \big(I - S \, (I - \mathcal{L} \big) \, \overline{w} &=& S \, D^{-1/2} \, (N - I) \, \phi, {\mbox{ in }} \Omega, \\ \overline{w} &=& 0, {\mbox{ on }} \delta \Omega, \end{eqnarray}

which is an elliptic BVP with Dirichlet boundary conditions.

Again, spectral graph theory guarantees the existence of a unique steady state solution $\overline{v} = \overline{v}(s,\phi)$, which can be expressed in terms of the $s$--dependent Green function:

\begin{equation} \mathcal{G}^s = \big(I - S \, (I - \mathcal{L})\big)^{-1}, \end{equation}

Again, when $S = I$, the BVP of social influence is reduced to the Laplace/Poison equation.

The Case of a Continuous Steering by a Single Source of Influence

  • $|\partial \Omega| = 1$ or $\partial \Omega = \{i[0]\}$, for a person $i = i[0] \in V$ called source (of opinion transmission in $G$).
  • $v_{i[0]}^t = 1 (\forall t \geq 1)$.
  • Let $s(i[0])_j$ be the vector of susceptibilities corresponding to source $i[0]$, i.e.,
\begin{equation} s(i[0])_j \left\{ \begin{array}{ll} = 0, & {\mbox{ for }} j = i[0],\\ > 0, & {\mbox{ for }} j \in V, j \neq i[0]. \end{array} \right. \end{equation}
  • Let $\phi(i[0])$ be the (almost everywhere) null vector of initial opinions corresponding to source $i[0]$, i.e.,
\begin{equation} \phi(i[0])_j = \left\{ \begin{array}{ll} 0, & {\mbox{ for }} j \neq i[0], {\mbox{ i.e., }} j \in \Omega,\\ 1, & {\mbox{ for }} j = i[0], {\mbox{ i.e., }} j \in \delta \Omega. \end{array} \right. \end{equation}
  • Totally, there exist $n$ potential sources $i[0]$ in $G$.
  • For each potential source, i.e., for each $i = i[0] \in V$, let $(\overline{v}(s(i),\phi(i))_j$ be the steady state opinion that person $j \in \Omega$ attains, when the source of the generated opinion is person $i$.
  • The matrix $\mathcal{U}^{\infty}$ with elements
\begin{equation} \mathcal{U}^{\infty}_{ij} = (\overline{v}(s(i),\phi(i))_j \end{equation}

is called matrix of influentiability of $G$.

  • Apparently, $\mathcal{U}^{\infty}_{ii} = 1$, while $\mathcal{U}^{\infty}_{ij} \in (0, 1]$, for $i
\begin{equation} \mathcal{U}^{\infty}_{ij} \left\{ \begin{array}{ll} = 1, & {\mbox{ for }} i = j,\\ \in (0, 1], & {\mbox{ for }} i \neq j. \end{array} \right. \end{equation}

I. The index of influence-out-degree centrality of person $i$: \begin{equation} c{influence-out-degree}(i) = \frac{1}{n - 1} \, \sum{j \in [n], j \sim i} \mathcal{U}^{\infty}_{i, j}. \end{equation}

The index of influence-out-degree centrality of person $i$ determines the normalized cumulative volume of opinion broadcasting that $i$ broadcasts to all her neighbors, when $i$ is the single (exclusive) source of opinion transmission. Apparently, this index depends only on the vector of susceptibility coefficients $s$, i.e., $c_{influence-out-degree}(i) = c_{influence-out-degree}^{s}(i)$ in such a way that:

\begin{equation} 0 = c_{influence-out-degree}^{0}(i) \leq c_{influence-out-degree}^{s}(i) \leq c_{influence-out-degree}^{1}(i) = c_{degree}(i), \end{equation}

where the last term in the previous inequality would be the index of out-degree centrality of person/vertex $i$.

II. The index of influence-in-degree centrality of person $i$: \begin{equation} c{influence-in-degree}(i) = \frac{1}{n - 1} \, \sum{j \in [n], j \sim i} \mathcal{U}^{\infty}_{j, i}. \end{equation}

The index of influence-in-degree centrality of person $i$ determines the normalized cumulative volume of opinion reception that can be delivered cumulatively to $i$ from all her neighbors, each time a neighbor of $i$ is a source opinion transmission. Apparently, this index depends only on the vector of susceptibility coefficients $s$, i.e., $c_{influence-in-degree}(i) = c_{influence-out-degree}^{s}(i)$ in such a way that:

\begin{equation} c_{degree}(i) = c_{influence-in-degree}^{0}(i) \leq c_{influence-in-degree}^{s}(i) \leq c_{influence-in-degree}^{1}(i) = 1. \end{equation}

Notice that if the above social influence model was reformulated in such a way that it could be applicable to directed graphs too, the first term in the previous inequality would be the index of in-degree centrality of person/vertex $i$.

Importing Python modules and scripts

In [1]:
%matplotlib inline 
%load_ext autoreload
import networkx as nx
import pandas as pd
import numpy as np
from numpy import linalg
from numpy.linalg import inv
from scipy.linalg import eigvalsh
from datetime import datetime
from lightning import Lightning
import create_imgtex as crim
import seaborn as sns
from scipy import stats
import os
import random
# !pip install --user tabulate
/home/mab/.local/lib/python2.7/site-packages/matplotlib/font_manager.py:273: UserWarning: Matplotlib is building the font cache using fc-list. This may take a moment.
  warnings.warn('Matplotlib is building the font cache using fc-list. This may take a moment.')
In [2]:
%autoreload 2
from chAs import *
import chAs as ca
import steady_utils as su
import influence as infl

Creating a graph

In [3]:
# n=10
# p=.3
# G=ca.create_conn_random_graph(n,p)
# source = [G.nodes()[0]]
# name = 'A connected Random-Renyi graph with %i nodes and probability %f' %(n,p)

# G=nx.petersen_graph()
# name = 'Petersen Graph'

# n=10
# G=nx.complete_graph(n)
# name = 'Complete Graph of %i nodes' %n

G=nx.karate_club_graph()
name = 'Karate Club Network'

# G=nx.florentine_families_graph()
# gnod={}
# for i,nd in enumerate(G.nodes()):
#     gnod[nd]=i
# G=nx.relabel_nodes(G,gnod)
# print G.nodes()
# print gnod
# name = 'Florentine Families Network'

# G=nx.krackhardt_kite_graph()
# name = 'Krackhardt Kite Network'

n=len(G.nodes())
p=0
source = [G.nodes()[0]]
In [4]:
degrc=nx.degree_centrality(G)
closc=nx.closeness_centrality(G)

labels={}
llabels={}
lllabels={}
noodd={}
groups={}
for i,nd in enumerate(G.nodes()):
    noodd[nd]=i
    labels[i]='id = %s, deg_cent = %.4f, clos_cent = %4f' %(nd,degrc[nd],closc[nd]) #degggss[nd],closs[nd])
    llabels[i]='id = %s, %s' %(nd,nx.neighbors(G,nd))
    lllabels[i]='id = %s, %s, deg_cent = %.4f, clos_cent = %4f' %(nd,nx.neighbors(G,nd),degrc[nd],closc[nd]) #degggss[nd],closs[nd])
    if nd in source:
        groups[i]=1
    elif nd not in source:
        groups[i]=2
lali=[]
grouli=[]
nlali=[]
nnlali=[]
for v in G.nodes():
    lali.append(labels[noodd[v]])
    nlali.append(llabels[noodd[v]])
    nnlali.append(lllabels[noodd[v]])
    grouli.append(groups[noodd[v]])    
edgess=[]
for edg in G.edges():
    edgess.append([noodd[edg[0]],noodd[edg[1]]])

Graph visualization

In [5]:
lgn = Lightning(ipython=True,local=True,size='large') # local vis
# lgn = Lightning(ipython=True, host='http://public.lightning-viz.org',size='full') # vis at server

# NODE COLORS
# 1. To use different colors for each country, set "group=grouli" below
# 1. To use different colors for type of node (officer, intermediary, entity, address), set "group=None" below

vis=lgn.force(conn=edgess, values=None, labels=nnlali, color=None, group=grouli, colormap=None, size=None, tooltips=True,
              width=1200, brush=True,zoom=True, height=None)#,

# To display in locally, use the first command and to display it online the second:
print '%s' %name
vis # local vis
Lightning initialized