what-when-how
In Depth Tutorials and Information
12.5 RoutinginDisconnectedSocialNetworks[4]
he clusters of some networks sometimes may not directly connect with each other.
hey have to select a suitable bridge tie to deliver a message to the destination. Using
Figure 12.3 as an example, we assume that cluster 1 does not directly link to cluster
3. hus, if the source node is in the cluster 1, it is very diicult to send a message to
the destination node which is in the cluster 3. But it does not mean that there is no
forward link for the source node to propagate its information. In Figure 12.3, node
a1 that belongs to cluster 1 can directly connect to a2 (that belongs to cluster 2).
Likewise, a3 (belongs to cluster 2) can directly connect with a4 (that belongs to clus-
ter 3). Moreover, a2 and a3 are involved in the same cluster. he dark line illustrates
the bridges which are established by a1 and a2, a3 and a4, respectively. hrough this
path the source node can forward its message to the destination node.
In fact, by indentifying the centrality of a node, we can explore the bridges
between different clusters. Typically, the centrality of a node is the degree in the
frame of a network. Centrality can demonstrate the ability of a central node to
communicate with other nodes in the network. Nowadays, there are three popular
centrality measures: the Freemans' degree, closeness, and betweenness measures.
“Degree centrality” is an efficient way to find the amount of directly con-
nected ties, which includes a selected node. For instance, a high degree centrality
node can keep connection with a huge number of other network nodes. During
the information propagation this kind of node can play the role of bride for
communications between different clusters. In contrast, other surrounding nodes
may be not as important as the high degree node in maintaining the connectivity
with other clusters. he degree calculation for a selected node a i as follow:
n
1
Cdegree(ai)  
P ai ak
(
,
)
=
i
Cluster 2
a2
a3
a4
a1
Cluster 3
Cluster 1
Source
Destination
Figure 12.3
Bridge ties with disconnected clusters. (From Liben-Nowell,
D. and Kleinberg, J. 2003. The link prediction problem for social networks.
In Proceedings of the Twelfth International Conference on Information and
Knowledge Management (NewOrleans,LA[November03-08,2003].CIKM'03.
ACM,NewYork,556-559.)
Search WWH ::




Custom Search