RESUMEN
This paper presents the benefits of using the random-walk normalized Laplacian matrix as a graph-shift operator and defines the frequencies of a graph by the eigenvalues of this matrix. A criterion to order these frequencies is proposed based on the Euclidean distance between a graph signal and its shifted version with the transition matrix as shift operator. Further, the frequencies of a periodic graph built through the repeated concatenation of a basic graph are studied. We show that when a graph is replicated, the graph frequency domain is interpolated by an upsampling factor equal to the number of replicas of the basic graph, similarly to the effect of zero-padding in digital signal processing.
RESUMEN
BACKGROUND: While the temporal networks have a wide range of applications such as opportunistic communication, there are not many clustering algorithms specifically proposed for them. METHODS: 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. RESULTS: 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. CONCLUSION: The algorithm provides a better result for temporal social networks with an acceptable running time.