Social Network Analysis is employed widely as a means to compute the probability that a given message ows through a social network. This approach is mainly grounded upon the correct usage of three basic graph- theoretic measures: degree centrality, closeness centrality and betweeness centrality. We show that, in general, those indices are not adapt to foresee the ow of a given message, that depends upon indices based on the sharing of interests and the trust about depth in knowledge of a topic. We provide new de nitions for measures that overcome the drawbacks of general indices discussed above, using Semantic Social Network Analysis, and show experimental results that show that with these measures we have a di erent understanding of a social network compared to standard measures.
Social Networks are considered, on the current panorama of web applications, as the principal virtual space for online communication. Therefore, it is of strong relevance for practical applications to understand how strong a member of the network is with respect to the others.
Traditionally, sociological investigations have dealt with problems of de ning properties of the users that can value their relevance (sometimes their importance, that can be considered di erent, the rst denoting the ability to emerge, and the second the relevance perceived by the others). Scholars have developed several measures and studied how to compute them in di erent types of graphs, used as models for social networks. This eld of research has been named Social Network Analysis. Sometimes the same name is attributed to a wider context, where we also mean to include analysis of the ways in which such values arise (for instance, processes able to change importance of members), or to provide methods for employing these measures in applications.
Majorly, scholars dealt with the Social Network Analysis from the viewpoint of information ow, namely they provide models of importance (and other aspects as well) to understand how probable would be that a piece of information passed through a given node. Mainly, the information ow has been studied for propagation of viruses (both in medical and in computer security contexts), news spread-out (and hence, studies about viral marketing as well), and message passing in certain application contexts.
Three basic measures have been developed that belong to the family of centrality measures : degree centrality, closeness centrality and betweeness centrality. In this paper we criticize the models of social network analysis developed for these measures, showing that there are cases in which these measures are not adapt. The criticism arises mainly as related to the absence of semantic aspects in measures. To show what we mean with these limits, let us introduce a general example.
Example 1. Consider two users of facebook, Alice and Bob, and assume that the measures of importance is settled to coincide with the number of friends, the distance to non-friends, and the probability of being in common between two non-friends. Alice results to be much more important in the network than Bob, under all the three measures. However, to a closer observation we notice that this result is de nitely true for certain topics whilst it results false for other ones. In particular, Alice is much more expert than Bob about Geography and History, equivalent with respect to Sport and weaker for Cuisine. When someone passes a message to Alice and the message regards Geography, she is much more likely to pass the message than Bob. Conversely, when a message regards Sport the opposite case holds. Cuisine information ow is better when passes through Bob.
The above described example shows that it can be the case that two members of a social network can exhibit di erent orders of prevalence in terms of centrality depending on the topic we refer the prevalence to. This may produce e ects that cannot be reproduced by a single index, as shown in the example below. Example 2. Consider ve individuals: Alice, Bob, John, Annie and Charlie. Alice is connected to Bob and John; John connects also to Bob and Charlie and also Annie is connected to Bob and Charlie, while Bob is connected directly to everyone and is person who loathes gossips when the others like or accept it.
If we don't consider topics we would say that dropping a gossip in the network, the right person to deliver it to have it spread is of course Bob.
Unfortunately, the message has contents of a topic which probably will see Bob cancel it, instead of forwarding it, while both John and Charlie are good choices because they are directly connected to three people each and they have a di erent attitude toward gossip than Bob.
The purpose of this paper is to give account to the aspects showed in the example above. We provide a model of Social Network Analysis that takes into account topics, and show that it can foresee information ow for message treating those topics in a more accurate way than classical topic-free social network analysis. We also name Semantic Social Network Analysis the techniques we studied in this investigation to cover a part of research that some previous studies did not cover satisfactorily.
The rest of the paper is organised as follows: in Section 2 we discuss related work on the subject. Further we employ Section 2 to provide the actual technical part of the paper and in Section 4 . Finally Section 5 takes some conclusions and sketches further work.
The reference literature can be considered as articulated in three themes: { Studies about implicit social links that exist among users of the internet (or of an internet application), or about enrichment of social web; { Investigations of the semantics of social networks; { Research about Social Network Analysis and relationships to semantic issues. Regarding the rst topic, we can look at methods for social link extraction, as discussed below, as one of the best structured investigations on the theme. This speci c method for extracting social networks from the web using similarity between collective contexts is proposed in [2]. The authors construct three social networks on the same set of named entities. They use Jaccard, overlap and Normalized Google Distance (NGD) [4] coe cients to retrieve degree of closeness between entities. They show how actors may be assigned di erent relevance degrees and that actors having higher ranking results may be assigned lower ranks and inversely by choosing another measure to perform the ranking. In our perspective their work is solid, but lacks in one important aspect, the authors build homophily on the based of the contents. This is a technique to build a network, and not an analysis of the network itself, as we do in this work. Su ering the same issue is the work of [9], where the authors present a new framework for applying Social Network Analysis to RDF representations of social data. In particular, the use of graph models underlying RDF and SPARQL extensions enables us to extract e ciently and to parametrize the classic Social Network Analysis features directly from these representations. The main criticisms to the proposed approach lie on the fact that, as already shown in many practical cases, it makes a lot of di erence, in terms of understanding of the structure of similarity between nodes, to know the relevance of the two nodes. In fact, similarity can be used, as done, for instance in [6], for community detection, where members are related to each other based on their similarity in semantic terms. This is di erent in terms of relationship, with respect to measuring the relevance and study attractivity. Clearly, being interested in Football lies on liking it, but the community is formed around authoritative persons, for instance journalists. A more practical research has been documented in [16] where an application of semantic social networks and attraction theory to web based services is carried out. The relation between trust and Social Network Analysis has been investigate in [17] and speci ed as a means for understanding deeply the meaning of centrality and other measures as related to authority. The same concept is employed to provide a framework for the general interpretation of the logic bases of recommendation systems in [7]. The studies cited above all aim at discovering network links by means of mining techniques. On the other hand, the introduction of notions derived from semantic web into social networks is the core quest of many recent studies, including [18]. As a complete reference to the current literature about meaning of social links, and relationships between social web and semantics, readers can look at [12]. More deeply, in [14] a direct and explicit comparison between social networks and the semantic web is carried out. This paper proposes a parallel between networked knowledge of members in a network and the basic notions of semantic web. The same issue is dealt with, with the speci city of a known technique, the semantic networks, in [8]. More generally, the semantic web methods are employed for understanding the meaning of social networks as sharing platforms for common knowledge, in [15]. The idea of using Social Network Analysis as a means for forecasting the probability of a message to pass through a given member of the network itself is not novel at all. Base of our analysis is the criticisms to the roughness of the employed measures, criticisms that are not novel anyhow. This has been dealt in two distinct ways: by using semantic methods for habilitating the forecast processes: in particular in [19], authors use semantic networks for foreseeing the behaviour in facebook. On the other hand, many criticisms are applied to centrality measures ([11], [10]). The main criticisms, that are met by the above mentioned investigations as well as by researches tending to correct the aws of the general methods for centrality measures, and the measures themselves, lie on the weakness of the notion of similarity derived from the notion of centrality. The above mentioned notion of similarity as derived from centrality measures, and its applications to the notion of reciprocity, a concept that has a crucial importance, for instance, in asymmetric social networks (Instagram, Twitter) are dealt with in [1]. Authors show that centrality measures as used so far are unsuccessful in forecasting the information ows. 3
In this section, we focus in computing two of the basic centrality measures: Degree centrality and Closeness centrality including topic and subtopic. 3.1
In order to de ne a di erent structure of a Social Network that includes the interests of an actor, we here introduce concepts like "topic" and "subtopic" and the relationships between them as they are de ned in [3, pp. 1{77]. Let us consider a simple example that represent knowledge concerning Cuisine (Figure 1). The structure is meant to represent the generality/speci city of the concepts involved, therefore is called a terminology. For example, a link between Cuisine and Italian Cuisine says that "Italian cuisine is a cuisine". When a concept is more speci c than other concepts, like seen in the previous example, it inherits the property of the more general one.
Messages in a social network can be classi ed as belonging to a set of topics and subtopics. 3.2
In classical Social Network Analisys actors with the highest Degree centrality are considered key members on the network. In other words, actors with many Italian Cuisine
French Cuisine
Indian Cuisine
Japanese
Cuisine direct connections are considered more important. As discussed earlier, this may not be true if we take into account semantics.
Consequently, we try to compute the Degree centrality of an actor, in the network, based on his depth (interest) in speci c subtopics. We here consider an actor more important or more central in a network if he has a high value of depth in a speci c topic. In order to distinguish the measures we name this measure Semantic User Pro ling. We compute the measure for one actor for all ve topics described earlier. The depth value can vary from 0:0 to 1:0. Intuitively, a depth of 1:0 means that the person is maximum interested in a speci c subtopic and a depth of 0:0 means that the person is not interested at all in that subtopic. The same stands also for topics. It is possible to compute Semantic User Pro ling for a node vp for each topic th as follow: l SUP (vp)th = X
p i shi i=1 where h = f1; :::; rg with r the number of topics, l represents the number of subtopics for each topic th and i is the weight of each subtopic shi. 3.3
Applying the existing measure Closeness centrality, actors with highest Closeness centrality are considered more central as they require only few intermediaries to reach other actors. The closeness is de ned as the reciprocal value of the sum of all shortest paths from one actor to all others actors in the network. This could not be completely true if we take into account semantics.
We here consider the closeness of an actor with respect to subtopics, as the minimum value between the depth of the actor and all others actors depth, in the network, that are on the shortest path from the actor to them.
If there is more than one shortest path from the actor to another actor, then we consider the minimum value of depth between all shortest path. Thus, we compute the Closeness centrality of an actor, in the network based on the minimum between his depth and the depths to all other actors.
To distinguish the measure from the standard Closeness centrality we call this measure Semantic Closeness centrality. The distance between two nodes, taking into account subtopics, that we named reversetopicdistance, is de ned as:
l dt(vp; vq) = min(min((X i=1
l i shi)p; (X i=1
l i shi)k); min((X i=1
l i shi)k; (X i=1 i shi)q)) where (Pli=1 i shi)k represents the depth of the actor, denoted by the node k, in the topic th and: { h = f1; :::; rg with r the number of topics { l is the number of subtopics that de nes the topic th { shi is the subtopic included in the topic th (shi v th) { i is the weight of the subtopic shi The distance denotes the minimum depth on the shortest path form the node p to the node q, for which all intermediary nodes are in the set f1; 2; :::; kg. At this point it is possible to compute Semantic Closeness centrality for a node vp on a topic th as follows:
CSC (vp)th =
Pn p=1;q6=p dt(vp; vq) n 1 where, once more h = f1; :::; rg with r the number of topics and n is the number of actors in the network.
It is reasonable to think that the Semantic Closeness centrality of an actor in a certain topic may be the sum of all reversetopicdistances weighted by the number of nodes, excluding the node for which we compute the measure. Intuitively, this measure represents the minimum depth in each topic, between one actor and all other actors, following the shortest path in the network. 3.4
From the Semantic Closeness centrality of a node on various topics is possible to derive a new measure, that we named Semantic Actuation, in order to quantify the actuation of an actor considering all topics. We can de ne it as a cross-topic measure. To explain, the actuation can be de ned as the good chance that an actor becomes engaged when a message regarding di erent topics arrives to him. For a node v, we can express this as:
SA(v) =
r X CSC (v)th h=1 where r is the number of topics.
The actuation of an actor is de ned as the sum of the Semantic Closeness centralities in all topics.
Intuitively, the formula nds the actors that are closer to all other actors in the network for all topics. 3.5
Computation of degree centrality is straightforwardly obtained from the basic algorithm for Social Networks, that simply counts the number of incident edges of each vertex, and then derives the consequent computations for relative and graded variants. In Semantic Social Network Analysis, we sum the weights, instead of counting the incident edges.
The base for computing both closeness and betweeness centrality is the labelling of edges by the graph distance, meant as shortest path. We extend here the method known as Floyd Warshall Algorithm. In indirected unlabelled graphs, the algorithm computes just the incident edges to obtain the correct value of distances. We use the vectorial min() function both to initialize the distance matrix and to give a the value of the distance between two vertices in the core of the algorithm and we extend the algorithm in [5] to take into account topics and subtopics.
{ A n n Topic Matrix T representing the minimum depth of all nodes in a graph. T = (tij ), where tij is the minimum depth between the depth of the node i and the depth of the node j on topic t in a graph G = (V; E): tij = ( 0 if i = j min(ti; tj ) if i 6= j and (i; j) 2 E
if i 6= j and (i; j) 2= E 1 { A n n Inverse Topic Distance T D representing the reversetopicdistance as described in the previous section. T D = (tdi(jk)), where tdi(jk) is the minimum depth on topic t on the shortest path from node i to node j for which all intermediary nodes are in the set f1; 2; : : : ; kgR Note that tdi(jk) can be recursively de ned as: tdi(jk) = ( tij
if k = 0 min(tdi(jk 1); min(tdi(kk 1); td(kkj 1))) if k 1 { A n n Weight Matrix W representing the edge weights of all nodes in a graph. W = (wij ), where wij is the weight of an edge between node i and node j in a graph G = (V; E).In our case the weight of each edge is 1 wij = ( 0 if i = j 1 if i 6= j and (i; j) 2 E 1 if i 6= j and (i; j) 2= E { A n n Path Matrix D representing the path distance between nodes, where D = (dikj ). dikj is the length of the shortest path from node i to node j for which all intermediate nodes are in the set f1; 2; : : : ; kg.
Note that di(jk) can be recursively de ned as: di(jk) = ( wij
if k = 0 min(di(jk 1); di(kk 1) + d(kkj 1)) if k 1 In the non extent algorithm we used ">" because we were no interested in a path with the same length as the previous path (only in shortest), but here we want to nd the minimum depth on all the shortest path from a node to another, thus we use " ".
The Semantic Floyd-Warshall Algorithm solves the problem of the shortest path between all pair of nodes and the minimum depth between all pair of nodes in a graph in time O(n3), where n is the order of the graph. At each step incrementally improves an estimate on the shortest path between two nodes and an estimate on the minimum depth between two nodes. 4
To test the methods introduced above in section 2, in order to nd the Semantic centrality of an actor, we conduct an experiment on a small, but real, part of the giant network Facebook.
With the experiment we want to examine the way in which the centrality of an actor changes when semantic information is included. (a) Network pointing highest Degree centrality (b) Network pointing highest Closeness centrality To perform the experiment, we take advantage on a relative small, but realistic dataset from Stanford Dataset Collection 1 [13].
We choose the social network Facebook because we want to lead the experiment on a representation whit an undirected graph. Other Social Networks, like Twitter, are usually represented with direct graphs. This, because are based on concepts like "followers" or "following", contrarily on Facebook, where we can found the desired notion of "friend".
The dataset consists of a list of friends from Facebook, collected from survey participants using the Facebook app2. As one can expect, the data has been anonymized by replacing the id-s with new values. From the 10 networks available we choose one with 347 nodes and 5038 edges. At this point we have a connected and undirect graph that represent 347 actors and 5038 friend relationships between them.
The two gures (Figures 2(a) and 2(b) ) display the earlier described network, where in the rst one we point out the nodes with the highest Degree centrality and in the second one the nodes with the highest Closeness centrality.
Lacking data about topic interest, a gaussian distribution has been assumed in order to simulate the depths of interests for each person in various subtopics. 1 http://snap.stanford.edu/ 2 https://www.facebook.com/apps/application.php?id=201704403232744 We used ve topics with four subtopic. Each person has been assigned a value of depth between 0:0 and 1:0, where 0:0 can be interpreted as "the person have no interest in the subtopic" and 1:0 can be interpreted as "the person is maximum interested in that speci c subtopic". The two tables below (Tables 1 and 2) evidence the rst 10 results when the standard formulas of centrality measure, Degree centrality and Closeness centrality, were applied on the network described earlier.
The rst table points out the rst 10 actors with the highest Degree centrality. The maximum value of Degree centrality can be 346, but note that the actor with id56 has degree centrality 77 which is the maximum value on this network.
Let us now focus on the results obtained on the semantic network. The next two tables (Tables 3 and 4) reveal the rst 10 actors with higher Semantic Degree centrality, where in the rst one are ordered by their Semantic Degree centrality in Movie and in the second one are ordered by the Semantic Degree centrality in Music.
It is clear that actors, considered important applying the existing measure, in the second case, applying the new measure, may not results important (keypersons) in the network showing that semantic measures can capture di erent information -and we say also important ones- compared to standard ones 5
In this paper we investigated an extension to Social Network Analysis based upon the usage of a network model that includes the notion of topic. This leads to a further model that incorporates the notion of sensitivity, by means of a value, called activation that is meant to denote the probability of a member of the network to be active in an information ow. Algorithms for computing extended notions of centrality are provided, and proved to be correct, complete and computationally e cient. We provide experiments that show that our approach can fruitfully solve few evident drawbacks of the general model, as applied to information ow forecast.
There are at least three di erent ways in which this investigation can be extended. First of all we aim at formalising a problem of dissemination of information pieces throughout a network. The problem can be formulated as follows: given a social network, a number k and a probability value p, select k members in such a way that the set of members reached by an information piece sent to the members in the selection and disseminated by them and the chains of members generated therefore, has a probability of being total (namely to cover the entire network) of at least p.
A second study investigates ways of providing reacher models of topics. In particular, we aim at investigating topics with sub-topics. 5. Matteo Cristani, Claudio Tomazzoli, and Francesco Olivieri. Semantic social network analysis foresees message ows. In Proceedings of the 8th International Conference on Agents and Arti cial Intelligence, pages 296{303, 2016. 6. Juan David Cruz, Cecile Bothorel, and Francois Poulet. Community detection and visualization in social networks: Integrating structural and semantic information.
ACM Trans. Intell. Syst. Technol., 5(
Networks, 29(