Fu Norie, Suppakitpaisarn Vorapong
JST, ERATO Kawarabayashi Large Graph Project, Global Research Center for Big Data Mathematics, National Institute of Informatics (NII), 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-0003 Japan.
Department of Computer Science, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo, 113-0033 Japan.
Comput Soc Netw. 2016;3(1):6. doi: 10.1186/s40649-016-0031-1. Epub 2016 Oct 21.
While the temporal networks have a wide range of applications such as opportunistic communication, there are not many clustering algorithms specifically proposed for them.
Based on betweenness centrality for periodic graphs, we give a clustering pseudo-polynomial time algorithm for temporal networks, in which the transit value is always positive and the least common multiple of all transit values is bounded.
Our experimental results show that the centrality of networks with 125 nodes and 455 edges can be efficiently computed in 3.2 s. Not only the clustering results using the infinite betweenness centrality for this kind of networks are better, but also the nodes with biggest influences are more precisely detected when the betweenness centrality is computed over the periodic graph.
The algorithm provides a better result for temporal social networks with an acceptable running time.
虽然时间网络在机会通信等领域有广泛应用，但专门针对它们提出的聚类算法并不多。
基于周期图的中介中心性，我们给出了一种时间网络的聚类伪多项式时间算法，其中传递值始终为正，且所有传递值的最小公倍数是有界的。
我们的实验结果表明，对于具有125个节点和455条边的网络，其中心性可在3.2秒内有效计算出来。不仅使用这种网络的无限中介中心性得到的聚类结果更好，而且在周期图上计算中介中心性时，能更精确地检测到具有最大影响力的节点。
该算法在可接受的运行时间内为时间社交网络提供了更好的结果。
