Betweenness centrality is one of the most known centrality measures in network analysis. It has been largely investigated in the past, and several extensions tailored to speci c contexts, also involving IoT, have been proposed. However, the classical betweenness centrality is not able to correctly evaluate the centrality of nodes in a multiple IoT scenario, i.e., a scenario where several networks of smart objects cooperate with each other. In fact, in such a context, the classical betweenness centrality disregards that each network of a MIoT maintains its autonomy (so that a MIoT does not coincide with a single big network) but, at the same time, cooperates with the other networks through suitable cross nodes. In this paper, we propose three new measures of betweenness centrality speci cally conceived for a multiple IoT scenario. First we de ne them and, then, we show how they can achieve the objectives missed by the classical betweenness centrality.
The betweenness centrality of a node in a network is de ned as the fraction
of the shortest paths between all the pairs of nodes that pass through it.
Betweenness centrality is well suited for measuring the in uence of a node over the
information spread through the network [
However, the classical betweenness centrality is not able to correctly evaluate
the centrality of nodes in a multiple IoT scenario, i.e., a scenario where several
networks of smart objects (SO) cooperate with each other. In such a scenario
(known as Multi-IoT or MIoT in the literature [
In this paper, we aim at providing a contribution to address this problem. Indeed, we propose three new measures of betweenness centrality, well suited for a MIoT and, more in general, for a scenario consisting of a set of related IoT. These measures are called Inner Betweenness Centrality (IBC), Soft Cross Betweenness Centrality (SCBC) and Hard Cross Betweenness Centrality (HCBC). They have been designed to clearly distinguish the contributions of c-nodes and i-nodes and we show that they are able to reach this objective. In particular, IBC has been conceived for measuring the betweenness centrality with a focus on a single IoT of the MIoT and it privileges i-nodes over c-nodes. As will be clari ed in the following, it does not coincide with the classical betweenness centrality because, di erently from this last one, it also considers paths which connect two nodes of the same IoT but, at the same time, involve nodes belonging to other IoT of the MIoT. By contrast, SCBC and HCBC are specialized to measure the betweenness centrality of nodes by privileging paths involving more IoT of the MIoT and, therefore, c-nodes over i-nodes. As it is indicated by their names, this privilege is more marked in HCBC than in SCBC.
This paper is organized as follows. In Section 2, we provide an overview of related literature. In Section 3, we illustrate the MIoT paradigm in detail. In Section 4, we introduce our new betweenness centrality measures. In Section 5, we describe our experimental analysis. Finally, in Section 6, we draw our conclusions and have a look at some possible future developments of our research e orts. 2
As one of the most important centrality measure, betweenness centrality [
As for the IoT, which is an example of a very dynamic and constantly evolving
network, the approaches for the incremental computation of betweenness
centrality are extremely interesting. Among these, we mention the ones described in
[
Surprisingly, despite the strong tie existing among betweenness centrality
and information di usion, there are very few studies concerning the role of
betweenness centrality in IoT. To the best of our knowledge, the only approaches
dealing with centrality in IoT have been proposed as part of methods for
determining trustworthiness [
In this section, we provide a brief overview of the MIoT paradigm. In particular,
we introduce those concepts necessary to understand the rest of the paper. The
interested reader can nd all details about this paradigm in [
A MIoT M can be de ned as a set of m IoT: M = fI1; I2; ; Img, where Ik is an IoT. Consider an object oj of M. We assume that, if oj belongs to Ik, it has an instance jk , representing it in Ik.
In M, a set M Dj of metadata are associated with oj . The MIoT paradigm considers a rich set of metadata for an object, because metadata play a key role in favoring the interoperability of IoT and of their objects, which is the ultimate objective of a MIoT. M Dj consists of three di erent subsets: M Dj = hM DjD; M DjT ; M DjOi. Here, M DjD represents the set of descriptive metadata, which denote the type of oj . In order to represent and handle descriptive metadata, our paradigm uses a proper taxonomy, such as the one de ned by the IPSO Alliance3. M DjT represents the set of technical metadata. These are compliant with the object type. The IPSO Alliance provides a well de ned set of technical metadata for each object type. Finally, M DjO represents the set of operational metadata. These regard the behavior of oj and is de ned as the union of the sets of the operational metadata of the instances of oj . 3 IPSO Alliance - https://www.omaspecworks.org/
It is possible to represent Ik by means of a graph: Gk = hNk; Eki where Nk indicates the set of the nodes of Ik. There is a node njk for each instance jk of an object oj in Ik. Instead, Ek denotes the set of the edges of Ik. There is an edge ejqk = (njk ; nqk ) if there exists a certain form of relationship (for instance, proximity) between the instances jk and qk of the objects oj and oq in the IoT Ik.
Finally, a MIoT M can be modeled as a graph G = hN; Ei were: { N = Sm
k=1 Nk; in other words, N is the union of the sets of the nodes of the corresponding IoT. { E = EI [ EC . Here, EI = Sm
k=1 Ek. EC = f(njk ; njq )jnjk 2 Nk; njq 2 Nq; k 6= qg; in this de nition, njk and njq are the nodes corresponding to the instances jk and jq of oj in Ik and Iq.
In other words, the set E of the edges of M consists of two subsets, EI and EC . EI is the set of the inner edges of M and is the union of the sets of the edges of the corresponding IoT. EC is the set of the cross edges of M; there is a cross edge for each pair of instances of the same object in di erent IoT.
We call: (i) i-edge an edge of M belonging to EI ; (ii) c-edge an edge of M belonging to EC ; (iii) c-node a node of M involved in at least one c-edge; (iv) i-node a node of M not involved in any c-edge; (v) c-object an object having at least one pair of instances whose corresponding nodes are linked by a c-edge. 4
Given a node nj of a graph G, the classic de nition of betweenness centrality is the following:
BC(nj ) =
X ns2N;nt2N;ns6=nj;nt6=nj nsnt (nj ) nsnt where nsnt is the total number of the shortest paths from ns to nt, whereas nsnt (nj ) is the number of those shortest paths passing through nj .
If we apply BC to the graph Gk associated with an IoT Ik and consider Ik isolated from the MIoT, this formula involves shortest paths which only pass from nodes of Ik. In order to consider also the potential shortest paths that connect nodes of Gk but pass through nodes of the other IoT of the MIoT, it should be applied to the graph G corresponding to the whole MIoT. However, in this way, it does not capture that a MIoT consists of di erent autonomous IoT cooperating with each other thanks to c-nodes, which play a key role that should be evidenced by any measure of centrality conceived for a MIoT. We argue that, owing to these weaknesses, BC could present several problems in a MIoT context, especially when it is necessary to compute a centrality measure, which privileges those nodes that allow the crossing from an IoT to another.
To address the challenges mentioned above, we de ne three new centrality metrics. The rst of them is called Inner Betweenness Centrality (IBC) and is de ned as follows.
Let njk 2 Nk be the node corresponding to the instance jk of the object oj in the IoT Ik of the MIoT M. The Inner Betweenness Centrality IBC(njk ) is de ned as:
IBC(njk ) =
X nsk 2Nk;ntk 2Nk;nsk 6=njk ;ntk 6=njk nsk ntk (njk ) nsk ntk where nsk ntk is the total number of the shortest paths from ns to nt that involve also nodes of the MIoT not belonging to Nk, and nsk ntk (njk ) is the total number of these shortest paths that pass through njk .
IBC can be considered as an evolution of BC, capable of evaluating inner central nodes taking into account the fact that the network Ik is not alone but it is part of a MIoT. As a consequence, if all the paths connecting nsk to ntk include at least one node belonging to networks di erent from Ik but inside the MIoT, then BC does not capture them and considers nsk and ntk unconnected. By contrast, in a more precise way, IBC considers that there may exist one or more connections between them in the MIoT, even if they require the intervention of nodes belonging to other networks.
The second betweenness centrality measure that we propose in this paper is called Soft Cross Betweenness Centrality (SCBC) and is de ned as follows. Let njk 2 Nk be the node corresponding to the instance jk of the object oj in the IoT Ik. The Soft Cross Betweenness Centrality SCBC(njk ) is de ned as: SCBC(njk ) =
X nsu 2Nu;ntv 2Nv;u6=v nsu ntv (njk ) nsu ntv
In few words, SCBC(njk ) computes the centrality of a node by selecting only the shortest paths between nodes belonging to di erent networks. There is no constraint on the node njk for which we are computing the SCBC. As a matter of fact, njk could belong either to Nu or to Nv or, nally, to another IoT of the MIoT di erent from Nu and Nv.
SCBC can be considered as an evolution of BC capable of detecting central (in the betweenness centrality sense) c-nodes and i-nodes by taking into account that these nodes do not belong to a single-IoT scenario but that they are part of a MIoT, and this fact can in uence the shortest paths considered in the computation of betweenness centrality.
The last betweenness centrality measure we are proposing here is called Hard Cross Betweenness Centrality (HCBC) and is de ned as follows. Let njk 2 Nk be the node corresponding to the instance jk of the object oj in the IoT Ik. The Hard Cross Betweenness Centrality HCBC(njk ) is de ned as:
HCBC(njk ) =
X nsu 2Nu;ntv 2Nv;k6=u;k6=v;u6=v nsu ntv (njk ) nsu ntv
In few words, analogously to SCBC(njk ), HCBC(njk ) computes the centrality of a node by selecting only the shortest paths between nodes belonging to di erent networks. Furthermore, di erently from the de nition of SCBC, the node njk is constrained to belong to a network di erent from the ones of the source and the destination nodes of the path.
HCBC can be considered as an evolution of BC along the same direction as SCBC. The only di erence between SCBC and HCBC is that the latter is capable of detecting central c-nodes and i-nodes linking at least three IoT.
IBC, SCBC and HCBC are capable of overcoming the limits characterizing the classic BC in a MIoT. We remark again that IBC is di erent from the classical BC because it considers that the corresponding IoT is not isolated but inside the MIoT. Given the complexity of a MIoT, such a speci c study can be really useful for several applications.
By contrast, if we want to know the most central nodes in a MIoT, the most suitable choices are SCBC and HCBC. SCBC is capable of highlighting the most suitable nodes which allow the cooperation of nodes belonging to di erent IoT. The term \Soft" characterizing SCBC is due to the soft restrictions of its constraints.
HCBC, instead, is much more restrictive than SCBC. As a consequence, it detects few nodes presenting very high values of betweenness centrality. In fact, they ensure a high cooperation level in the MIoT because they are linked to a higher number of IoT than the other nodes.
The choice between SCBC and HCBC depends on the application context. For instance, if we consider information di usion, SCBC is well suited for fast information di usion. HCBC, instead, is a better choice for spreading information among many IoT, even though the di usion process will be slower than the one guaranteed by SCBC, because of the reduced number of nodes with a high HCBC. 5 5.1
Testbed
We derived our testbed from Thingful4, a search engine for the Internet of Things
supporting the search of data regarding a huge number of existing things,
distributed all over the world. Thingful also provides some suitable APIs, which
can be used for querying it through a software program and which we exploited
for the construction of our testbed. In order to obtain our testbed, we needed
to perform several tasks. They are described in detail in [
Our MIoT consists of 11 IoT, reported in the rst column of Table 1. We associated an object with each thing. Since we had 250 things, we obtained 250 objects. 200 of these objects had associated only one instance; 35 of them had associated two instances; nally, 15 of them had associated three instances. As a consequence, we had 315 instances in our testbed, distributed among the 11 IoT of our MIoT, as shown in Table 1. 4 Thingful: a Search Engine for the Internet of Things - https://thingful.net
A (necessarily complex) visualization of our testbed is presented in Figure 1. The interested reader can nd the corresponding dataset (in .csv format) at the address www.barbiana20.unirc.it/miot/datasets/miot2. The password to type is \za.12&;lq74:#". 5.2
Tests In this section, we describe the tests that we carried out to evaluate the significance of our new betweenness centrality measures in a MIoT and to compare them with the classical betweenness centrality. In our test activity, we adopted the testbed illustrated in the previous section.
We started our experiments considering the top-12 central nodes returned by BC and verifying the rank of the same nodes when the other centrality measures are applied5. Obtained results are reported in Table 2.
From the analysis of this table we can clearly observe that BC and IBC return completely di erent results. In fact, 11 of the top-12 central nodes returned by BC have a rank higher than 200 in IBC. Instead, a good correspondence can be observed between the ranks of BC and SCBC, denoting that BC shows a good capability of nding the most \soft" central nodes in a MIoT. By contrast, there is a very loose correspondence between BC and HCBC. This denotes that BC is incapable of nding the most central hard c-nodes. In conclusion, it seems that the BC's incapability of distinguishing between c-nodes and i-nodes and between c-edges and i-edges leads it to show a behavior (someway similar to the one of SCBC) intermediate between IBC and HCBC.
Then, we repeated the same evaluation for the top-12 central nodes returned by IBC. Obtained results are reported in Table 3. From the analysis of this table we can observe that the ranks returned by IBC and those returned by SCBC and HCBC are totally di erent. Actually, this was an expected result. However, it is interesting to observe that there is a weak correspondence between IBC and BC, because the top-12 central nodes returned by IBC have a rank between 5 and 95 in BC.
After this, we analyzed the top-12 central nodes returned by SCBC. Obtained results are reported in Table 4. Again, we observe a certain correspondence between SCBC and BC, a totally di erent behavior characterizing SCBC and IBC and a weak correspondence between SCBC and HCBC. 5 Recall that our MIoT consists of 315 nodes.
All the previous conclusions are con rmed by the analysis of the top-12 central nodes returned by HCBC, reported in Table 5. Observe, also, in this table the substantial di erence between HCBC and SCBC, due to the restriction characterizing the de nition of the former.
To further verify our previous conclusions and to quantify them, we decided
to apply the Kendall Tau rank distance metric [
We computed the Kendall Tau rank distance metric for all the possible pairs of ranks determined by considering the four metrics mentioned above. Obtained results are reported in Table 6. From the analysis of this table we can see that Nodes HCBC rank BC rank IBC rank SCBC rank all of our previous conjectures about the metric characteristics and similarities are con rmed. In fact, we can see that IBC and HCBC are completely di erent. The same happens for IBC and SCBC. Quite a high di erence can be observed for BC and HCBC. A certain (not very high) di erence can be observed for BC and IBC and for SCBC and HCBC. Finally, BC and SCBC present the highest similarity. 6
In this paper, we have presented an attempt to rede ne betweenness centrality in a multiple IoT scenario, i.e., a scenario where several networks of smart objects cooperate with each other. We have seen that the classical notion of betweenness centrality, which is well suited for a single IoT, present several weaknesses in this new scenario. Indeed, both if it is applied to one IoT at a time and if it is applied to the MIoT as a whole, classical betweenness is not capable of capturing the speci city of the MIoT scenario. In particular, it does not consider the fact that in MIoT there exist several autonomous networks of objects which cooperate with each other through c-nodes that, therefore, play a key role and should be privileged over i-nodes by a centrality measure operating in such a scenario. Then, we have introduced new betweenness centrality measures and we have discussed their features w.r.t. the classic betweenness centrality. Finally, we have presented some experiments devoted to con rm the inadequacy of the classical betweenness centrality for a MIoT and, then, to show the adequacy of the new measures.
In our opinion, this preliminary paper is a starting point for addressing many challenges in the context of MIoT. For instance, analogously to what we have done for betweenness centrality, it is possible to investigate new forms of centralities speci cally suited for a MIoT. Furthermore, we argue that smart objects are becoming more and more intelligent and autonomous, showing a behavior increasingly similar to the one of humans. In this case, it is not out of place to investigate issues like object pro ling and object reliability, as well as to de ne techniques to detect anomalous and possibly malicious behaviors of one or more objects in a MIoT.
This work was partially supported by: (i) the Italian Ministry for Economic Development (MISE) under the project \Smarter Solutions in the Big Data World", funded within the call \HORIZON2020" PON I&C 2014-2020 (CUP B28I17000250008), and (ii) the Department of Information Engineering at the Polytechnic University of Marche under the project \A network-based approach to uniformly extract knowledge and support decision making in heterogeneous application contexts" (RSAB 2018). 26. D.R. White and S.P. Borgatti. Betweenness centrality measures for directed graphs.
Social Networks, 16(4):335{346, 1994. Elsevier.