# Influencer Identification on Link Predicted Graphs

Laura P. Schaposnika and Raina Wub

###### Abstract

How would admissions look like in a university program for influencers? In the
realm of social network analysis, influence maximization and link prediction
stand out as pivotal challenges. Influence maximization focuses on identifying
a set of key nodes to maximize information dissemination, while link
prediction aims to foresee potential connections within the network. These
strategies, primarily deep learning link prediction methods and greedy
algorithms, have been previously used in tandem to identify future
influencers. However, given the complexity of these tasks, especially in
large-scale networks, we propose an algorithm, The Social Sphere Model, which
uniquely utilizes expected value in its future graph prediction and combines
specifically path-based link prediction metrics and heuristic influence
maximization strategies to effectively identify future vital nodes in weighted
networks. Our approach is tested on two distinct contagion models, offering a
promising solution with lower computational demands. This advancement not only
enhances our understanding of network dynamics but also opens new avenues for
efficient network management and influence strategy development.

link prediction, centrality metrics, vital nodes identification

##  I Introduction

When a company is launching a new product and wants to use social media for
marketing, understanding who to hire for such campaigns becomes of most
importance to maximize profit. With the explosion of social media in recent
years, a common strategy has been to target certain influential individuals
for advertising. These individuals, or “influencers,” become the initial
spreaders in different social settings, and through their connections and
followers, companies reach greater awareness (and sales) in the entire
society. However, social groups are constantly evolving and thus influencers
in certain social setting may no longer be the optimal selection in the few
months or years until the product is released, which can lower efficiency. It
becomes clear, then, that being able to predict future influencers is
extremely important.

Within a mathematical setting, one can consider social networks as graphs,
where the nodes represent members of the network, and their connections are
represented by edges. The study of how nodes can influence a network has been
done for many decades, and the reader can refer to recent surveys such as Lü
et al.’s listofidentificationtypes  in 2016, Pei et al.’s survey2  in 2019,
and AbdulAmeer et al.’s survey1  in 2022 to learn about the scope of such
work.

In particular, Domingos and Richardson imp1  studied influence through a viral
marketing perspective. In 2003, Kempe et al. imp2  formalized this as the
influence maximization problem (IMP) of choosing $k$ nodes of greatest
influence, proving that a complete solution was NP-hard. However, it is
interesting to note that to the best of our knowledge, no mathematical
definition of a social Influencer as been proposed in the literature, and thus
we shall introduce here what we think can be a useful way of thinking of such
important individuals within our society (see Definition 29).

In the present paper we will focus on heuristic measures, revolving around
local centralities due to lower time complexity: while global metrics take
into consideration more complete information about the graph, they are often
computationally expensive. Furthermore, Hu et al. hu  claimed that global
influence can be approximated by local influence from neighbors of order
around three to four, which means local measures may be more cost-effective.
As mentioned before, one should keep in mind that social networks are
constantly changing. In 2004, Liben-Nowell and Kleinberg
linkpredictioncomparison  formalized the link prediction problem for social
networks as predicting future edges based on knowledge of the current graph.
Hasan and Zaki linkpredictionsurvey  and Lü and Zhou linkpredictionsurvey2
provided surveys of link prediction results. In our work, we shall focus on
local similarity metrics and their quasi-local extensions given by Aziz et al.
globalextensions , which are heuristic measures similar to centrality.

In 2019, Ghafouri and Khasteh lpim1  introduced the idea of using a graph
modelling technique to engage in link prediction prior to use of greedy
algorithms for influence maximization as a way to account from invisible edges
between nodes (i.e. edges not observed when collecting data on the network).
Singh and Kailasam lpim2  utilized a similar approach when predicting sets of
influential nodes for the next iteration of the graph through link prediction
using the a type of Restricted Boltzmann Machine (RBM). In 2023, Yanchenko et
al. exante  discussed the use of deep learning link prediction to understand
the outcomes of the future networks, then identify influential nodes through
the greedy algorithm and dynamic degree discount. We take a similar approach,
but focus on heuristic link prediction measures whereas they consider linear
regression, deep learning, matrix factorization, and graph neural networks,
and more. We also evaluate many other common centrality metrics and algorithms
that, to the best of our knowledge, previous literature has not covered. In an
effort to lower time complexity, our graph prediction also makes use of
expected value to decrease computation cost of influence spread.

We shall seek to quantify influence through simple and complex contagion. As
stated by Min & Miguel simplecontagion , simple contagion is a model from
epidemiology that runs on the assumption that there is a fixed probability of
transmission between each pair of vertices. Centola and Macy
complexcontagiondefinition  defined complex contagion as a model for actions
or information with some perceived social cost, considering both personal
resistance to influence and forces like peer pressure and social affirmation:
a person is infected only if sufficiently many of their neighbors are.

In general terms, easily accepted information spreads as simple contagion
whereas more controversial or effort-requiring topics may be complex
contagion. Examples of some categorizations can be seen in Table 1 below. We
shall begin our study in Section II) by studying link prediction and
influencer identification separately on dynamic social networks, and then we
shall examine influence through simple and complex contagion models in Section
IV.2). By putting the above together we shall present our definition of
influencer, detail the specific influence model definitions, and introduce our
concrete algorithm, the Social Sphere Model (see Section III).

Information Type |  Contagion Type |  Source
---|---|---
Viral Memes |  Simple Contagion |  Weng et al. memescontagions
Nonviral Memes |  Complex Contagion |  Weng et al. memescontagions
Spread of Disease |  Simple Contagion |
Health Behaviors |  Complex Contagion |  Campbell and Salath’e healthbehaviors
Music |  Simple Contagion |  Notarmuzi et al. conversationcontroversial
TV Shows |  Simple Contagion |  Notarmuzi et al. conversationcontroversial
Political/Societal Controversies |  Complex Contagion |  Notarmuzi et al. conversationcontroversial
Social Movements |  Complex Contagion |  Centola change
Table 1: Example contagion scenarios and categorizations.

Researchers have noted that the performances of the same set of nodes differ
noticeably in the simple and complex contagion (see Figure 1 for an example).
For example, Watts and Dodds ltmbehavior  found that while the former places a
great deal of emphasis on influencers, the latter says away from choosing
traditional influencers as initial nodes, especially when considering the
relative costs (traditionally influential nodes are likely more expensive
hires).

(a) Simple Contagion at time $t=0$

(b) Simple Contagion at time $t=1$

(c) Simple Contagion at time $t=7$

(d) Complex Contagion at time $t=0$

(e) Complex Contagion at time $t=2$

(f) Complex Contagion at time $t=7$

Figure 1: Contagion examples with initial infected node 0 and distances marked
on edges (successful infections and successful interactions for complex
contagion are marked with red).

In Section V, and through the use of the Social Sphere Model, we observe that
influence generally spreads much faster in the simple contagion model than in
the complex. We also notice the following:

  * •

better performance for some parameters in our modified prediction metrics and
algorithms when compared to the originals (see Section II);

  * •

high similarity between our model’s predicted influencers and the ‘true’
future influencers in both selection and collective influence, suggesting the
effectiveness of our model; and

  * •

potential in empirical datasets for identifying influencers overlooked by a
static model.

Our paper is organized as follows: in Section II, we explore previous works
around heuristic measures in link prediction and influencer identification. We
explain the Social Sphere Model and our mathematical definition for
influencers in Section III. Our methodology is detailed in Section IV, with
evaluation methods in Section IV.1, concrete contagion models in Section IV.2,
and experimental setup in Section IV.3. We examine our model’s influence in
simple and complex contagion through analysis of our algorithm’s results on
both empirical datasets and random graphs in Section V. Finally, we give a
summary and future directions for our research in Section VI.

##  II Social Networks

Social networks are generally modeled using graph theory by expressing the
network as a graph $G=(V,E)$, for $V$ the set of vertices (the individuals of
the network) and $E$ the set of edges (the connections between individuals).
Given such a graph, one may assign a weight function

$w:E\rightarrow[0,1],$

where $w(u,v)$ is the weight of edge $uv$. Such weights may represent a
variety of parameters of the social network, and in this paper, we consider
weights to be approximations for probabilities of influence transmission, be
it information, disease, or more. In particular, we take inspiration from
Goyal et al. bernoullidistribution , who took the weights $p(i,j)$ to be the
total number of interactions over the total number of trials. In order to
study such models, one may assume that the probability of interaction between
two nodes during a fixed interval of time is constant, in which case each
interval of time can be considered as a Bernoulli trial for temporal datasets.

###  II.1 Weight functions

Since the geometric distribution counts the number of Bernoulli trials needed
to succeed, one can approximate the expected number of intervals needed for an
interaction to occur between two nodes $i$ and $j$ as $\frac{1}{w(i,j)}$, the
expected value of the geometric distribution with probability $w(i,j)$. These
distances are marked on the edges of each graph in Figure 1, and they can be
used to approximate the amount of time needed for information to spread along
each edge. Formally, we can define them as follows.

######  Definition 1.

The distance between two vertices $u$ and $v$ though their edge $uv$ is given
by the function

$\displaystyle d:E$ $\displaystyle\rightarrow$ $\displaystyle\mathbb{R}$
$\displaystyle uv$ $\displaystyle\mapsto$ $\displaystyle\frac{1}{w(u,v)}.$ (1)

For convenience, we will also give some preliminary definitions around
neighborhoods, paths, and degree:

######  Definition 2.

For a graph $G=(V,E)$, define the following:

  * •

for $v\in V$, the set of all $n$-order neighbors of $v$ is denoted by
$N_{n}(v)$;

  * •

for $u,v\in V$, the set of paths between $u$ and $v$ is denoted by $P(u,v)$;

  * •

for a path

$p:(u=v_{0},v_{1},\dots v_{n}=v)\in P(u,v),$

between $u$ and $v$, we define the values

$\displaystyle a(p)$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{n-1}d(v_{i},v_{i+1})$ (2) $\displaystyle b(p)$
$\displaystyle=$ $\displaystyle\sum_{i=0}^{n-1}w(v_{i},v_{i+1});$ (3)
$\displaystyle D(u,v)$ $\displaystyle=$ $\displaystyle\min_{p\in
P(u,v)}a(u,v).$ (4)

To illustrate the above definitions, consider the graphs in Figure 1. In this
setting, one has that

$\displaystyle N_{1}(0)$ $\displaystyle=$ $\displaystyle\\{1\\}$
$\displaystyle N_{2}(0)$ $\displaystyle=$ $\displaystyle\\{3,4\\}$
$\displaystyle P(0,2)$ $\displaystyle=$
$\displaystyle\\{(0,1,3,2),(0,1,4,2)\\}$ $\displaystyle a((0,1,3,2))$
$\displaystyle=$ $\displaystyle 2+3+3=8$ $\displaystyle b((0,1,3,2))$
$\displaystyle=$
$\displaystyle\frac{1}{2}+\frac{1}{3}+\frac{1}{3}=\frac{7}{6}$ $\displaystyle
D(0,2)$ $\displaystyle=$ $\displaystyle 7$

(achieved by the path $p=(0,1,4,2)$).

######  Remark 1.

The function $D(u,v)$ calculates the minimum weighted distance between
vertices $u$ and $v$.

######  Definition 3.

Given a graph $G=(V,E)$, let

  * •

$k_{u}=|N_{1}(u)|$ be the unweighted degree of vertex $u$,

  * •

$\langle k\rangle=\frac{1}{|V|}\sum_{v\in V}k_{v}$ be the average degree over
all vertices in $G$,

  * •

$s_{u}=\sum_{v\in N(u)}w(u,v)$ be the weighted degree (strength) of vertex
$u$, and

  * •

$\langle s\rangle=\frac{1}{|V|}\sum_{v\in V}s_{v}$ be the average strength
over all vertices in $G$.

Coming back to Figure 1’s underlying graph, for instance, we can see that

$k_{0}=1,~{}\langle k\rangle=\frac{1}{5}(1+3+2+2+2)=2,~{}s_{0}=\frac{1}{2}$

