=Paper=
{{Paper
|id=Vol-2400/paper-33
|storemode=property
|title=Querying Influence Graphs over Online Social Networks Effectively and Efficiently
|pdfUrl=https://ceur-ws.org/Vol-2400/paper-33.pdf
|volume=Vol-2400
|authors=Vincenzo Moscato,Antonio Picariello,Giancarlo Sperlì,Alfredo Cuzzocrea
|dblpUrl=https://dblp.org/rec/conf/sebd/0001PSC19
}}
==Querying Influence Graphs over Online Social Networks Effectively and Efficiently==
https://ceur-ws.org/Vol-2400/paper-33.pdf
Querying Influence Graphs over Online Social
Networks Effectively and Efficiently
(Discussion Paper)
Vincenzo Moscato1 , Antonio Picariello1 , Giancarlo Sperlı́1 , and Alfredo
Cuzzocrea2
1
DIETI Dept., University of Naples “Federico II”, Naples, Italy
{vincenzo.moscato,antonio.picariello,giancarlo.sperli}@unina.it
2
DIA Dept., University of Trieste, Trieste, Italy
alfredo.cuzzocrea@dia.units.it
Abstract. From the Social Networks Analysis (SNA) perspective, Viral
Marketing has the aim to maximize the number of people that become
aware of a given product/service by identifying a few number of indi-
viduals, considered more “influential” that can be promoted products or
services. In this paper we propose a novel concept of influence graph that
can be easily derived by querying social network modelled as a graph.
Furthermore, spread diffusion model has been defined as a Combinatorial
Multi-Armed Bandit (CMAB) problem for retrieving the most influential
users, without any kind of preliminary knowledge.
Keywords: Social Networks Analytics · Viral Marketing · Influence Diffusion
and Maximization · Online Social Networks Models
1 Introduction
The use of Online Social Networks or OSNs have rapidly become an essential
part of every day life, and today about 2 billions of users are connected on simple
smart platforms, where single people or communities of people share personal
information, feelings, opinions about their life or on public facts [1, 5], and, of
course, such environments represent a novel channel for assessing, choosing and
buying goods and services .
Sociologists find out that individuals are frequently, explicitly or implicitly,
influenced by their social contacts while deciding whether to adopt an innovation
(such as a political idea, or to buy a new product): the way in which new practices
spread through a population should so mainly depend on the fact that people
influence each others’ behavior.
Copyright c 2019 for the individual papers by the papers authors. Copying per-
mitted for private and academic purposes. This volume is published and copyrighted
by its editors. SEBD 2019, June 16-19, 2019, Castiglione della Pescaia, Italy.
It appears really important for big companies to target “opinion leaders”,
because if they are able to influence users of a community, it will start a large
cascade of further recommendations. One of the main problems here is to maxi-
mize the number of people that become aware of a given product, finding the best
set of users to start the diffusion and, consequently, to maximize the spread: this
is, for example, the basic idea behind each social advertisement campaigns, and
it corresponds to solve an Influence Maximization (IM) problem, which has the
goal to find a small subset of nodes that could maximize the spread of influence
over a social network graph.
An application of this strategy in social advertising is surely the so-called
Viral Marketing. Viral Marketing allows to improve the spread awareness about
a given product/service through a sort of “word-of-mouth” advertising. In a nut-
shell, a company selects a fixed (small) number of individuals, considered more
influential, and offers or discounts them the product/services, hoping that they
will be recursively recommended: as in epidemic diffusion, the viral effect starts
and new products can reach a large number of people. In this way, users will
influence their neighbors/friends triggering a “cascade effect”. Viral marketing
thus capitalizes on the advantages of social networks, and in particular their
high capacity of fast and effective information diffusion. In this paper, we pro-
pose a novel approach for viral marketing based on modeling OSNs as a graph
database. Using regular path queries, we can then query the database and extract
relevant “social paths”, by which users influence the other ones, considering a
number of different social interactions. Relevant social paths are thus oppor-
tunely merged into an influence graph that describes the influence spread over
a social network, following the Independent Cascade (IC) model. Finally, we
exploit a particular online learning problem, namely the Combinatorial Multi-
Armed Bandit (CMAB) framework, to determine the most influential users. The
chosen approach allows us to automatically estimate the influence probabilities
during the influence maximization stage, without any preliminary knowledge.
2 OSN modeling
Our idea consists in modeling a generic OSN as a graph database that is an
undirected edge-labeled graph G = (V, L, E) where:
– V is the set of graph vertices, representing the main entities of a social
network;
– L is a set of labels, usually belonging to a given vocabulary and describing
the different kinds of relationships that can occur among the social network
entities;
– E ⊆ V × L × V is the set of edges;
– V and E are abstract data types with a set of properties (expressed using sev-
eral attributes that can be different depending on the type of nodes/edges).
To better explain the proposed approach, we consider a case study based
on YELP social network. YELP is an On-line Social Network in which users
can build friendship relationships and submit reviews about business objects,
described by a set of attributes (i.e. business hour, accessibility and parking
and so on), across all industries. Furthermore, an evaluation metrics based on
a 5-point rating is assigned to both entities for estimating their relevance with
respect to their reviews and actions on YELP.
Considering our model, we can represent Yelp as a graph in which the vertices
set is composed by Users and Business objects while friendship and reviews
represent respectively the relationships between two users or a user and business
object. Furthermore, vertices and edges can be described by a set of attributes.
Using this general model we have defined a methodology to analyze users’
behavior, proposing the novel concepts of “social path”.
A social path is a particular edge-labeled path, i.e. a sequence p = (v1 , l1 , v2 , . . . , lk , vk+1 )
with (vi , li , vi+1 ) ∈ E for each i ∈ {1, , k}.
Given the graph in Figure 1, examples of social paths connecting two users be-
longing to YELP are: p1 = (vinni, f riendship, giank) and p2 = (vinni, review, gamberorosso, review, giank).
Fig. 1: An example of OSN graph using YELP data.
From a social paths, we can derive relevant social paths, i.e. special social
paths that may be used in a variety of Social Networks Analytics applications.
The elements belonging to a relevant social path must match a set of conditions
Θ, defined on the attributes of nodes and edges belonging to the path.
For example, in YELP, the paths p1 and p2 can be relevant for an influence
analysis problem and represent different ways by which a user can “influence”
another one.
We explicitly note that a relevant social path can be expressed by regular
path queries on a graph database [4]. A regular path query (RPQ) over the set
of edge labels L is expressed as a regular expression over L. 3 In other terms,
RPQs have the form Q(x, y) : (x, R, y), R being a regular expression over the
vocabulary of edge labels.
To extract the set of nodes’ pairs connected by relevant social paths, we can
first exploit regular path queries and then filtering the obtained results on the
base of Θ conditions.
As an example, the query Q(ui , uj ) : (ui , review, review, uj ) returns the set
of users pairs that have performed a review on the same business object, and in
particular, it can be represented using the graph in Figure 2.
Fig. 2: An example of graph generated using RPQs on YELP.
Exploiting as further condition Θ = (e2 .t − e1 .t) ≤ δt ∧ (e1 .m = e2 .m) (m
and t respectively being the mood and timestamp of a given review), we can
select only the set of users pairs in which the user uj has performed a review
immediately after ui with the same mood.
3 Influence analysis: building an Influence Graph from
an OSN
We can express more complex social paths using conjunctive RPQs [4]. As an
example, the query Q(ui , uj ) : (ui , review, review, uj ) ∧ (ui , f riendship, uj ) re-
turns the set of users pairs that have performed a review on the same business
object and are friends.
We define influential paths all the social paths that are relevant for an in-
fluence analysis problem. The execution of specific RPQS describing influential
paths on the database graph (representing a particular social network) allows
to determine a new homogeneous graph (vertices are only users), that we call
“influence graph”, we used to effectively model the influence spread over an
OSN.
More precisely, an Influence Graph is a labeled graph IG = (V̂ , E, b τ ) where:
3
The answer Q(D) to a RPQ Q over a database D is the set of pairs of nodes
connected in D by a social path traversing a sequence of edges forming a word in the
regular language L(Q) defined by Q.
– V̂ is the set of nodes such that each v ∈ Vb corresponds to a user u ∈ U ;
– Ê ⊆ V̂ × V̂ is the set of edge (with no self-loops);
– τ : V̂ × V̂ → [0, 1] is a function that assigns to each edge e = (vi , vj ) a label,
representing the probability τ that user ui can influence user uj .
To build an influence graph, we used a sentiment analysis technique to as-
sociate a predefined mood to each YELP review whilst we initially decided to
exploit only the influence graph structure/topology, without considering the in-
fluence probabilities. In particular, we adopted a Combinatorial Multi-Armed
Bandit (CMAB) approach [6] that allows us to automatically estimate the influ-
ence probabilities during the influence maximization stage. More in detail, the
CMAB approach consists of multiple rounds, in each of them we leverage an IM
method. Considering that we start without the knowledge of influence probabil-
ities, the obtained spread will be low compared to the optimal solution and we
refer to such situation as a regret. At each step, we then attempt to reduce the
regret and, at the same time, to improve influence probabilities estimation using
an exploration-exploitation trade-off.
In particular, the regret ρ after n rounds can be described by the Equation 1:
it practically represents the difference between spread σ related to the optimal
seed set S ∗ (knowing the right probabilities) and that returned by the CMAB
strategy applied to current seed set S i at iteration i.
n
X
ρ = n · σ(S ∗ ) − σ̄(S i ) (1)
i=1
Indeed, CMAB is based on the following exploration-exploitation trade-off:
– exploration allows us to improve our knowledge, incrementally learning the
influence probabilities over the network;
– exploitation allows us to achieve the largest spread by exploiting the current
knowledge.
3.1 Modeling Influence maximization as CMAB problem
In our model, we consider m arms each one with a random variable Xji ∈ [0, 1]
having µj as mean, which represents the obtained reward when the arm j is
triggered at the round i. Furthermore, in the CMAB model it is possible to play
a superarm A in each round: in this way all arms in A are triggered. We indicate
with pAj the probability of arm j to be triggered when superarm A is played.
At each round, we then adopt an approximation oracle that leverages the
current means’ distribution µ̂ = (µ̂1 , µ̂2 , ..., µ̂m ) to find the best (super)arm
to play. After that, the superarm is played and consequently several arms are
triggered. In the end, we observe the rewards obtained from each arm to update
their mean estimation µ̂j . To this goal, we use the number of times nj,i that an
arm j has been triggered until the round i and the process continues until i = n.
In other terms, the CMAB relies on the Independent Cascade (IC) diffusion
model that mimics the spread of an epidemic disease, evolving along discrete
steps.
b τ ) , where at each edge (u, v) ∈ E
Given an influence graph IG = (V̂ , E, b is
assigned a influence probability τu,v ∈ [0, 1], the process starts with an initial
set of active nodes S0 and each node u ∈ S0 has a single chance to activate
each outgoing inactive node v: it happens with probability τu,v . The node v can
become active in the next step and attempt to influence each one of its inactive
out-neighbors. In this way the cascade continues until the process converges; the
final spread σ(Sn ) represents the number of nodes that are activated starting
from S0 after n iterations. Thus, IM tries to maximize the final spread using
reduced seed sets.
3.2 The IM algorithm
The procedure receives as input an influence graph IG without the knowledge of
influence probabilities τ . In the initial step, it is used the vector µ̂0 that assigns
0 or a low influence probability to each edge (u, v).
At each round, the algorithm attempts to reduce the regret by implementing
a particular exploration-exploitation trade-off technique (coin flip):
– the exploitation is performed using as approximation oracle the very simple
and efficient greedy strategy proposed by the authors in [2, 3] that allows to
select a seed set S (with |S| = k) representing the played superarm A (it
requires to solve an IM problem on the graph IG with influence probability
estimating through the current means’ vector µ̂);
– the exploration is obtained generating a seed set S in a random way.
When a superarm is played, the diffusion process starts and leads to active
several inactive nodes by triggering other arms. At the end of the process, it is
evaluated the reward considering the number of nodes that are activated. This
information is the used to update the means’ estimation µ̂ by the following
Equation:
Pz
nj,i
µ̂j = i=1 (2)
z
nj,i being the number of activated nodes playing the arm j at step i and z ∈ [1, n].
Thus, we improve the knowledge to minimize the regret in the next step.
4 System Overview and Implementation Details
Here, we present an overview of the system for viral marketing purposes, whose
main components together with the related workflow are shown in Figure 3.
The system relies on a multilayer architecture typical of Big Data infras-
tructures based on the Apache Hadoop4 technological stack and supports four
main tasks: i) data ingestion, ii) data storing, iii) batch computation, iv) data
visualization.
During the data ingestion, and using the functionalities provided by an ETL
module, information about users’ social interactions are:
4
http://hadoop.apache.org/
Sentiment
Analyzer
Staging Area Influence
Maximization Dashboard
ETL KB
Query Engine
Influence Graph
RPQS
OSN
Graph Builder
DATA INGEST DATA STORING BACH PROCESSING DATA VISUALIZATION
Fig. 3: System Architecture.
– periodically extracted from several OSNs (e.g., YELP, TripAdvisor, etc.)
using the related API;
– cleaned and transformed in according to a particular log format containing
information on user, timestamp and the performed action with several at-
tributes (as an example h vinni, 13-05-2018, Gambero Rosso, “the food was
delicious”, . . .i);
– loaded into a particular Staging Area.
Concerning implementation details, the ETL module was realized exploiting
facilities provided by the Talend5 tool. In turn, the Staging Area repository was
implemented through the Cassandra6 columnar database.
The data storing task has the goal of generating the OSN graph database
by means of OSN Graph Builder module, using data from staging area. For each
OSN, the final graph is then stored into system Knowledge Base (KB). The OSN
Graph Builder module was realized on the top of Spark7 engine (choosing Python
as programming language), while we exploited Neo4j8 for the KB.
During the batch computation task several activities are performed:
– textual reviews are processed to infer the related sentiment using Sentiment
Analyzer module that is saved as edge property within the KB;
– on the base of a set of RPQs, the KB is queried by a Query Engine module
to extract the influence graph;
– an influence maximization procedure (based on the CMAB theory) is applied
on the influence graph to determine the most influential users (through In-
fluence Maximization module).
Regarding implementation details, the Sentiment Analyzer module was im-
plemented on the top of Spark engine leveraging several GATE9 NLP libraries.
5
https://www.talend.com/l
6
http://cassandra.apache.org/
7
https://spark.apache.org/
8
https://neo4j.com/
9
https://gate.ac.uk/
GATE detects sentiment related to each sentence in the text in terms of score (a
numeric value for the sentiment), sarcasm (a boolean value to indicate whether
the sentence is sarcastic or not) and polarity (a boolean value that can be posi-
tive or negative). RPQs are expressed in the Cypher Graph Query Language10
and the Query Engine module was realized using Spark. The IG is stored in
a textual raw format directly on HDFS. Eventually, the Influence Maximization
module implements the CMAB IM algorithm in Python leveraging Spark graphs’
management libraries.
Data visualization task allows to present results of several elaborations (e.g.,
influence graph, influential users, etc.) thanks to the functionalities provided by
Data visualization module implemented using the Jupiter11 tool.
5 Conclusion
In this paper we presented a novel approach for viral marketing based on mod-
eling OSNs as particular graph databases. In particular, we derive the influence
graph by analyzing influence paths and using CMAB technique.
Future works will be devoted to provide more evaluation of the proposed
approach and to compare the proposed methodology with different and more
recent influence maximization approaches.
References
1. Jordi Albors, Juan C Ramos, and Jose L Hervas. New learning network paradigms:
Communities of objectives, crowdsourcing, wikis and open source. International
Journal of Information Management, 28(3):194–202, 2008.
2. Flora Amato, Antonio Bosco, Vincenzo Moscato, Antonio Picariello, and Giancarlo
Sperl. A novel influence diffusion model based on user generated content in online
social networks. In Proceedings of the 6th International Conference on Data Science,
Technology and Applications. SCITEPRESS - Science and Technology Publications,
2017.
3. Flora Amato, Vincenzo Moscato, Antonio Picariello, and Giancarlo Sperlı́. Diffusion
algorithms in multimedia social networks: a preliminary model. In Proceedings of
the 2017 IEEE/ACM International Conference on Advances in Social Networks
Analysis and Mining 2017, pages 844–851. ACM, 2017.
4. Angela Bonifati, Wim Martens, and Thomas Timm. An analytical study of large
sparql query logs. Proc. VLDB Endow., 11(2):149–161, October 2017.
5. Glen Urban. Don’t just relate-advocate!: a blueprint for profit in the era of customer
power. Pearson Education, 2005.
6. Sharan Vaswani, Laks Lakshmanan, Mark Schmidt, et al. Influence maximization
with bandits. arXiv preprint arXiv:1503.00024, 2015.
10
https://neo4j.com/cypher-graph-query-language/
11
http://jupyter.org/