Kirchhoff Centrality Measure for Collaboration Network
This paper extends the concept of betweenness centrality based on Kirchhoff’s law for electric circuits from centrality of nodes to centrality of edges. It is shown that this new measure admits analytical definition for some classes of networks such as bi
- PDF / 1,129,855 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 35 Downloads / 152 Views
Institute of Applied Mathematical Research, Karelian Research Center, Russian Academy of Sciences, 11, Pushkinskaya St., Petrozavodsk, Russia 185910 [email protected] 2 Transbaikal State University, 30, Aleksandro-Zavodskaya St., Chita, Russia 672039 [email protected]
Abstract. This paper extends the concept of betweenness centrality based on Kirchhoff’s law for electric circuits from centrality of nodes to centrality of edges. It is shown that this new measure admits analytical definition for some classes of networks such as bipartite graphs, with computation for larger networks. This measure is applied for detecting community structure within networks. The results of numerical experiments for some examples of networks, in particular, Math-Net.ru (a Web portal of mathematical publications) are presented, and a comparison with PageRank is given.
Keywords: Kirchhoff centrality measure Weighted graph · Community structure
1
·
Betweenness centrality
·
Introduction
Betweenness centrality is an efficient concept for analysis of social and collaboration networks. A pioneering definition of the betweenness centrality for node i was given in [9] as the mean ratio of the total number of geodesics (shortest paths) between nodes s and t and the number of geodesics between s and t that i lies on, considered for all i, j. A shortcoming of betweenness centrality is analyzing only the shortest paths, thereby ignoring the paths being one or two steps longer; at the same time, the edges on such paths can be important for communication processes in a network. In order to take such paths into account, Page and Brin developed the wellknown PageRank algorithm for ranking of all pages in the Web’s graph based on the Markov chain limit theorem. Jackson and Wolinsky [11,12] proposed the model of communication game in which the utility depends of the structure of the network. They apply the Myerson value [1,13] to analyse the betweenness of the nodes in the network. Other allocation rules were proposed in [5,6,16,17]. Brandes and Fleischer [8] and Newman [14] introduced the concept of current c Springer International Publishing Switzerland 2016 H.T. Nguyen and V. Snasel (Eds.): CSoNet 2016, LNCS 9795, pp. 147–157, 2016. DOI: 10.1007/978-3-319-42345-6 13
148
V.V. Mazalov and B.T. Tsynguev
flow betweenness centrality (CF-centrality). In [2,8], a graph was treated as an electrical network with edges being unit resistances. The CF-centrality of an edge is the amount of current flowing through it with averaging over all sourcedestination pairs, when one unit of current is induced at the source and the destination (sink) is connected to the ground. In [3], the authors developed this concept further, suggesting to ground all nodes equally; as a result, averaging runs only over the source nodes, reducing computational cost. This new approach will be referred to as beta current flow centrality (βCF-centrality). Moreover, in contrast to the works [2,8,14,15], the weighted networks were considered in [3], mostly in the context of the βCFce
Data Loading...