and $\langle
s\rangle=\frac{1}{5}(\frac{1}{2}+\frac{4}{3}+\frac{2}{3}+\frac{2}{3}+\frac{5}{6})=\frac{4}{5}$.

###  II.2 Link Prediction

Link prediction is a field that seeks to identify potential future edges in a
graph by considering properties of the current graph. There are many types of
link prediction strategies, but keeping time complexity in mind we will focus
on local methods in this paper, where operating over pairs of nodes will give
us similarity scores $s(u,v)$ for all $u\neq v\in V,uv\not\in E$.

The types of link prediction we will be using are path-based, focusing on
first-order and second-order neighbors of nodes. We are interested in how a
greater penalty for common neighbors with higher degree can affect
performance.

We shall give a brief description of the following link prediction models,
which shall allow us in particular to see that they can be thought of as
variations or extensions of each other:

  * •

common neighbors (e.g. commonneighbors ),

  * •

local path (e.g. resourceallocation ),

  * •

Jaccard coefficient (e.g. linkpredictioncomparison ),

  * •

resource allocation (e.g. resourceallocation ),

  * •

quasi-local resource allocation (e.g. globalextensions ),

  * •

RA$-2$, and

  * •

quasi-local RA$-2$.

Common Neighbors. Considering collaboration networks, Newman proposed in
commonneighbors  that the more common neighbors two nodes share, the more
likely they are to form a link in the future, leading to the following
definition:

######  Definition 4.

The common neighbors (CN) similarity score for $u,v\in V$ is

$s_{u,v}^{CN}:=|N(u)\cap N(v)|.$

Murata and Moriyasu weightedlinkprediction  amended common neighbors for
weighted networks to be dependent on the sum of the weights between the nodes
summed over common neighbors leading to the following weighted definition:

######  Definition 5.

The weighted common neighbors (WCN) similarity score for $u,v\in V$ is

$s_{u,v}^{WCN}:=\sum_{x\in N(u)\cap N(v)}\frac{b(u,x,v)}{2}.$

Local Path (Quasi-Local Common Neighbors). Zhou et al. resourceallocation
created the local path metric from the observation that common neighbors as a
similarity metric often gives the same scores to many nodes, making the actual
rankings ambiguous. They extended the computation of score to include paths of
three edges, weighting the longer paths by some $\epsilon$:

######  Definition 6.

The local path (LP) similarity score for $u,v\in V$ is

$s_{u,v}^{LP}:=|N(u)\cap N(v)|+\epsilon|P_{2}(u,v)|.$

Here, we take $\epsilon=10^{-3}$. Moreover, Aziz et al. globalextensions
noted that local path is the quasi-local extension of common neighbors.
Extending on the previously mentioned work of Murata and Moriyasu
weightedlinkprediction , Bai et al. weightedlocalpath  developed a weighted
index for local path (weights here are adjusted to match the latter):

######  Definition 7.

The weighted local path (WLP) similarity score  for $u,v\in V$ is

$s_{u,v}^{WLP}:=s_{u,v}^{WCN}+\epsilon\sum_{(u,i,j,v)\in
P(u,v)}\frac{b(u,i,j)\cdot b(i,j,v)}{4}.$

Jaccard Coefficient. Liben-Nowell and Kleinberg linkpredictioncomparison
derived the Jaccard coefficient from information retrieval, with the following
definition:

######  Definition 8.

The Jaccard coefficient (JC) similarity score for $u,v\in V$ is

$s_{u,v}^{JC}:=\frac{N(u)\cap N(v)}{N(u)\cup N(v)}.$

Within this setting, a penalty is given when the union of the neighborhoods of
the nodes is larger. This can be understood as the more friends people have,
the less likely that they will both be with a specific common neighbor and
then meet.

Resource Allocation. Zhou et al. resourceallocation  came up with the resource
allocation metric based on the eponymous process where each individual has
resources to be split evenly among its neighbors, defined as follows:

######  Definition 9.

The resource allocation (RA) similarity score for $u,v\in V$ is

$s_{u,v}^{RA}:=\sum_{x\in N(u)\cap N(v)}\frac{1}{|N(x)|}.$

Within this model, a penalty is given to the common neighbors with greater
degree on the intuition that a shared neighbor with more neighbors itself is
less likely to connect those two specific neighbors when it chooses to
introduce people on account of having fewer resources to do so.

Lü and Zhou weightednetworkweakties  made a variant of the above resource
allocation for weighted graphs, leading to the following:

######  Definition 10.

The weighted resource allocation (WRA) similarity score for $u,v\in V$ is

$s_{u,v}^{WRA}:=\sum_{x\in N(u)\cap N(v)}\frac{b(u,x,v)}{s(x)}.$

Quasi-Local Resource Allocation. Aziz et al. globalextensions  made a quasi-
local extension for RA, where one considers paths of three edges in addition
to paths of two edges. In other words:

######  Definition 11.

The quasi-local resource allocation (QRA) similarity score for $u,v\in V$ is

$s_{u,v}^{QRA}:=\left(\sum_{x\in N(u)\cap
N(v)}\frac{1}{|N(x)|}\right)+\epsilon\left(\sum_{(u,i,j,v)\in
P(u,v)}\frac{1}{|N(i)||N(j)|}\right).$

The weighted quasi-local resource allocation (WQRA) similarity score for
$u,v\in V$ is

$s_{u,v}^{WQRA}:=s_{u,v}^{WRA}+\epsilon\sum_{(u,i,j,v)\in
P(u,v)}\frac{b(u,i,j)\cdot b(i,j,v)}{s(i)s(j)}.$

A New Resource Allocation Variant: RA$-2$. Finally, returning to the intuition
that common neighbors with larger degrees contribute less to the similarity
between two nodes, we shall introduce here a new similarity metric as a
version of resource allocation. To the best of our knowledge, this is the
first time this variant has been introduced. Suppose a node $u$ wants to
connect two of its neighbors: there are then $\binom{|N(u)|}{2}$ pairs to
choose from, so each pair of its neighbors has a $\frac{1}{\binom{|N(u)|}{2}}$
probability of being linked. For ease of calculation, we approximate this to

$\frac{2}{|N(u)|^{2}}.$

Summing over all common neighbors, we then have the RA$-2$ similarity:

######  Definition 12.

The RA$-2$ similarity score for vertices $u,v\in V$ is

$s_{u,v}^{RA2}:=\sum_{x\in N(u)\cap N(v)}\frac{2}{|N(x)|^{2}}.$

The weighted RA$-2$ (WRA$-2$) similarity score  for $u,v\in V$ is

$s_{u,v}^{WRA2}:=\sum_{x\in N(u)\cap N(v)}\frac{b(u,x,v)}{s(x)^{2}}.$

Quasi-Local variant of RA$-2$ Inspired by Aziz et al. globalextensions , we
also create a quasi-local variant for RA$-2$:

######  Definition 13.

The quasi-local RA$-2$ (QR$-2$) similarity scorefor $u,v\in V$ is

$s_{u,v}^{QR2}:=\left(\sum_{x\in N(u)\cap
N(v)}\frac{2}{|N(x)|^{2}}\right)+\epsilon\left(\sum_{(u,i,j,v)\in
P(u,v)}\frac{4}{|N(i)|^{2}\cdot|N(j)|^{2}}\right).$

The weighted quasi-local RA$-2$ (WQR$-2$) similarity score for $u,v\in V$ is

$s_{u,v}^{WQR2}:=s_{u,v}^{WRA-2}+\epsilon\left(\sum_{(u,i,j,v)\in
P(u,v)}\frac{b(u,i,j)\cdot b(i,j,v)}{f(i)^{2}f(j)^{2}}\right).$

In the following sections we shall illustrate the importance of these novel
similarity metrics and their use within our Social Sphere Model.

###  II.3 Node Centrality

