In this paper, we describe a novel data model for particular online business social networks such as Tripadvisor and Yelp: we also de ne a greedy in uence maximization algorithm to determine the most in uential users on the base of proper in uence patterns. The result of such analysis is then combined with some economic data in order to propose a set of possible nancial strategies for business objects. Finally, a case study and some preliminary and interesting results are presented for the Yelp dataset.
Nowadays, there is a massive usage of social networks, and this phenomenon a ects many contexts and real life scenarios. People express opinions and sentiments, often sharing also multimedia contents. The di usion of these new communication instruments allows the proliferation of a big amount of data, and Internet becomes the most important source of social network data.
However, handling and analyzing such data is not a trivial task, since several aspects should be taken into account. First of all, social network databases are very complex and heterogeneous, storing di erent kinds of information. Secondly, the huge amount of available data and stored information makes it hard to analyze and correlate, falling into the eld of big data. Another important challenge consists in the problem of applying traditional data mining techniques on social data in order to extract information and correlations.
In this paper, we focus on the eld of social networks in which users express opinions, judgments, and ratings about items, places, and/or services. There are lots of platforms allowing to do this, and Tripadvisor and Yelp are only the most known and representative ones.
In particular, we aim to investigate the problem of how one user can in uence other user judgments with her/his opinions and reviews on an item. Since the items objective of the judgments belong to the context for which the social network has been thought, it can also contains economic data. In this case, we refer to a particular type of items, called business objects.
Analyzing business objects in a social network context should take into account not only object details and economic aspects, but also the in uence and the bias that user judgments give to other users. In this direction, the goal of our work is twofold: in a rst phase, we propose a model for the social network allowing to discover the most in uential users and, secondly, how this result can be merged with economic data in order to propose nancial strategies for business objects.
In order to understand the potentiality of Social Network Analysis for nancial purposes, let us suppose that we are in a big city area in which there are several types of business objects (such as pubs, museums, hotels and so on) that provide di erent services and/or products. We can associate to each business object several information regarding their main features (i.e. open hours, atmosphere, types of cousin, etc.), and also economic information (i.e. ticket information, menu price, etc.). Users are able to make several reviews, that are short text descriptions of their experience in these rms after they visit them. An automatic system could perform a NLP analysis of the reviews, in order to extract the sentiment of each one, and successively derive an homogeneous graph, obtained by correlating temporal and semantic information, to infer weighted relationships between users. Exploiting the features and the properties of these graphs, we identify the most in uential users focusing on a speci c area or on a given category of business objects. The retrieved social in uence may be used in viral marketing: the small subset of in uential users in the social networks is essential for marketing a product, exploiting the attitude of the most in uential people for suggesting to a given business object a speci c advertising strategy, a di erent type of approach to hit these speci c users or to create alliance with other shops in order to increase their revenue growing up the amount of users attending their business activity.
The rest of the paper is organized as follows. Section 2 discusses the stateof-the-art for the in uence maximization and other research issues in business social networks. In Section 3, the proposed model for social network and the building of the in uence graph are described, whereas Section 4 discusses the adopted in uence maximization strategy. Section 5 shows preliminary experimental results. Eventually, Section 6 gives some conclusions and discussions of the paper. 2
The technological development leads to see Online Social Networks (OSNs) an important means on which it is possible to make business, allowing rms to promote their products and services and users to provide feedbacks about their experiences.
In [
Nowadays, the continuous increase in the use of smartphones has led to the emergence of a new type of social network called Location Based Social Networks (LBSNs); the peculiarity of these networks is to integrate the user's location into the well-known OSN capabilities, introducing new research topics and issues.
An in uence maximization problem [14] proposes to maximize the bene t of location promotion, leveraging the feature of LBSN.s To address this problem, the authors propose two models to capture the check-in behavior of individual LBSN users, based on how location-aware propagation probabilities can be derived.
Indeed, a large number of people rely on content published on OSN for making their decisions. This facet leads to engage spam reviewer to increase the popularity of particular business objects or to harm a possible competitor.
Thus, the spammers detection is another important research topic in a LBSN;
in fact the 20% of the reviews in the Yelp website are actually spam, as shown
in [
The wellness of information in OSNs has allowed to focus on Viral Marketing applications, developing new marketing strategies based on \word-of-mouth". Di erent models have been proposed in literature to describe the spread of idea in OSNs.
A family of approaches are based on Stochastic models, in which a node
can be in an active or inactive state depending on the in uence exerting by its
activated neighbors. Granovetter and Schelling [
Based on the spread models, the in uence maximization problem has been
proposed in literature. A rst work on this topic is provided by Richardson
and Domingos [
To model a real market, we de ne a particular network, called Knowledge Sharing Network, in which there are N 2 rms that provide several services and M users. In particular: De nition 1 (Knowledge Sharing Network) A Knowledge Sharing Network (KSN) is a quadruple G = (V ; E; ; !), where V is a set of vertices, E is a set of edges, and and ! are two weight functions such that : V ! [0; 1] and ! : V V ! [0; 1] The set of vertices is de ned as V = U [ BO, with U being a set of KSN users and BO a set of business objects. The set of edges is in turn composed by three kinds of relationships: Social relationships, established between two users, Business relationships, existing between a user and business object, and Neighbor relationships, established between two business objects that are located in the same geographic area and belong to the same category.
In our vision of KSN, users and business object nodes are generic nodes containing several attributes such as preferences, price, business info, open hours and so on. Thus, a KSN model allows to represent heterogeneous entities and relationships in a uni ed network.
Example 1 (Example of KSN) To better explain our idea we show an example in Figure 1. Let V inni, Giank, F lora and P icus be four users and BO1, BO2 and BO3 be three rms. The four users made reviews in di erent times (t1 > t2 > t3 > t4) about the three business objects, two of which are linked by a neighbor relationship. It is possible to note how it is easy to represent di erent types of relationships by our model. Eventually, each user or business object is respectively composed by several attributes about preferences or services.
The in uence analysis problem seeks to identify the best subset of users that allows to maximize the spread of new products, new idea or so on. Moreover, in the real world, there are di erent rms competing among themselves with the aim to maximize its pro t in order to attract an increasing number of customers. In particular, the in uence exerts from a user respect to another one is computed by evaluating several common actions made on the same business object.
To analyze user behavior we exploit the concepts of social path and relevant social paths.
De nition 2 (Social Path) A social path between two vertices vs1 and vsk of a KSN is a sequence of distinct vertices and edges sp(vs1 ; vsk ) = vs1 ; es1 ; vs2 ; :::; esk 1 ; vsk such that 9e(vsi ; vsi+1 ) 2 E for 1 i k 1. The length of the path is Pik=11 !(e1si ) , being a normalizing factor. We say that a social path contains a vertex vh if 9e(vi; vh) : e 2 sp(vs1 ; vsk ).
The above de nition allows us to correlate the path length with the concept of distance between two nodes interconnected by the examined path; exploiting this de nition, we can perform pruning strategies based on a given threshold. The following example will better explain our basic ideas.
Example 2 (Social Path) Considering the network in Example 1, we can identify several social paths, representing communication ows between users by social channels. In particular, the business objects is a communication means to interconnect users in this type of network. In Figure 2 we represent in concise way these types of information. De nition 3 (Relevant Social Path) Let be a set of conditions de ned over the attributes of vertices and edges of a KSN. A relevance social path is a social path satisfying .
A particular kind of relevant social path is constituted by the in uential paths that connect two users and by which a user can \in uence" other users. It is possible to identify weak and strong in uential paths; in particular, in the rst case, the user ui in uences uj , if the user uj posts a review of the same sentiment of the review previously posted by ui on the same business object, while in the second one two users have to be also friends.
Example 3 (In uential Path) Considering the Example 2, we can identify three relevant social paths. Each social path corresponds to a sequence of reviews or tips following given rules; for instance, a social path is instantiated due to the fact that Giank made a review on BO2 before to Vinny and with the same sentiment, while another path is instantiated due to the fact that Picus made a review on another business object close to BO2 with an opposite sentiment.
To deal with the in uence maximization problem, we build an homogeneous graph (In uence Graph) IG = (V ; E; !) whose vertices are speci c users of KSN; in particular, there exists an edge e between two vertices vi and vj for all in uential paths connecting vi and vj . For each edge, the related weight will be determined as in the following: !(ei;j ) =
PM k=1 (spk(vi; vj ))
Nj ; (1) M being the number of distinct in uential paths between vi and vj and Nj the number of in uential paths of having as destination vertex vj . Example 4 (In uential Graph) Considering the Example 3, we can build the In uence Graph, shown in Figure 4, by exploiting the equation 1. In particular, it is possible to note that Picus can in uence two users: Giank and Vinny, since they could have seen the previous negative review made by Picus on BO1, that is a business object close to BO2.
The in uence maximization problem aims at identifying a minimum number of users that maximize the spread of new idea or technologies in the OSN. Nevertheless, given that the interest of users for a speci c product or business object is variable due to di erent causes, for instance the change of opinion of friends about the examined products or the introduction of new product, the temporal dimension acquires an increasing value. The scope of rms' market campaign is to maximize the spread of new product in a speci c time interval, for instance couple of weeks or few months, more than reach as many users as possible in many years.
Thus, we can deal with the following problem: De nition 4 (In uence Maximization problem) Given a sharing knowledge graph KSN G, a set of users U , k a desired number of in uential people and a time-horizon T , the in uence maximization problem consists in identifying a minimal subset of users that allows to maximize the spread of in uence in G within T .
In this formulation of the problem the aim is the identi cation of the subset
of most in uential customers in the KSN graph. Thus, this formulation of the
problem led us to ask who are the most in uential people and how we can identify
them. To deal with this problem our idea is to leverage the hill climbing greedy
strategy proposed by Kempe et al. [
Thus we propose the In uential path greedy algorithm (IPGA) 1. The idea behind our approach is to build iteratively the seed set S, choosing in each step a node that leads to obtain the largest increase in the estimated spread until the cardinality of S does not equals to k.
Algorithm 1 In uential path greedy algorithm 1: procedure Inf luential P ath Greedy Algorithm(G,k) 2: S = ; 3: while jSj k do 4: u arg maxv2V 5: S S [ u 6: end while 7: return S0 8: end procedure
To better explain our idea we show how the described algorithm allows us to identify the two in uential users in Figure 4. By using the proposed greedy strategy on the in uential graph of Example 4 and choosing a value of k equals to 2, it is possible to note that the most in uential users are Picus and Giank. In fact, as shown in Figure 4, other users in the network are more likely to be in uenced by these two users.
In the following, we will describe the used methodology for evaluating the efciency and the e ectiveness of the introduced in uence maximization algorithm over the examined network4.
To perform the described evaluation, we used the Yelp dataset5: it is composed by information about 77 K local businesses in 10 cities across 4 countries (U.K., Germany, Canada, US). Moreover this dataset contains also 2.2 M of review made from 552 K of users connected through 3.5M of social edges. We enrich the examined dataset crawling di erent economic information from YELP website 6; in particular, for each category, we use the uni ed id of each business object for extracting the related economic information that can regard the range price, menu price, ticket price by using the YELP API7.
Experiments have been conducted exploiting ENEAGRID/CRESCO High
Performance Computing infrastructure resources. ENEAGRID consists in
computational and storage resources (more than 8000 cores and 1.5 PB of storage)
located in 6 ENEA research centers interconnected by means of GARR network.
Among the 6 sites, Portici Research Center is the most relevant one hosting the
newest CRESCO 8 clusters [
To perform our experiments, we set up an environment for big data processing using Spark and Hadoop. We set up a cluster in a cloud-based environment consisting of 3 computing nodes with 4 cores 16GB RAM each one.
We show the evaluation made to suggest possible market strategy based on trend set analysis and user preferences.
Firstly, we measured the execution time of our approach of in uence maximization varying the size of the related seed set k.
Successively, we evaluated the spread of in uence with respect to a given ground-truth. The ground-truth is composed by a set of in uential users using a strategy that takes in account how many relevant reviews have been made by each user. For this reason, we de ne the popularity value for each user, based on a combination of votes (useful, funny and cool votes) that users can assign to its reviews.
The trend of running time varying the cardinality k of seed set from 1 to 50 is shown in gure 5.
We use a recall based measure to evaluate the e ectiveness of our approach with respect to the generated ground truth:
R = jU \ U~ j ^ ^ jU j 4 For the provided analysis, we set the value of normalizing factor 5 https://www.yelp.com/dataset challenge 6 www.yelp.com 7 https://www.yelp.com/developers/documentation/v2/overview 8 http://www.cresco.enea.it equals to 0:5 where U^ corresponds to the set of in uentials in the ground-truth and U~ is the set of in uentials computed by the in uence maximization algorithm.
The obtained results of recall have been shown in Table 1, computed on both
the following graphs and considering the seed set cardinality k equals to 50,
following the parameters settings in [
As we can see from the results shown in the table 1, our method provides better performance with respect to the approach based on friendship relationships because it allows to consider several data, including also nancial information.
These types of data contribute to properly de ne the in uence exerts from users on the others that corresponds to a combination of the relevance of reviews made by them and the price range of business objects that they attend. These types of information are useful in modern market in which the dynamic interactions among users can lead the business objects strategies. Thus, based on the data involved in the proposed model ( nancial information, geographical information and so on), each rm can decide what is the better strategies to spend the budget for its market campaign. Eventually, each company can choose among the following strategies in each time horizon: in uence new users by providing them discounts or gifts, consolidate in uenced users through speci c o ers for them, or cooperate with other business objects.
In this paper we have presented a data model for social network in order to analyze the in uence among users. This approach can be useful for several applications such as trend analysis, viral marketing, location mining, urban planning and so on. In particular, the in uence maximization problem is surely useful for increasing the pro ts obtained by marketing plan. The identi cation of the most in uential people, in fact, allows rms to better optimize the marketing plan, tailoring the action for each customer to his preferences. 14. Zhu, W.Y., Peng, W.C., Chen, L.J., Zheng, K., Zhou, X.: Exploiting viral marketing for location promotion in location-based social networks. ACM Trans. Knowl. Discov. Data 11(2), 25:1{25:28 (Nov 2016), http://doi.acm.org/10.1145/ 3001938