Metric |  Time Complexity (unweighted) |  Time Complexity (weighted) |  Type
---|---|---|---
Degree Centrality |  $O(|E|)$degreecomplexity  |  $O(|E|)$degreecomplexity  |  local listofinfluencers2
Coreness |  $O(|E|)$corenessalgorithm  |  $O(|E|)$ |  iterative listofinfluencers2
H-index |  $O(|V|\langle k\rangle)$ h-indexcomplexity  |  $O(|V|\langle k\rangle)$ |  local listofinfluencers2
LocalRank |  $O(|V|\langle k\rangle^{2})$ localrank  |  N/A |  local listofinfluencers2
Clustering Coefficient (and ClusterRank) |  $O(|V|\max_{v\in V}k_{v}^{2})$ clusteringcoefftime  |  $O(|V|\max_{v\in V}k_{v}^{2})$ |  listofinfluencers2
Closeness |  $O(|V||E|)$ timecomplexities  |  $O(|V||E|+|V|^{2}\log|V|)$ fibheap  |  path-based listofidentificationtypes , global listofinfluencers2
Betweenness |  $O(|V||E|)$ betweennessalgorithm  |  $O(|V||E|+|V|^{2}\log|V|)$ betweennessalgorithm  |  path-based listofidentificationtypes , global listofinfluencers2
Eigenvector |  $O(|V|^{2}\cdot\text{iteration \\#})$ poweriterationmethod  |  $O(|V|^{2}\cdot\text{iteration \\#})$ poweriterationmethod  |  global, iterative listofinfluencers2
PageRank |  $O(|E|\cdot\text{iteration \\#})$pagerankcomplexity  |  $O(|E|\cdot\text{iteration \\#})$pagerankcomplexity  |  iterative listofinfluencers2
Balanced Index |  $O(\langle k\rangle V+V\log V)$ ltmmetrics  |  $O(\langle k\rangle V+V\log V)$ |  local
Table 2: Time complexities and categorizations of centrality metrics on
weighted networks.

Vital node identification is a crucial part of social network analysis,
applicable to many field ranging from marketing to epidemiology. Centrality
methods, some of the most common of these processes, offer a window into
understanding influence dynamics within social networks. Mathematically,
centrality methods are based on functions that assign a real-number score to
each $v\in V$, essentially ranking the nodes in terms of influence
listofidentificationtypes .

The choice of centrality metric often significantly alters the perceptions of
who the vital nodes (influencers) are. This section explores common centrality
metric definitions, operating principles, and practical implications. We shall
give a brief description of the following twelve methods, of which Table 2
contains a comparative analysis of the time complexities and classifications:

  * •

degree;

  * •

coreness, introduced by Seidman kcoreorigin ;

  * •

H-index, introduced by Hirsch h-indexorigin ;

  * •

LocalRank, introduced by Chen et al. localrank ;

  * •

ClusterRank, introduced by Chen et al. clusterrank ;

  * •

closeness, introduced by Bavelas closenessorigin ;

  * •

betweenness, introduced by Freeman betweennessorigin ;

  * •

eigenvector, introduced by Landau eigenvectororigin ;

  * •

PageRank, introduced by Brin and Page pagerankorigin ;

  * •

LeaderRank, introduced by Lü et al. leaderrank ;

  * •

balanced index, introduced by Karampourniotis et al. ltmmetrics , and

  * •

complex path, introduced by Guilbeault and Centola complexpathlength .

Degree. One of the fastest methods to compute node centrality is by
considering its graph theoretical degree, creating a centrality metric from
the traditional idea that the more connections a vertex has, the more
influential it is.

######  Definition 14.

The degree centrality of a node $i$ is defined as

$DC_{i}=k_{i}.$

The weighted degree centrality (strength) of a node $i$ is defined as

$S_{i}=\sum_{j\in N(i)}w(i,j)=s_{i}.$

Coreness. In 1983, Seidman kcoreorigin  defined the $k$-core as a measure of
the network cohesion of a node, where a subgraph is a $k$-core if it has
minimum degree at least $k$. Batagelj and Zaveršnik corenessalgorithm  define
a $k$-core decomposition algorithm in Algorithm 1.

Algorithm 1 $k$-shell decomposition corenessalgorithm

Graph $G$

Sort $V$ by increasing degree

for each $v\in V$ in order do

core$[v]$ = deg$[v]$

for $u\in N(v)$ do

if deg$[u]>$ deg$[v]$ then

deg$[u]-=1$

Reorder $u$ in $V$

end if

end for

end for

Output list of core values

Later on, Kitsak et al. coreness  took the core numbers for each vertex as its
corenness value. Eidsaa and Almaas s-core  created a weighted version of
$k$-core, where node strength is used rather than degree in the decomposition
and when a node $u$ is selected (has the minimum strength in the pruned
graph), it is in the $\lceil s_{u}\rceil$-core. A similar definition can be
taken using $\lfloor s_{u}\rfloor$, and the algorithm is modified accordingly
in Algorithm 2 below.

Algorithm 2 weighted $k$-shell decomposition

Graph $G$

Sort $V$ by increasing strength

for each $v\in V$ in order do

core$[v]=\lfloor s(v)\rfloor$

for $u\in N(v)$ do

if deg$[u]>$ deg$[v]$ then

deg$[u]-=w(u,v)$

Reorder $u$ in $V$

end if

end for

end for

Output list of core values

H-index. Along the same lines of study, but within the academic world, Hirsch
h-indexorigin  proposed the H-index to measure the impact of a scientist’s
research outputs through considering citations per paper. Lü et al. h-index
then used it in the context of centrality metrics, introducing the following
definition:

######  Definition 15.

Define the operator $H$ on a finite set $S=\\{x_{1},\dots,x_{m}\\}$ as the
maximum integer $h$ such that there are $h$ elements in $S$ with values $\geq
h$. The $n$-order H-index is defined as

$h_{i}^{(n)}=H(h_{j_{1}}^{(n-1)},\dots,h_{j_{k_{i}}}^{(n-1)}),$

where $h_{i}^{(0)}=DC_{i}$.

From the above perspective, the classical H-index can be seen as the $1$-order
H-index. Lü et al. h-index  proved that the H-index forms a middle ground
between a progression from degree centrality to coreness, where the $0$-order
index is degree and the $\infty$-order index converges to the $k$-core score.
Finally, it is interesting to note that Zhao et al. weightedhindex  defined
the w-lobby index, a metric for weighted networks similar to the H-index, as
follows:

######  Definition 16.

The w-lobby index of a node $u$ is the largest integer $k$ such that
$|\\{s(v)\geq k|v\in N(u)\\}|\geq k$.

Through the above definitions, we can introduce the $n$-order H-degree, which
is defined as

$WH_{i}^{(n)}=WH(wh_{j_{1}}^{(n-1)},\dots,wh_{j_{k_{i}}}^{(n-1)}),$

with $wh_{i}^{(0)}=s(i)$. In this paper, we take the $10$th order H-index.

LocalRank. Aiming to find a more effective local method due to the high time
complexities of global and path-based methods, Chen et al. localrank
introduced the following extension of degree centrality to more than just
first-order neighborhoods:

######  Definition 17.

The LocalRank score of a node $u$ is

$LR_{u}=\sum_{v\in N(u)}\sum_{w\in N(v)}|N(w)|+|N_{2}(w)|.$

ClusterRank. Watts and Strogatz clusteringcoeff  defined the clustering
coefficient around the percent of existing links between a node’s neighbors
over the total potential amount to quantify how clustered the network is:

######  Definition 18.

The clustering coefficient of a node $i$ in the directed network $c_{i}$ is
defined as

$c_{i}=\frac{|\\{(jk\in E|j,k\in N(i)\\}|}{k_{i}(k_{i}-1)}.$

Working with the intuition that nodes in more clustered parts of the network
may be more redundant and thus have less influence, Chen et al. clusterrank
then used the clustering coefficients of nodes to define the following
centrality metric:

######  Definition 19.

The ClusterRank score of a node $i$ is

$f(c_{i})\sum_{j\in N(i)}(k_{j}+1),$

where $f(c_{i})$ is an exponential function of $c_{i}$ of the form
$\alpha^{-c_{i}}$ for a fixed constant $\alpha$ (usually $10$).

######  Remark 2.

This metric considers the clustering coefficient of the neighboring parts of
the network: a node whose neighbors are already tightly clustered may be able
to spread information within its cluster very quickly, but has more difficulty
doing outreach to other communities, whereas nodes that may bridge clusters
might be better.

Taking the weighted score to be $f(c_{i})\sum_{j\in N(i)}(s_{j}+1)$ gives a
modification for weighted networks.

Closeness. Bavelas introduced in 1948 closenessorigin  the idea of closeness
centrality as proportional to the reciprocal of the sum of the shortest path
lengths from each pair of vertices $u\neq v$. Rephrasing, Freeman closeness
defines the concept of closeness centrality as a measure of the relative
proximity of a node $p_{k}$ to the rest of the graph $G$, defined as

$C_{C}(p_{k})=\frac{n-1}{\sum_{i=1}^{n}D(p_{k},p_{i})},$

where $V=\\{p_{1},\dots,p_{n}\\}$ are the vertices of the graph.

In a survey of influencer identification metrics, Lü et al.
listofidentificationtypes  note that disconnected networks then pose a problem
as distances go to infinity, making the nodes indistinguishable by closeness
centrality (as they are all then $0$). They then give the following
modification:

######  Definition 20.

The closeness centrality of node $i$ is defined as the reciprocal of the
harmonic mean of the geodesic distances from $i$ to all other nodes, i.e.

$CC_{i}=\frac{1}{n-1}\sum_{j\neq i}\frac{1}{d_{i,j}}.$

Betweenness. Betweenness centrality considers how critical a node $i$ is to
the spread of information, e.g. what percentage of shortest paths going from
one node to another must pass through $i$. First formally defined it in 1977
by Freeman betweennessorigin , it can be understood along with an efficient
algorithm for computing betweenness centrality, through the work of Brandes
betweennessalgorithm :

######  Definition 21.

The betweennness centrality of a node $i$ is simply

$BC_{i}=\sum_{s,t\neq i,s\neq t}\frac{g_{st}^{i}}{g_{st}},$

where $g_{st}^{i}$ is the number of paths that pass through $i$ among the
shortest paths between $s$ and $t$ and $g_{st}$ is the number of shortest
paths between $i$ and $j$.

Eigenvector. In eigenvectororigin  Landau gave a clarified overview of a
previous paper of his detailing the use of eigenvectors to rank chess players,
which has been credited with being the first use of eigenvector centrality.
Later on, Lü et al. listofidentificationtypes  defined the eigenvector
centrality scores $EC$ of $G$ as the vector $\vec{x}$ with components
$x_{i}=EC_{i}$ such that $\vec{x}:=\frac{1}{\lambda}A\vec{x}$ for the largest
eigenvector $\lambda$ of $A$. In other words,

######  Definition 22.

The eigenvector centrality of a node $i$ is the $i$th component of the
eigenvector corresponding to the largest eigenvalue of $A$.

The assumption behind this is that a node’s influence is a linear combination
of the influences of its neighbors, weighted by the weights of its outgoing
edges.

PageRank. PageRank is a search algorithm presented by Brin and Page
pagerankorigin  in a paper where they introduced a Google prototype, modeled
on the behavior of a bored, link-clicking user. They defined the algorithm as
follows:

######  Definition 23.

The PageRank score $PR(u)$ of each vertex $u$ satisfies the following
property:

$PR(u)=(1-d)+d\sum_{v\in N(u)}\frac{PR(v)}{k_{v}},$

where $d$ is a fixed constant in $[0,1]$.

They set $d$ as the damping coefficient, where the $(1-d)$ term represents the
probability a user loses interest and goes to a random webpage. For our
purposes, we will set $d=1$.

Xing and Ghorbani weightedpagerank  modified the PageRank algorithm for
weighted graphs:

######  Definition 24.

The weighted PageRank score $PR(u)$ of each vertex $u$ satisfies the following
property:

$WPR(u)=(1-d)+d\sum_{v\in N(u)}\frac{WPR(v)\cdot w(u,v)}{s_{v}},$

where $d$ is a fixed constant in $[0,1]$.

LeaderRank. Inspired by PageRank, Lü et al. leaderrank  created the LeaderRank
algorithm. Their intention was to include a “ground node” connected to every
node in the network, called node $n+1$, and then used the following recursive
relationship to solve for their influences:

######  Definition 25.

At time $t$, the LeaderRank score of node $i$ is defined recursively as
$LR_{v}(t)=\sum_{v\in N(u)}\frac{LR_{v}(t-1)}{k_{v}}$.

To differentiate the original nodes from the added one, all nodes from the
original graph begin with value $1$ and the leader node begins with value $0$.
Once the function stabilizes, the leader node’s value gets evenly distributed
to the rest of the nodes and deleted. Thus, the LeaderRank scores at the
ending time $t_{c}$ are $LR_{u}=LR_{u}(t_{c})+\frac{LR_{n+1}(t_{c})}{|V|}$ for
each vertex $u\in V$. Weighted LeaderRank scores can be calculated in the same
fashion as weighted PageRank (see Definition 24).

Balanced Index (BI)
Karampourniotis et al. ltmmetrics  introduced the Balanced Index metric for
complex contagion by taking a weighted combination the metrics of resistance,
degree, and neighbors’ degrees. In the context of threshold models, the
resistance $r_{v}$ of a node $v$ is defined as a measure of the current
threshold of each node, where uninfected nodes $v$ initially begin with
$r_{v}=\theta_{v}\cdot s(v)$ and experience decreasing resistance as more of
its neighbors become infected. At resistance $0$ the node also becomes
infected. The neighbors’ degree comes from Karampourniotis et al.’s ltmmetrics
indirect drop of resistance metric, which for node $v$ takes the sum over the
nodes that $v$ could infect in a single turn (i.e. the nodes $j$ with
remaining resistance less than $\frac{w(i,j)}{s(i)}$). The balanced index
metric is thus as follows:

######  Definition 26.

The balanced index score of a node $i$ is

$BI_{i}=a\cdot r_{i}+b\cdot k_{i}+c\sum_{j\in N(i)|r_{j}=1}(k_{j}-1)$

for nonnegative weights $a+b+c=1$.

We can adjust this for weighted graphs by taking

$BI_{i}=a\cdot r_{i}+b\cdot s_{i}+c\sum_{j\in N(i)|r_{j}\leq
w(i,j)}(s_{j}-w(i,j)).$

Complex Path Centrality. Seeking to extend the path length measures
traditionally used in simple contagion to the wide bridges (reinforcing ties)
used in complex contagion paths, Guilbeault and Centola complexpathlength
created complex path centrality, based on the following:

######  Definition 27.

Let $T_{j}$ be the resistance of node $j$. Then,

  * •

the bridge between nodes $i$ and $j$ (the set of nodes in $N(j)$ that are
distance $0$ or $1$ away from some node in the neighborhood of $N(i)$) is

$BW_{i,j}:=\\{v|v\in N(j)\land(v\in N(i)\lor\exists u\in N(i):uv\in E)\\},$

with width $W_{i,j}=|B_{i,j}|$ and indicator variable $[W_{i,j}]$ such that
$[W_{i,j}]=1$ if $W_{i,j}\geq T_{j}$ and $0$ otherwise. A bridge is locally
sufficient for contagion spread if $W_{i,j}\geq T_{j}$.

  * •

$B_{i}$ is the set of nodes $j\neq i$ such that $W_{i,j}>0$,

  * •

the proportion of locally sufficient bridges is $LB_{i}=\sum_{x\in
B_{i}}[W_{i,j}]$,

  * •

$GEO_{i,j}$ is the shortest path between $i$ and $j$ only through edges
between nodes connected by sufficient bridges, and

  * •

$\phi(GEO_{i,j})$ is the list of vertices in the path $GEO_{i,j}$.

From this, they then defined a complex path from node $i$ to node $j$ as the
sequence of sufficiently wide paths from $i$ to $j$. Mathematically, they
write it as follows:

######  Definition 28.

The complex path centrality of a node $i$ is defined as

$CC_{i}=\frac{1}{n-k_{i}}\sum_{i\neq j}|\phi(GEO_{i,j})|.$

###  II.4 Heuristic Top-$k$ Algorithms

In marketing, one generally finds it prudent to advertise through more than
one channel; thus we are concerned with not only finding the single most
effective influencer, which centrality metrics aim to do, but with finding the
set of $k$ influencers with the greatest collective influence for some $k$
determined by budget.

Transitioning from the single influencer concept to this more practical
problem then introduces more complexities. In particular, from Lü et al.
listofidentificationtypes , the straightforward approach of taking the highest
$k$ nodes by score in a given centrality metric could lead to redundant
influences. When information travels relatively unresisted, as in simple
contagion (see Table 1), redundancy is often undesirable, as when a single
successful interaction suffices to influence an individual, having too much
overlap between the chosen nodes’ targets potentially undermines their
collective effectiveness and influence. However, in complex contagion, social
reinforcement is actually necessary to induce influence cascades, which leads
to interesting questions around the straightforward top-$k$ algorithm. We
shall thus assess whether the perceived redundancy truly implies reduced
performance.

In this section, we explore alternative methodologies to reduce redundancy in
the locations of the chosen influencers and modify them to consider centrality
metrics as well. We consider the following five algorithms and modify some of
them to incorporate centrality metrics, as different centrality metrics may
have underlying properties that perform better in tandem with certain
algorithms. For the sake of convenience, call these modified algorithms as
centrality algorithms.

LIR. To reduce the number of adjacent nodes in the chosen set of $k$, Liu et
al. lir_original  created the local index rank (LIR) algorithm. They first
defined the function $Q(x)$ to be $1$ for $x>0$ and $0$ otherwise, then set
the $LI$ score of each node $u$ as

$LI(u)=\sum_{v\in N(u)}Q(k_{v}-k_{u}).$

They then focused on the nodes with $LI$ value $0$ (disregarding those that
simply have no edges) and picked the $k$ nodes from there with largest degree
111In this paper, we modify the original algorithm to incorporate centrality
metrics by sorting by the score the node has on a given centrality metric..

Algorithm 3 LIR Algorithm lir_original

$G$, $k$

Find the $LI$ values for all the nodes

Find the list $\\{v|LI(v)=0\\}$

Sort nodes by degree (decreasing)

Output the top $k$ nodes in the sorted list

LIR-2. Inspired by the LIR method described before, Tao et al. lir2  created
an LIR-2 method as a quasi-local extension to second-order neighbors. They
define the LIR-2 score of a node $u$ to be

$LI_{2}(u)=\sum_{v\in N(u)}Q(k_{v}-k_{u}),$

as shown in Algorithm 4.

Algorithm 4 LIR-2 Algorithm lir2

$G$, $k$

Find the $LI_{2}$ values for all the nodes

Make sorted list $L$ of sets of nodes with the same $LI_{2}$ values in
increasing order

Make an empty list FinalList

for Set $S$ in $L$ do

Sort nodes in $S$ in decreasing order of degree

Append to FinalList

end for

Output the top $k$ nodes in FinalList

Joint Nomination. Dong et al. jointnomination  proposed the joint nomination
algorithm as an algorithm geared towards immunization purposes, where it seeks
to select vertices whose removal can help stop influence spread. Their method
spans $k$ rounds. In each round, a random node is selected as a nominator, one
of its neighbors is randomly selected as conominator, and finally a random
common neighbors of the nominator and conominator is selected into the chosen
set, as shown in Algorithm 5. For developing our Social Sphere model we shall
amend the method of random selection by including probabilities based on
centrality metric score and weights 222In this paper, we deviate from the
original version of joint nomination by choosing nodes with probability
proportional to centrality score, choosing co-nominators with probability
proportional to the weight of the edges between them, and choosing a common
neighbor (nominee) $i$ with probability $\frac{w(u,i)\cdot w(v,i)}{\sum_{j\in
N(u)\cap N(v)}w(u,j)\cdot w(v,j)}$..

Algorithm 5 Joint Nomination jointnomination

$G,k$

Create a set of nominees

Identify a set $N$ of $k$ random nominators

for $u\in N$ do

Identify set of neighbors $C$

Randomly pick a co-nominator $v$, where neighbor $i$ is chosen with weight
$\frac{w(u,i)}{s(u)}$.

while $N(u)\cap N(v)$ is $\emptyset$ do

Remove $v$ from $C$

Randomly pick another co-nominator $v$

if $C$ is empty then

Add a random conominator to the nominees

Break

end if

end while

if $|N(u)\cap N(v)|>0$ then

Randomly pick a nominee $n$ from their common neighbors

Add $n$ to the nominees

end if

end for

Output nominees

VoteRank. From a different perspective, Zhang et al. voterank  proposed
VoteRank as an algorithm where influential nodes are chosen by “votes” of the
vertices in the graph. There are $k$ rounds of voting. Each node begins with
voting power $1$ and score $0$ and will divide their voting power among their
neighbors, thus changing their scores. In this setting, the node with maximum
score is chosen in each round and a resulting penalty given to its neighbors
(see Algorithm 6).

Algorithm 6 VoteRank Algorithm voterank

$G$, $k$

Initialize each node $v$ with score $score(v)=0$ and voting ability $va(v)=1$

Create an (empty) list $L$ of chosen nodes

for $i$ in range$(k)$ do

Reset the scores of all the nodes to $0$

for $u\in V\setminus L$ do

for $v\in N(u)\setminus L$ do

Add $1$ to $score(v)$

end for

end for

Pick the node $n$ with greatest score and add it to $L$

Set the voting power of $n$ to $0$

Decrease the voting power of its neighbors by $\frac{1}{\langle s\rangle}$

end for

Output $L$

Later on, researchers such as Sun et al. wvoterank  have modified VoteRank to
fit weighted graphs by changing the score to include the importance of having
many neighbors. Researchers such as Li et al. dilvoterank  and Kumar and Panda
kcorevoterank  have combined VoteRank with metrics such as the DIL method
(proposed by Liu et al. dil ) and coreness; inspired by these works, we give a
generalization of VoteRank for a given centrality metric $c$ (such as the ones
in Section II.3) by setting each node’s voting ability to its score with
respect to $c$.

Graph Coloring. Finally, aiming to avoid redundancy, Zhao et al. graphcoloring
proposed the graph coloring method as a means of selecting separated vertices.
They use the Welsh-Powell algorithm to separate the graph into sets such that
each set has a unique color and no nodes in the same set share an edge. For a
given centrality metric, they then pick the $k$ nodes with highest score from
the largest independent set as their chosen $k$ vertices.

Algorithm 7 Welsh-Powell Algorithm graphcoloring

Graph $G$

Label nodes as $v_{1},\dots,v_{n}$ in descending order according to degree

Let $\pi(v_{1})=1$

for $i$ in $\\{1,2,\dots,n-1\\}$ do

Let $C(v_{i+1})=\\{\pi(v_{j})|j\leq i,v_{j}\in N(v_{i+1})\\}$

Take the smallest numbered color in the set of colors $C$ not in $C(v_{i+1})$
as $\pi(v_{i+1})$

$i+=1$

end for

Output the values of the color function $\pi$

Through the extension and modification of the above algorithms, we shall
proceed to introduce our Social Sphere Model.

##  III The Social Sphere Model

Expanding on the previous sections, we shall introduce here our model, the
Social Sphere Model for path-based similarity and heuristic centrality
measures, an approach designed here to predict future influencers in changing
social networks. This model synthesizes key elements of link prediction and
top-$k$ influencer algorithms, offering a comprehensive tool for understanding
and anticipating changes in social networks. The uniqueness of our approach
lies in the use of lower complexity link prediction metrics rather than more
costly neural networks and the inclusion of expected value in our predicted
graph creation.

###  III.1 Mathematical Influencers

As mentioned before, one may study social networks through their graph
representation, where vertices represent individuals, and their relations are
reflected within the edges. In influence maximization, influencers are often
defined as those most important to a network, whether structurally or
influentially survey2 . In this paper, we shall use a more specific definition
of influencer in relation to centrality and influence maximization algorithms.

######  Definition 29 (Influencer).

A vertex in a network represented by a graph $G$ is an influencer (with
respect to some centrality metric) if it is either a $k$-influencer or a
single influencer, where

  * •

a $k$-influencer is a vertex selected through one of the $k$-node selection
algorithms with respect to some centrality metric, and

  * •

a single influencer is the highest scoring vertex with respect to some
centrality metric.

###  III.2 Future Network Prediction

Understanding how to predict the future state of influencers is of upmost
importance when considering information spread. Through previously reviewed
literature, one is able to do the following:

  * •

predict future links of our social network, and

  * •

find the most influential $k$ nodes of a given social network.

We shall combine these and look for future influencers by first predicting the
state of the future network, like Yanchenko et al. exante  did. However, when
considering the formation of the future graph, rather than selecting the top
edge pairs, we simply take normalized similarity scores to be probabilities of
transmission and add them to the graph as weights, using expected value to
calculate the distance. Moreover, given the unit of time $t$ we are predicting
for, we can find a better predictor for the transmission probability.

Suppose the probability an edge forms between two nodes $u$ and $v$ in one
unit of time is $p_{u,v}$. Consider the analogy of a coin flip: an edge
forming between two nodes in one unit of time is equivalent to a
correspondingly weighted coin landing heads on a single flip. Thus, the
probability an interaction has occurred in those $t$ units of time is simply
the probability the coin comes up heads some time in its $t$ flips, which is
$1-(1-p_{u,v})^{t}$. Similarly, we can take the outcome of the coin flip as
whether or not two nodes become connected. Then the probability of connection,
and thus transmission of information, is simply $1-(1-p_{u,v})^{t}$, which we
take as an updated weight, enabling us to better account for time evolution.

###  III.3 Future Top-$k$ Nodes Prediction

Our algorithm for future influencer prediction (see Algorithm 8) takes a graph
and, given a target $t$ units of time in the future, predicts future
connections with a normalized similarity metric. It then applies a top-$k$
algorithm to identify potential future influencers.

Algorithm 8 Future Top-$k$ Nodes Prediction

Graph $G$, Normalized Similarity Metric $M$, Top-$k$ Algorithm $c$, $t$

For vertices $u\neq v$ with $uv\not\in E$, calculate $s^{M}_{u,v}$.

for $u,v$ such that $s^{M}_{u,v}\neq 0$ do

Add edge $uv$ to $G$ with weight $1-(1-s^{M}_{u,v})^{t}$ and distance
$\frac{1}{1-(1-s^{M}_{u,v})^{t}}$.

end for

Identify the top $k$ nodes on $G$ using $c$.

In what follows we shall first described the methods developed in order to
implement our model, give an analysis of our results, and describe some of the
applications and future directions.

##  IV Methods

In order to illustrate the different uses of our model and our algorithm, we
shall test our algorithm on both a random graph and an empirical dataset:
given a graph $G$, we form a training graph from a random subset of existing
edges of given size, predict the future state of the training graph, and
identify influencers on those predicted graphs. For each graph and parameter
tested, we repeated the process ten times, averaging the data. We modelled a
dynamic network by taking the training graph as the current configuration and
the original graph $G$ as the future network, thus allowing us to assess the
efficacy of the influencers found in terms of their ability to “infect” nodes
over time when set as the initial spreaders in $G$.

###  IV.1 Evaluation Methods

Our testing focused on two key aspects:

  * (I)

the effectiveness of the predicted influencers compared to those found in the
actual network, and

  * (II)

the success of our predictions in identifying true influencers.

To measure the effectiveness mentioned in (I), we quantify influence as the
percentage of nodes infected at each unit of time when the chosen influencers
are set as initial spreaders on $G$ and an influence model (see Section IV.2)
is run. The results are then presented visually in the form of line graphs.

From a different perspective, we describe the predictive success mentioned in
(II) as the similarity between our predicted influencers (and their influence)
and the influencers found on $G$ (the “true” influencers), quantified in two
different ways:

  1. 1.

accuracy, the fraction of chosen influencers on the predicted graph that are
also chosen by the same methods of influencer identification on the original,
and

  2. 2.

mean squared error, a function from statistics that evaluates the differences
between the influence of the influencers chosen on the predicted graphs and
the original graph; for a given prediction metric and influencer
identification algorithm, the mean squared error is

$\frac{1}{r}\sum_{i=0}^{r}(O(t)-P(t))^{2},$

where $P(t)$ is the fraction of infected nodes at time $t$ when the influence
of the influencers chosen on the predicted graph are evaluated on the original
graph and $O(t)$ is defined similarly for the original graph.

###  IV.2 Contagion Models

To account for different types of information, we evaluate influence according
to two simplified models for simple contagion and complex contagion.

Simple Contagion.  In general, simple contagion can be understood as an
“infection” of information, where an uninfected individual $j$ becomes
infected with probability $p$ once news is passed along to them from an
infected individual $i$, in a simple percolation model. For simplicity’s sake,
we shall take $p=1$ (following SRI models). Then consider our definition of
distance as the expected units of time transmission takes; with this model,
influence thus can be approximated as transmitting across each edge $uv$ in
$d(u,v)$ units of time. Thus, we can see the following:

######  Definition 30.

In a Simple Contagion model, at time $t$, the infected set $I(t)$ is defined
as follows:

$I(t)=\\{v\in V|\exists u\in I(0):D(u,v)\leq t\\}.$

Complex Contagion. Complex contagion is usually described by threshold models,
where each node is given a resistance $\theta_{v}$ and is activated according
to a function

$f:I\rightarrow[0,1]$

(see e.g. Shakarian et al. icmltm  for further details). While resistance
often varies depending on the individual, in this paper we set it to be a
fixed percentage of each vertex’s strength, as considering how perceived
plurality can lead to adoption, individuals with larger neighborhoods may have
more resistance and similarly the converse may happen.

######  Definition 31.

In a Complex Contagion model, at time $t$, the infected set $I(t)$ is defined
as follows:

$I(t)=\\{v\in V|\sum_{i\in I(t-1)}w(i,v)\geq\theta\cdot s_{v}\\},$

where $\theta\in[0,1]$ is a given threshold fraction.

###  IV.3 Experimental Setup

We tested our algorithm on an Erdös-Rényi random graph and an existing
collaboration network dataset. Erdös and Rényi erdosrenyirgraph  defined these
random graphs by taking two parameters, $n\in\mathbb{Z}$ and $p\in[0,1]$. The
graph is created with $n$ vertices, and each pair of vertices is connected by
an edge with probability $p$. We used a graph with $n=500$ and $p=0.05$. The
empirical network we used is the arXiv General Relativity and Quantum
Cosmology collaboration network from a paper by Leskovec et al. cagrqc , found
in the Stanford Large Network Dataset Collection snapnets . The network
contains $5242$ nodes and $14496$ edges. In the random graph case, we took
$k=5$ and in the arXiv dataset, we took $k=25$. Additionally, we tested the
influences of single influencers in each scenario as well.

For each of the datasets, we took two parameters: one when $90\%$ of edges are
chosen and $t=1$, and the second one when $70\%$ of the edges are chosen and
$t=3$. We are assuming that edges occur at around the same rate each unit of
time; thus, the former models influencer prediction in the near future and the
latter predicts for more distant networks.

This methodology and experimental setup pave the way for our findings, which
offer novel insights into the prediction of influencers in dynamic social
networks.

##  V Results

We shall describe here our results obtained though the methods appearing in
the previous section, with insightful findings around the efficacy of our
model in accurately predicting future influencers and analysis of the
comparative performances of various similarity measures, centrality measures,
and algorithms. We shall also break down these results and provide a clearer
understanding of our model’s capabilities and limitations below.

###  V.1 Results on a Random Graph

Thorough applications of our model to Erdö-Rényi random graphs, one can see
the following:

  * •

the average MSE for each of our algorithms is low, indicating a high
similarity to the performance of influencers chosen on the “future” graph,

  * •

the average accuracy differed depending on algorithm and Social Sphere Model
parameters, but is often quite high, and

  * •

the influence of influencers from the predicted graphs is comparable to that
of the original and often performes better than influencer identification done
on their training graphs.

Prediction Metric | Complex | Simple | Overall
---|---|---|---
Common Neighbors | 0.10224 | 9.77175E-05 | 0.05117
Jaccard | 0.10427 | 0.00011 | 0.05219
Local Path | 0.09998 | 0.00020 | 0.05009
Quasi-Local RA | 0.11917 | 0.00019 | 0.05968
Quasi-Local RA$-2$ | 0.10407 | 0.00020 | 0.052134
RA$-2$ | 0.10120 | 0.00010 | 0.05065
Resource Allocation | 0.12174 | 9.47277E-05 | 0.06092
Overall | 0.10753 | 0.00014 | 0.05383
Table 3: Average MSE over all top-$k$ algorithms for link prediction metrics using $70\%$ training graphs from a $500$-node Erdös-Rényi graph. Prediction Metric | Complex | Simple | Overall
---|---|---|---
Common Neighbors | 0.10127 | 7.30107E-05 | 0.05067
Jaccard | 0.09809 | 7.47762E-05 | 0.04908
Local Path | 0.07243 | 0.00020 | 0.03632
Quasi-Local RA | 0.07870 | 0.00020 | 0.03945
Quasi-Local RA-2 | 0.07062 | 0.00020 | 0.03541
RA-2 | 0.10448 | 7.62052E-05 | 0.05228
Resource Allocation | 0.10244 | 7.05446E-05 | 0.05126
Overall | 0.08972 | 0.00013 | 0.04492
Table 4: Average MSE over all top-$k$ algorithms for link prediction metrics using $90\%$ training graphs from a $500$-node Erdös-Rényi graph. Algorithm |  Common Neighbors |  Jaccard |  Local Path |  Quasi-Local RA |  Quasi-Local RA-2 |  RA-2 |  Resource Allocation |  Overall
---|---|---|---|---|---|---|---|---
Centrality VoteRank |  0.32 |  0.3467 |  0.3183 |  0.3567 |  0.345 |  0.345 |  0.3533 |  0.3407
Graph Coloring |  0.0167 |  0.0167 |  0.01 |  0.01 |  0.01 |  0.0167 |  0.0167 |  0.01381
Joint Nomination |  0.0117 |  0.0183 |  0.0117 |  0.0183 |  0.0133 |  0.025 |  0.0117 |  0.0157
k Highest |  0.4567 |  0.4617 |  0.4183 |  0.4267 |  0.4417 |  0.4833 |  0.465 |  0.4505
LIR |  0.2833 |  0.3267 |  0.28 |  0.3367 |  0.395 |  0.3633 |  0.3 |  0.3264
LIR-2 |  0.34 |  0.36 |  0.34 |  0.38 |  0.44 |  0.44 |  0.38 |  0.3829
Single Influencer |  0.375 |  0.3583 |  0.3583 |  0.35 |  0.3583 |  0.3667 |  0.375 |  0.3631
Random |  0 |  0 |  0.01 |  0.01 |  0.01 |  0.01 |  0.01 |  0.0071
VoteRank |  0.3231 |  0.3477 |  0.3215 |  0.3569 |  0.3446 |  0.3446 |  0.3538 |  0.3418
Overall |  0.2529 |  0.2646 |  0.2439 |  0.2634 |  0.2805 |  0.2855 |  0.2667 |  0.2654
Table 5: Average accuracy over all top-$k$ algorithms for algorithms and link prediction metrics using $70\%$ training graphs from a $500$-node Erdös-Rényi graph. Algorithm |  Common Neighbors |  Jaccard |  Local Path |  Quasi-Local RA |  Quasi-Local RA-2 |  RA-2 |  Resource Allocation |  Overall
---|---|---|---|---|---|---|---|---
Graph Coloring |  0.0233 |  0.0233 |  0.0600 |  0.0600 |  0.0600 |  0.0233 |  0.0233 |  0.0390
Joint Nomination |  0.0067 |  0.0117 |  0.0100 |  0.0133 |  0.0150 |  0.0133 |  0.0100 |  0.0114
k Highest |  0.6867 |  0.6783 |  0.5867 |  0.5833 |  0.5850 |  0.6867 |  0.6850 |  0.6417
LIR |  0.5217 |  0.5367 |  0.5067 |  0.5433 |  0.6033 |  0.6033 |  0.5483 |  0.5519
LIR-2 |  0.6400 |  0.6400 |  0.6400 |  0.6600 |  0.6600 |  0.6600 |  0.6600 |  0.6514
Single Influencer |  0.6167 |  0.6000 |  0.5583 |  0.5417 |  0.5417 |  0.6000 |  0.5917 |  0.5786
Random |  0.0000 |  0.0000 |  0.0100 |  0.0100 |  0.0100 |  0.0100 |  0.0000 |  0.0057
VoteRank |  0.6 |  0.62 |  0.5954 |  0.6354 |  0.6308 |  0.62 |  0.6277 |  0.6185
Overall |  0.4338 |  0.4361 |  0.4149 |  0.4264 |  0.4345 |  0.4497 |  0.4411 |  0.4338
Table 6: Average accuracy over all top-$k$ algorithms for algorithms and link
prediction metrics using $90\%$ training graphs from a $500$-node Erdös-Rényi
graph.

Mean Squared Error (MSE) Comparison. We averaged the MSE for all algorithms
and their parameters over each prediction metric in both scenarios tested (see
Table 3 and Table 4, where the smallest value in each column appears in bold).
In each case, the MSE was quite low, averaging around $0.11$ for complex
contagion and $0.00014$ for simple contagion. It is interesting to note that
in simple contagion, less variance was observed; this is likely due to the
deterministic structure of our simplified influence model. However, even in
the more realistic complex contagion scenario we also saw a relatively small
mean squared error in the fraction of nodes infected, implying that overall
the influence plots for the predicted graphs are quite close to that of the
future graph.

Accuracy Comparison. We averaged the accuracy for all algorithms over each
centrality metric and prediction metric in both scenarios tested (see Table 5
and Table 6, where the largest value(s) in each row appear in bold). In these
tables, we can see the overall predicting ability: the highest accuracies in
the $70\%$ scenario are around $0.5$ (implying around half of the chosen
vertices are the same on average) and are $0.7$ in the $90\%$ scenario.
Therefore one has a high accuracy in the overall selection of influencers,
meaning that our predicted graphs do not stray far from the true future graph.
In particular, notice that there are a total of $500$ vertices in the graph;
when chosen randomly there is an expected overlap of $\frac{5}{500}\cdot
5=0.05$ influencers from linearity of expectation, i.e. an accuracy of
$0.0001$.

Interestingly, there are also noticeable differences between the overall
accuracies of different algorithms. Overall, the selection of the $k$ highest-
scoring centrality metrics performed best in each scenario, with VoteRank,
LIR, LIR$-2$, and single influencer selection (taking the top scorer with
respect to each centrality metric) also performing relatively well. Graph
coloring and joint nomination do not perform well with respect to accuracy,
however, which is to be expected. For the former, note that with the addition
of our various predicted edges, the division of the graph into independent
sets was likely changed drastically, which then throws off the accuracy of the
nodes chosen in the predicted graphs, and for the latter notice that the
algorithm itself relies on a semi-random selection, meaning similar selection
of vertices is already quite unlikely. However, since we have weighted the
probability distributions when selecting for joint nomination, we do see
higher accuracy than expected.

Algorithm Comparisons. We compared both the total overall performance
differences by algorithm and their relative performances when also considering
a prediction metric.

(a) On complex contagion

(b) On simple contagion

Figure 2: Average performance of each algorithm over all graphs as fraction
infected over time using $70\%$ training graphs from a $500$-node Erdös-Rényi
graph.

(a) On complex contagion

(b) On simple contagion

Figure 3: Average performance of each algorithm over all graphs as fraction
infected over time using $90\%$ training graphs from a $500$-node Erdös-Rényi
graph.

We can see from Figure 2 and Figure 3 that LIR, LIR$-2$, and VoteRank are the
best performers overall. Surprisingly, the $k$ highest algorithm is not too
shabby either, surpassing joint nomination and graph coloring in each
scenario. Possible explanations for this is first, that the purpose of joint
nomination lies with disconnecting the graph rather than creating high
influence spread, and second, that since some predicted graphs work better
with graph coloring than others due to the aforementioned upsetting of the
colorings, its average may have been lowered. As expected, random selection
and single influencer selection (labeled as ‘None’ in the figures) perform
worst overall.

When considering different prediction metrics, we will look only at data from
the complex contagion models (see Figure 4 and Figure 5), as the simple
contagion data is very close together for each pair of algorithms and
prediction metrics, making it less interesting. In most of the graphs, we can
see that compared to ‘None,’ the training graph itself, there are a
substantial number of predicted graphs that perform consistently better
(RA$-2$ and QR$-2$, for instance). Moreover, the predicted graphs all display
influence approaching or, in 5(c), even surpassing the averages for the
original graph, suggesting an improvement in prediction when our Social Sphere
Model is used.

(a) Graph Coloring

(b) Joint Nomination

(c) $k$ Highest

(d) LIR

(e) LIR$-2$

(f) VoteRank

Figure 4: Average performance of each algorithm and prediction metric as
fraction infected over time using $70\%$ training graphs from a $500$-node
Erdös-Rényi graph.

(a) Graph Coloring

(b) Joint Nomination

(c) $k$ Highest

(d) LIR

(e) LIR$-2$

(f) VoteRank

Figure 5: Average performance of each algorithm and prediction metric as
fraction infected over time using $90\%$ training graphs from a $500$-node
Erdös-Rényi graph.

###  V.2 Results on an Empirical Dataset

The application of our algorithm to the arXiv collaboration network led to the
following conclusions:

  * •

our similarity metric RA$-2$ has the lowest average MSE overall,

  * •

the Social Sphere Model may be able to identify latent influencers who perform
even better than those in the original graph, and

  * •

there always exist parameters for our modified centrality algorithms that
perform better than the originals.

Prediction Metric | Complex | Simple | Overall
---|---|---|---
Common Neighbors | 0.02641 | 0.00557 | 0.01599
Jaccard | 0.02282 | 0.00493 | 0.01388
Local Path | 0.04713 | 0.00811 | 0.02762
Quasi-Local RA | 0.04289 | 0.00753 | 0.02521
Quasi-Local RA-2 | 0.04081 | 0.00738 | 0.02410
RA-2 | 0.02254 | 0.00635 | 0.01444
Resource Allocation | 0.02278 | 0.00543 | 0.01411
Overall | 0.03220 | 0.00647 | 0.01933
Table 7: Average MSE over all top-$k$ algorithms for link prediction metrics using $70\%$ training graphs from the arXiv GrQc dataset. Prediction Metric | Complex | Simple | Overall
---|---|---|---
Common Neighbors | 0.01914 | 0.01368 | 0.01641
Jaccard | 0.01854 | 0.01334 | 0.01594
Local Path | 0.02607 | 0.01365 | 0.01986
Quasi-Local RA | 0.02539 | 0.01392 | 0.01966
Quasi-Local RA-2 | 0.02558 | 0.01371 | 0.01965
RA-2 | 0.01804 | 0.01372 | 0.01588
Resource Allocation | 0.01846 | 0.01414 | 0.01630
Overall | 0.02160 | 0.01374 | 0.01767
Table 8: Average MSE over all top-$k$ algorithms for link prediction metrics using $90\%$ training graphs from the arXiv GrQc dataset. Centrality Metrics |  Common Neighbors |  Jaccard |  Local Path |  Quasi-local RA-2 |  Quasi-local RA |  RA-2 |  Resource Allocation |  Overall
---|---|---|---|---|---|---|---|---
Balanced Index |  0.0151 |  0.0106 |  0.0292 |  0.0260 |  0.0247 |  0.0104 |  0.0116 |  0.0182
Betweenness |  0.0110 |  0.0094 |  0.0224 |  0.0205 |  0.0194 |  0.0087 |  0.0092 |  0.0144
Closeness |  0.0170 |  0.0138 |  0.0295 |  0.0262 |  0.0249 |  0.0133 |  0.0135 |  0.0197
ClusterRank |  0.0174 |  0.0151 |  0.0301 |  0.0296 |  0.0287 |  0.0146 |  0.0149 |  0.0215
Complex Path Centrality |  0.0475 |  0.0480 |  0.0442 |  0.0434 |  0.0431 |  0.0486 |  0.0484 |  0.0462
Degree |  0.0107 |  0.0097 |  0.0229 |  0.0219 |  0.0195 |  0.0086 |  0.0084 |  0.0145
Eigenvector |  0.0109 |  0.0095 |  0.0240 |  0.0223 |  0.0212 |  0.0091 |  0.0098 |  0.0152
H-index |  0.0156 |  0.0152 |  0.0318 |  0.0282 |  0.0268 |  0.0150 |  0.0152 |  0.0211
k-core |  0.0117 |  0.0103 |  0.0222 |  0.0189 |  0.0187 |  0.0109 |  0.0107 |  0.0148
LeaderRank |  0.0108 |  0.0083 |  0.0229 |  0.0211 |  0.0196 |  0.0076 |  0.0080 |  0.0140
LocalRank |  0.0094 |  0.0080 |  0.0231 |  0.0216 |  0.0205 |  0.0077 |  0.0079 |  0.0140
PageRank |  0.0130 |  0.0087 |  0.0266 |  0.0240 |  0.0237 |  0.0099 |  0.0094 |  0.0165
Overall |  0.0158 |  0.0139 |  0.0274 |  0.0253 |  0.0242 |  0.0137 |  0.0139 |  0.0192
Table 9: Average MSE for centrality metrics over all algorithms and contagion models on $70\%$ training graphs. Centrality Metrics |  Common Neighbors |  Jaccard |  Local Path |  Quasi-local RA-2 |  Quasi-local RA |  RA-2 |  Resource Allocation |  Overall
---|---|---|---|---|---|---|---|---
Balanced Index |  0.0132 |  0.0132 |  0.0221 |  0.0221 |  0.0218 |  0.0129 |  0.0132 |  0.0169
Betweenness |  0.0114 |  0.0107 |  0.0199 |  0.0192 |  0.0198 |  0.0102 |  0.0111 |  0.0146
Closeness |  0.0123 |  0.0117 |  0.0201 |  0.0198 |  0.0197 |  0.0111 |  0.0116 |  0.0152
ClusterRank |  0.0120 |  0.0120 |  0.0206 |  0.0202 |  0.0204 |  0.0120 |  0.0118 |  0.0156
Complex Path Centrality |  0.0732 |  0.0732 |  0.0376 |  0.0374 |  0.0377 |  0.0733 |  0.0734 |  0.0580
Degree |  0.0107 |  0.0102 |  0.0172 |  0.0169 |  0.0170 |  0.0099 |  0.0101 |  0.0131
Eigenvector |  0.0077 |  0.0074 |  0.0120 |  0.0117 |  0.0116 |  0.0069 |  0.0072 |  0.0092
H-index |  0.0125 |  0.0126 |  0.0182 |  0.0179 |  0.0177 |  0.0122 |  0.0124 |  0.0148
k-core |  0.0030 |  0.0029 |  0.0048 |  0.0045 |  0.0046 |  0.0031 |  0.0029 |  0.0037
LeaderRank |  0.0115 |  0.0108 |  0.0179 |  0.0175 |  0.0181 |  0.0104 |  0.0105 |  0.0138
LocalRank |  0.0107 |  0.0109 |  0.0198 |  0.0193 |  0.0195 |  0.0103 |  0.0105 |  0.0144
PageRank |  0.0122 |  0.0116 |  0.0204 |  0.0199 |  0.0199 |  0.0113 |  0.0117 |  0.0153
Overall |  0.0159 |  0.0156 |  0.0192 |  0.0189 |  0.0190 |  0.0153 |  0.0155 |  0.0170
Table 10: Average MSE for centrality metrics over all algorithms and contagion models on $90\%$ training graphs. Centrality Metric |  Common Neighbors |  Jaccard |  Local Path |  Quasi-Local RA |  Quasi-Local RA-2 |  RA-2 |  Resource Allocation |  Overall
---|---|---|---|---|---|---|---|---
Balanced Index |  0.3217 |  0.4166 |  0.3091 |  0.3714 |  0.3691 |  0.4086 |  0.4046 |  0.3716
Betweenness |  0.3811 |  0.3903 |  0.3549 |  0.3537 |  0.3503 |  0.3937 |  0.3943 |  0.3740
Closeness |  0.2897 |  0.3371 |  0.2720 |  0.3120 |  0.3154 |  0.3463 |  0.3411 |  0.3162
ClusterRank |  0.2794 |  0.2731 |  0.2217 |  0.1891 |  0.1806 |  0.2760 |  0.2714 |  0.2416
Complex Path Centrality |  0.2171 |  0.2160 |  0.1326 |  0.1320 |  0.1343 |  0.2171 |  0.2166 |  0.1808
Degree |  0.3634 |  0.3520 |  0.3400 |  0.3211 |  0.3211 |  0.3594 |  0.3594 |  0.3452
Eigenvector |  0.2691 |  0.2154 |  0.2577 |  0.2091 |  0.2057 |  0.2240 |  0.2189 |  0.2286
H-index |  0.1846 |  0.1509 |  0.0617 |  0.0571 |  0.0560 |  0.1509 |  0.1497 |  0.1158
k-core |  0.4680 |  0.4623 |  0.4417 |  0.4394 |  0.4371 |  0.4634 |  0.4611 |  0.4533
LeaderRank |  0.3514 |  0.3491 |  0.3297 |  0.3177 |  0.3154 |  0.3560 |  0.3531 |  0.3389
LocalRank |  0.3000 |  0.2886 |  0.2200 |  0.2057 |  0.2017 |  0.2977 |  0.3000 |  0.2591
PageRank |  0.3766 |  0.3651 |  0.3503 |  0.3291 |  0.3263 |  0.3674 |  0.3674 |  0.3546
Overall |  0.3169 |  0.3180 |  0.2743 |  0.2698 |  0.2678 |  0.3217 |  0.3198 |  0.2983
Table 11: Average overall accuracies for centrality metrics on $70\%$ training graphs from the arXiv GrQc dataset. Centrality Metric |  Common Neighbors |  Jaccard |  Local Path |  Quasi-Local RA |  Quasi-Local RA-2 |  RA-2 |  Resource Allocation |  Overall
---|---|---|---|---|---|---|---|---
Balanced Index |  0.4166 |  0.4869 |  0.3989 |  0.4589 |  0.4571 |  0.4857 |  0.4851 |  0.4556
Betweenness |  0.4743 |  0.4703 |  0.4366 |  0.4343 |  0.4349 |  0.4709 |  0.4697 |  0.4558
Closeness |  0.3874 |  0.3983 |  0.3714 |  0.3857 |  0.3846 |  0.4006 |  0.4000 |  0.3897
ClusterRank |  0.2937 |  0.2743 |  0.2080 |  0.1960 |  0.1903 |  0.2743 |  0.2771 |  0.2448
Complex Path Centrality |  0.1680 |  0.1640 |  0.1560 |  0.1566 |  0.1571 |  0.1720 |  0.1680 |  0.1631
Degree |  0.4606 |  0.4206 |  0.4229 |  0.3869 |  0.3869 |  0.4223 |  0.4194 |  0.4171
Eigenvector |  0.3789 |  0.3131 |  0.3600 |  0.2977 |  0.3029 |  0.3217 |  0.3189 |  0.3276
H-index |  0.1834 |  0.1743 |  0.0863 |  0.0869 |  0.0834 |  0.1714 |  0.1726 |  0.1369
k-core |  0.5274 |  0.5217 |  0.4909 |  0.4829 |  0.4857 |  0.5211 |  0.5211 |  0.5073
LeaderRank |  0.4640 |  0.4326 |  0.4274 |  0.4006 |  0.4006 |  0.4360 |  0.4349 |  0.4280
LocalRank |  0.3280 |  0.3194 |  0.2246 |  0.2200 |  0.2183 |  0.3194 |  0.3194 |  0.2784
PageRank |  0.4851 |  0.4480 |  0.4497 |  0.4143 |  0.4177 |  0.4509 |  0.4486 |  0.4449
Overall |  0.3806 |  0.3686 |  0.3360 |  0.3267 |  0.3266 |  0.3705 |  0.3696 |  0.3541
Table 12: Average overall accuracies for centrality metrics on $90\%$ training
graphs from the arXiv GrQc dataset.

Mean Squared Error Comparison. Considering Table 9 and Table 10, one can see
that the mean squared error of the percentage infected is still small, though
substantially larger than before, likely due to the larger variation that
comes with more vertices and a larger graph. Notably, our new link prediction
metric has the smallest average MSE over all the prediction metrics in both
scenarios, with it also being the smallest in $75\%$ of the metrics in Table
10; we also see a similar trend in Table 11 and Table 12, where our new metric
has the highest fraction in the $70\%$ case and the second highest in the
$90\%$ scenario. These results support our hypotheses, as there is a
significant decrease in MSE in the $90\%$ scenario as opposed to the $70\%$
one, this indicating that our link prediction metrics can identify influencers
with very similar influence to that of the original, thus effectively showing
prediction.

Accuracy Comparison.  When one compares the two scenarios described in Table
11 and Table 12, one can see more variation in the influencers chosen in the
second scenario due to less information; in the $90\%$ case, the graph is
already very similar to the final configuration and link prediction is more
accurate, whereas predictions may be less grounded for the latter case. For
more specific data, see Appendix A.

(a) On complex contagion

(b) On simple contagion

Figure 6: Average performance of each algorithm over all graphs as fraction
infected over time using $70\%$ training graphs from the arXiv GrQc dataset.

(a) On complex contagion

(b) On simple contagion

Figure 7: Average performance of each algorithm over all graphs as fraction
infected over time using $90\%$ training graphs from the arXiv GrQc dataset.

Influence Comparison. In what follows, we shall consider the relative
influences of influencers selected by the following methods:

  1. 1.

the algorithms,

  2. 2.

the various prediction metrics when controlling for algorithm, and

  3. 3.

the various centrality metrics when controlling for algorithm.

We have mapped out the average performances of the various algorithms in
Figure 6 and Figure 7. Notice that, as in the random graph case, VoteRank
performs admirably in both simple and complex contagion in each scenario.
Intriguingly, the $k$ highest algorithm also seems to do well, particularly in
complex contagion. Unlike in Section V.1, LIR and LIR$-2$ exhibit sub-optimal
efficiency and have effectively swapped with graph coloring and joint
nomination. A possible explanation for this observation is the difference in
structure of the empirical dataset and the Erdös-Rényi random graph. For
instance, the empirical dataset is not fully connected (and it is thus
impossible for the fraction infected to be $1$, as there are too many
disconnected pieces).

(a) Graph Coloring

(b) Joint Nomination

(c) $k$ Highest

(d) LIR

(e) LIR$-2$

(f) VoteRank

Figure 8: Average performance of each algorithm and prediction metric as
fraction infected over time using $70\%$ training graphs from the arXiv GrQc
dataset in complex contagion.

(a) Graph Coloring

(b) Joint Nomination

(c) $k$ Highest

(d) LIR

(e) LIR$-2$

(f) VoteRank

Figure 9: Average performance of each algorithm and prediction metric as
fraction infected over time using $70\%$ training graphs from the arXiv GrQc
dataset in simple contagion.

When one controls for algorithm and investigate the average influences of the
various prediction metrics (see Figure 8 and Figure 9), we can see that

  * •

in most cases the respective influence plots of the original graph and the
various predicted graphs are very close, and

  * •

influencers found on the predicted graphs are often able to spread their
influence to more of the population.

The first observation entails that the Social Sphere Model is able to produce
results comparable with influence identification on the original graph. To
elaborate on the second, scenarios such as in 8(a), 8(d), and 9(e) depict the
influence plots of predicted graphs as eventually plateauing to values above
those of the original graph (and the training graph). This suggests that link
predicted graphs may sometimes be able to find latent influencers, those that
were influential in the past but overlooked in the current graph.

One should note that Xie et al. dynamicedgedecay  have previously explained
the drawbacks to having a model that only considers a small window of the
graph’s historical data: a powerful influencer who is perhaps temporarily
inactive may be overlooked in favor of a currently active, less influential
individual. Importantly, our Social Sphere Model thus also presents an
incorporation of historical data in finding influencers.

Finally, our analysis of the effectiveness of our modifications to the various
algorithms showed that for VoteRank, there exist centrality VoteRank metrics
whose averages in accuracy or MSE over all the predicted graphs match or
surpass VoteRank’s performance in both the $70\%$ and $90\%$ scenarios, namely
closeness, complex path, H-index, $k$-core, and LocalRank in the $70\%$ graph
and Balanced Index and LeaderRank in the $90\%$ graph.

When comparing the relative influence of the nodes chosen with VoteRank over
the various link prediction metrics, the above is also true (see Figure 10,
Figure 11, and Appendix A); in particular, betweenness is shown to be one of
the best performing metrics in each scenario (None refers to VoteRank) and
closeness and complex path centrality also often do almost as well. This is
likely because our contagion models are deterministic and are concerned with
the distances between vertices, which the three mentioned metrics, being path-
based, are geared to do. Similar observations hold for LIR and LIR$-2$.

(a) Original Graph

(b) Common Neighbors Predicted Graph

(c) deg2 RA Predicted Graph

(d) Jaccard Predicted Graph

(e) Local Path Predicted Graph

(f) Quasi-Local deg2 ra Predicted Graph

(g) Quasi-Local RA Predicted Graph

(h) Resource Allocation Predicted Graph

Figure 10: Performance of influencers chosen with Centrality VoteRank (the
original VoteRank is labelled as None) on predicted graphs formed from $70\%$
training graphs from the arXiv GrQc dataset in complex contagion.

(a) Original Graph

(b) Common Neighbors Predicted Graph

(c) Jaccard Predicted Graph

(d) Local Path Predicted Graph

(e) Quasi-Local RA Predicted Graph

(f) Quasi-Local RA-2 Predicted Graph

(g) RA-2 Predicted Graph

(h) Resource Allocation Predicted Graph

Figure 11: Performance of influencers chosen with Centrality VoteRank (the
original VoteRank is labelled as None) on predicted graphs formed from $70\%$
training graphs from the arXiv GrQc dataset in simple contagion.

##  VI Conclusion

In this research, we introduced the Social Sphere Model, a novel algorithm
which utilizes heuristic link prediction and influencer identification to
forecast future influencers in weighted networks. Our comprehensive analyses
on both a random graph and a real world scenario (through the arXiv
collaboration network) have demonstrated the algorithm’s efficacy,
particularly evident in the low mean squared error and relatively high
accuracy, suggesting the Social Sphere Model’s promising prediction
capabilities for detecting future influencers, which is similar to Yanchenko
et al. exante ’s findings that the influence of their model’s selected nodes
were comparable to that of the Oracle method.

By modifying and extending several existing influencer identification
algorithms to incorporate centrality metrics, we found that the modified forms
of VoteRank were comparable to the original form of VoteRank when using
metrics such as betweenness. Our proposed similarity metric, RA-$2$,
particularly excelled in both mean squared error and accuracy for the $90\%$
graphs. Moreover, our analysis of different link prediction metrics differing
mostly in the degree of their denominators poses interesting questions around
the optimal metric when applying the Social Sphere Model for different graphs
and parameters.

The practical applications of our algorithm span a wide array of fields from
marketing to epidemiology, offering valuable insights for strategic planning
and information control. These include:

  * •

Viral marketing: in the scenario mentioned in Section I, taking our algorithm
over existing social media data and estimating $t$ from the expected time for
production can assist in identifying potential future influencers in the
network, giving more time (a valuable commodity) for negotiation, scouting,
and strategizing. The relatively short time complexities of heuristic models
are also sometimes valuable in these scenarios. As an analogy, if one wanted
to understand how admissions would look like in a university program for
influencers, our algorithm would allow one to evaluate the potential of an
influencer or group of influencers in the wider network.

  * •

Better Network Approximation: The already-documented crimeprediction  utility
of link prediction in approximating incomplete network data further
underscores the significance of our approach, especially considering the
typically resource-intensive nature of complete data collection.

  * •

Historical Consideration: Our results show potential in identifying hidden or
overlooked influencers, which presents a dynamic aspect that can enhance
performance and integrate more information in the search for influencers.

In particular, our model differentiates from other ones by making use of
relatively low time complexity metrics and algorithms as opposed to neural
networks, the training of which may be infeasible for smaller businesses that
might seek to calculate future influencers. The simplicity and efficiency of
it can thus allow for quick identification of influencers and thus better
networking.

Since our model is inspired by a deterministic simple contagion model, which
restricts the differentiation in algorithm performance, we present here an
interesting future research path to explore more realistic contagion models
and extend the Social Sphere Model further.

Finally, it would be of much interest to study the implications of the Social
Sphere Model more graph theoretically on different network types: in
particular, towards identifying the most effective combinations of link
prediction and influencer identification metrics for specific network types,
such as temporal or directed networks, varying empirical dataset origins, and
properties like varying clustering coefficient or diameter values.

Acknowledgments. We extend our gratitude to the MIT PRIMES-USA program for
their invaluable support and guidance throughout this research. The research
of LPS is partially supported by NSF FRG Award DMS- 2152107, a Simons
Fellowship and NSF CAREER Award DMS 1749013. Part of the work appearing here
was done whilst LPS was a Visiting Fellow at All Souls College, Oxford.

Affiliations.

  1. (a)

University of Illinois at Chicago, Chicago, IL 60607, USA.

  2. (b)

Lakeside High School, Seattle, WA 98107.

## References

  * [1] Degree centrality.  https://docs.tigergraph.com/graph-ml/current/centrality-algorithms/degree-centrality.
  * [2] Pagerank.  https://docs.tigergraph.com/graph-ml/current/centrality-algorithms/pagerank#:~:text=This%20algorithm%20has%20a%20time,the%20time%20needed%20for%20computation.
  * [3] Ansam Ali AbdulAmeer, Muhammed Abaid Mahdi, and Mahdi Abed Salman.  Detection of influencers in social networks: A survey.  Journal of Kufa for Mathematics and Computer, 10(1):18–26, 2023\.
  * [4] Furqan Aziz, Haji Gul, M. Irfan Uddin, and Georgios Gkoutos.  Path-based extensions of local link prediction methods for complex networks.  Scientific Reports, 10, 11 2020.
  * [5] Meng Bai, Ke Hu, and Yi Tang.  Link prediction based on a semi-local similarity index.  Chinese Physics B, 20(12):128902, dec 2011.
  * [6] V. Batagelj and M. Zaversnik.  An o(m) algorithm for cores decomposition of networks, 2003.
  * [7] Alex Bavelas.  Communication Patterns in Task-Oriented Groups.  Acoustical Society of America Journal, 22(6):725, January 1950.
  * [8] Giulia Berlusconi, Francesco Calderoni, Nicola Parolini, Marco Verani, and Carlo Piccardi.  Link prediction in criminal networks: A tool for criminal intelligence analysis.  PloS one, 11:e0154244, 04 2016.
  * [9] Ulrik Brandes.  A faster algorithm for betweenness centrality.  The Journal of Mathematical Sociology, 25, 03 2004.
  * [10] Sergey Brin and Lawrence Page.  The anatomy of a large-scale hypertextual web search engine.  Computer Networks and ISDN Systems, 30(1):107–117, 1998.  Proceedings of the Seventh International World Wide Web Conference.
  * [11] Ellsworth Campbell and Marcel Salathé.  Complex social contagion makes networks more vulnerable to disease outbreaks, 2012.
  * [12] Damon Centola.  Change.  Little, Brown and Company, 2021.
  * [13] Damon Centola and Michael Macy.  Complex contagions and the weakness of long ties.  American Journal of Sociology, 113(3):702–734, 2007.
  * [14] Duanbing Chen, Hui Gao, Linyuan Lü, and Tao Zhou.  Identifying influential nodes in large-scale directed networks: The role of clustering.  PloS one, 8:e77455, 10 2013.
  * [15] Duanbing Chen, Linyuan Lü, Ming-Sheng Shang, Yi-Cheng Zhang, and Tao Zhou.  Identifying influential nodes in complex networks.  Physica A: Statistical Mechanics and its Applications, 391(4):1777–1787, 2012.
  * [16] Pedro M. Domingos and Matthew Richardson.  Mining the network value of customers.  In Knowledge Discovery and Data Mining, 2001.
  * [17] Zhihao Dong, Yuanzhu Chen, Terrence Tricco, Cheng Li, and Ting Hu.  Hunting for vital nodes in complex networks using local information.  Scientific Reports, 11, 04 2021.
  * [18] Marius Eidsaa and Eivind Almaas.  $s$-core network decomposition: A generalization of $k$-core analysis to weighted networks.  Phys. Rev. E, 88:062819, Dec 2013.
  * [19] Paul L. Erdos and Alfréd Rényi.  On the evolution of random graphs.  Transactions of the American Mathematical Society, 286:257–257, 1984.
  * [20] Michael L. Fredman and Robert Endre Tarjan.  Fibonacci heaps and their uses in improved network optimization algorithms.  In JACM, 1984.
  * [21] Linton Freeman.  A set of measures of centrality based on betweenness.  Sociometry, 40:35–41, 03 1977.
  * [22] Linton C. Freeman.  Centrality in social networks conceptual clarification.  Social Networks, 1:215–239, 1978.
  * [23] Saeid Ghafouri and Seyed Hossein Khasteh.  Influence maximization under partially observable environments.  In 2019 27th Iranian Conference on Electrical Engineering (ICEE), pages 1984–1988, 2019.
  * [24] Amit Goyal, Francesco Bonchi, and Laks Lakshmanan.  Learning influence probabilities in social networks.  volume 241-250, pages 241–250, 02 2010.
  * [25] Douglas Guilbeault and Damon Centola.  Topological measures for identifying and predicting the spread of complex contagions.  Nature Communications, 12, 07 2021.
  * [26] Mohammad Hasan and Mohammed Zaki.  A Survey of Link Prediction in Social Networks, pages 243–275.  03 2011.
  * [27] J. E. Hirsch.  An index to quantify an individual’s scientific research output.  Proceedings of the National Academy of Sciences, 102(46):16569–16572, November 2005.
  * [28] Yanqing Hu, Shenggong Ji, Yuliang Jin, Ling Feng, H. Eugene Stanley, and Shlomo Havlin.  Local structure can identify and quantify influential global spreaders in large scale social networks.  Proceedings of the National Academy of Sciences, 115(29):7468–7472, jul 2018.
  * [29] P. D. Karampourniotis, B. K. Szymanski, and G. Korniss.  Influence maximization for fixed heterogeneous thresholds.  Scientific Reports, 9(1), apr 2019.
  * [30] David Kempe, Jon Kleinberg, and Éva Tardos.  Maximizing the spread of influence through a social network.  In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’03, page 137–146, New York, NY, USA, 2003. Association for Computing Machinery.
  * [31] Maksim Kitsak, Lazaros Gallos, Shlomo Havlin, Fredrik Liljeros, Lev Muchnik, H. Stanley, and Hernan Makse.  Identification of influential spreaders in complex networks.  Nature Physics, 6, 01 2010.
  * [32] Sanjay Kumar and Bishwajit Panda.  Identifying influential nodes in social networks: Neighborhood coreness based voting approach.  Physma A: Statistical Mechanics and its Applications, 553:124215, 01 2020.
  * [33] E. Landau.  Über Preisverteilung bei Spielturnieren.  Teubner, 1914.
  * [34] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos.  Graph evolution: Densification and shrinking diameters.  ACM Trans. Knowl. Discov. Data, 1(1):2–es, mar 2007.
  * [35] Jure Leskovec and Andrej Krevl.  SNAP Datasets: Stanford large network dataset collection.  http://snap.stanford.edu/data, 2014.
  * [36] Yaxiong Li, Xinzhi Yang, Xinwei Zhang, Mingyuan Xi, and Xiaochang Lai.  An improved voterank algorithm to identifying a set of influential spreaders in complex networks.  Frontiers in Physics, 10, 08 2022.
  * [37] David Liben-Nowell and Jon Kleinberg.  The link prediction problem for social networks.  In Proceedings of the Twelfth International Conference on Information and Knowledge Management, CIKM ’03, page 556–559, New York, NY, USA, 2003. Association for Computing Machinery.
  * [38] Dong Liu, Yun Jing, Jing Zhao, Wenjun Wang, and Guojie Song.  A fast and efficient algorithm for mining top-k nodes in complex networks.  Scientific Reports, 7:43330, 02 2017.
  * [39] Jun Liu, Qingyu Xiong, Weiren Shi, Xin Shi, and Kai Wang.  Evaluating the importance of nodes in complex networks.  Physica A: Statistical Mechanics and its Applications, 452:209–219, 2016.
  * [40] Qiang Liu, Yu-Xiao Zhu, Yan Jia, Lu Deng, Bin Zhou, Jun-Xing Zhu, and Peng Zou.  Leveraging local h-index to identify and rank influential spreaders in networks.  Physica A: Statistical Mechanics and its Applications, 512:379–391, dec 2018.
  * [41] Linyuan Lu and Tao Zhou.  Role of weak ties in link prediction of complex networks, 2009.
  * [42] Linyuan Lü, Duanbing Chen, Xiao-Long Ren, Qian-Ming Zhang, Yi-Cheng Zhang, and Tao Zhou.  Vital nodes identification in complex networks.  Physics Reports, 650:1–63, sep 2016.
  * [43] Linyuan Lü, Yi-Cheng Zhang, Chi Ho Yeung, and Tao Zhou.  Leaders in social networks, the delicious case.  PloS one, 6:e21202, 12 2011.
  * [44] Linyuan Lü and Tao Zhou.  Link prediction in complex networks: A survey.  Physica A: Statistical Mechanics and its Applications, 390(6):1150–1170, mar 2011.
  * [45] Linyuan Lü, Tao Zhou, Qian-Ming Zhang, and H. Stanley.  The h-index of a network node and its relation to degree and coreness.  Nature Communications, 7:10168, 01 2016.
  * [46] Byungjoon Min and Maxi Miguel.  Competing contagion processes: Complex contagion triggered by simple contagion.  Scientific Reports, 8, 07 2018.
  * [47] Tsuyoshi Murata and Sakiko Moriyasu.  Link prediction of social networks based on weighted proximity measures.  volume 85-88, pages 85–88, 12 2007.
  * [48] M. Newman.  Newman, m.e.j.: Clustering and preferential attachment in growing networks. phys. rev. e 64, 025102.  Physical review. E, Statistical, nonlinear, and soft matter physics, 64:025102, 09 2001.
  * [49] Daniele Notarmuzi, Claudio Castellano, Alessandro Flammini, Dario Mazzilli, and Filippo Radicchi.  Universality, criticality and complexity of information propagation in social media.  Nature Communications, 13(1), mar 2022.
  * [50] Sen Pei, Jiannan Wang, Flaviano Morone, and Hernán A Makse.  Influencer identification in dynamical complex systems.  Journal of Complex Networks, 8(2):cnz029, 08 2019.
  * [51] Thomas Schank and Dorothea Wagner.  Approximating clustering coefficient and transitivity.  J. Graph Algorithms Appl., 9:265–275, 2005.
  * [52] Stephen Seidman.  Network structure and minimum degree.soc netw 5:269-287.  Social Networks, 5:269–287, 09 1983.
  * [53] Congzhou M Sha and Nikolay V Dokholyan.  Simple exponential acceleration of the power iteration algorithm, 2021\.
  * [54] Paulo Shakarian, Abhinav Bhatnagar, Ashkan Aleali, Elham Shaabani, and Ruocheng Guo.  The Independent Cascade and Linear Threshold Models, pages 35–48.  01 2015.
  * [55] Ashwini Kumar Singh and Lakshmanan Kailasam.  Link prediction-based influence maximization in online social networks.  Neurocomputing, 453:151–163, 2021.
  * [56] Hong-Liang Sun, Duanbing Chen, Jialin He, and Eugene Ch’ng.  A voting approach to uncover multiple influential spreaders on weighted networks.  Physica A: Statistical Mechanics and its Applications, 519, 12 2018\.
  * [57] Li Tao, Mutong Liu, Zili Zhang, and Liang Luo.  Identifying multiple influential spreaders in complex networks by considering the dispersion of nodes.  Frontiers in Physics, 9, 01 2022.
  * [58] Zelin Wan, Yash Mahajan, Beom Woo Kang, Terrence J. Moore, and Jin-Hee Cho.  A survey on centrality metrics and their network resilience analysis.  IEEE Access, 9:104773–104819, 2021.
  * [59] Sebastian Wandelt, Xing Shi, and Xiaoqian Sun.  Complex network metrics: Can deep learning keep up with tailor-made reference algorithms?  IEEE Access, 8:68114–68123, 2020.
  * [60] Duncan J. Watts, Peter Sheridan Dodds, John Deighton served as editor, and Tulin Erdem served as associate editor for this article.  Influentials, networks, and public opinion formation.  Journal of Consumer Research, 34(4):441–458, 2007.
  * [61] Duncan J. Watts and Steven H. Strogatz.  Collective dynamics of ‘small-world’ networks.  Nature, 393:440–442, 1998.
  * [62] Lilian Weng, Filippo Menczer, and Yong-Yeol Ahn.  Virality prediction and community structure in social networks.  Scientific Reports, 3(1), aug 2013.
  * [63] Wenlei Xie, Yuanyuan Tian, Yannis Sismanis, Andrey Balmin, and Peter Haas.  Dynamic interaction graphs with probabilistic edge decay.  volume 2015, 05 2015.
  * [64] Wenpu Xing and Ali A. Ghorbani.  Weighted pagerank algorithm.  Proceedings. Second Annual Conference on Communication Networks and Services Research, 2004., pages 305–314, 2004.
  * [65] Eric Yanchenko, Tsuyoshi Murata, and Petter Holme.  Link prediction for ex ante influence maximization on temporal networks, 2023.
  * [66] Jian-Xiong Zhang, Duan-Bing Chen, Qiang Dong, and Zhi-Dan Zhao.  Identifying a set of influential spreaders in complex networks, 2016.
  * [67] Star Zhao, Ronald Rousseau, and Fred Ye.  H-degree as a basic measure in weighted networks.  J. Informetrics, 5:668–677, 10 2011.
  * [68] Xiang-Yu Zhao, Bin Huang, Ming Tang, Hai-Feng Zhang, and Duanbing Chen.  Identifying effective multiple spreaders by coloring complex networks.  EPL (Europhysics Letters), 108, 10 2014.
  * [69] Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang.  Predicting missing links via local information.  The European Physical Journal B, 71(4):623–630, oct 2009.

##  Appendix A More Data

Figure 12: Average of accuracies for different algorithms on $70\%$ training
graphs for the Erdös-Rényi random graph. Figure 13: Average accuracies for
different algorithms on $90\%$ training graphs for the Erdös-Rényi random
graph. Figure 14: Average accuracies for different algorithms on $70\%$
training graphs from the arXiv GrQc dataset. Figure 15: Average accuracies for
different algorithms on $90\%$ training graphs from the arXiv GrQc dataset.

A complete set of simulation data, csv files, and line plots can be found at
https://drive.google.com/drive/folders/1WyuwbMddzajawt4nfh7rLrztY99zO6sm?usp=sharing.