Block matrix formulations for evolving networks. (English) Zbl 1362.05120
Summary: Many types of pairwise interactions take the form of a fixed set of nodes with edges that appear and disappear over time. In the case of discrete-time evolution, the resulting evolving network may be represented by a time-ordered sequence of adjacency matrices. We consider here the issue of representing the system as a single, higher-dimensional block matrix, built from the individual time slices. We focus on the task of computing network centrality measures. From a modeling perspective, we show that there is a suitable block formulation that allows us to recover dynamic centrality measures respecting time’s arrow. From a computational perspective, we show that the new block formulation leads to the design of more effective numerical algorithms. In particular, we describe matrix-vector product based algorithms that exploit sparsity. Results are given on realistic data sets.
MSC:
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 15A69 | Multilinear algebra, tensor calculus |
References:
| [1] | A. Alsayed and D. J. Higham, {\it Betweenness in time dependent networks}, Chaos Solitons Fractals, 72 (2015), pp. 35-48. · Zbl 1352.90020 |
| [2] | Z. Bai, D. Day, and Q. Ye, {\it ABLE: An adaptive block Lanczos method for non-Hermitian eigenvalue problems}, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 1060-1082. · Zbl 0932.65045 |
| [3] | M. Benzi, E. Estrada, and C. Klymko, {\it Ranking hubs and authorities using matrix functions}, Linear Algebra Appl., 438 (2013), pp. 2447-2474. · Zbl 1258.05067 |
| [4] | M. Benzi and C. Klymko, {\it Total communicability as a centrality measure}, J. Complex Netw., 1 (2013), pp. 124-149. |
| [5] | S. Boccaletti, G. Bianconi, R. Criado, C. I. D. Genio, J. Gómez-Garden͂es, M. Romance, I. Sendin͂a-Nadal, Z. Wang, and M. Zanin, {\it The structure and dynamics of multilayer networks}, Phys. Rep., 544 (2014), pp. 1-122. |
| [6] | S. P. Borgatti, {\it Centrality and network flow}, Soc. Networks, 27 (2005), pp. 55-71. |
| [7] | S. P. Borgatti and M. Everett, {\it A graph-theoretic framework for classifying centrality measures}, Soc. Networks, 28 (2006), pp. 466-484. |
| [8] | D. Calvetti, L. Reichel, and F. Sgallari, {\it Application of anti-Gauss quadrature rules in linear algebra}, in Applications and Computation of Orthogonal Polynomials, W. Gautschi, G. H. Golub, and G. Opfer, eds., Birkhäuser, Basel, 1999, pp. 41-56. · Zbl 0938.65075 |
| [9] | I. Chen, M. Benzi, H. H. Chang, and V. S. Hertzberg, {\it Dynamic communicability and epidemic spread: A case study on an empirical dynamic contact network}, J. Complex Netw. (2016), . |
| [10] | P. Erdös and A. Rényi, {\it On random graphs}, Publ. Math. Debrecen, 6 (1959), pp. 290-297. · Zbl 0092.15705 |
| [11] | E. Estrada and D. J. Higham, {\it Network properties revealed through matrix functions}, SIAM Rev., 52 (2010), pp. 696-714. · Zbl 1214.05077 |
| [12] | C. Fenu, D. Martin, L. Reichel, and G. Rodriguez, {\it Block Gauss and anti-Gauss quadrature with application to networks}, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1655-1684. · Zbl 1425.65063 |
| [13] | L. Freeman, {\it Centrality in networks: I. Conceptual clarification}, Soc. Networks, 1 (1979), pp. 215-239. |
| [14] | G. H. Golub and G. Meurant, {\it Matrices, Moments and Quadrature with Applications}, Princeton University Press, Princeton, NJ, 2010. · Zbl 1217.65056 |
| [15] | G. H. Golub and C. F. Van Loan, {\it Matrix Computations, 4th ed.}, Johns Hopkins University Press, Baltimore, MD, 2012. · Zbl 1268.65037 |
| [16] | T. Graham and S. Wright, {\it Discursive equality and everyday talk online: The impact of superparticipants}, J. Comput. Mediat. Commun., 19 (2014), pp. 625-642. |
| [17] | P. Grindrod and D. J. Higham, {\it A matrix iteration for dynamic network summaries}, SIAM Rev., 55 (2013), pp. 118-128. · Zbl 1262.91121 |
| [18] | P. Grindrod and D. J. Higham, {\it A dynamical systems view of network centrality}, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 470 (2014), 20130835. · Zbl 1371.90039 |
| [19] | P. Grindrod, D. J. Higham, and M. C. Parsons, {\it Bistability through triadic closure}, Internet Math., 8 (2012), pp. 402-423. · Zbl 1258.05115 |
| [20] | P. Grindrod, D. J. Higham, M. C. Parsons, and E. Estrada, {\it Communicability across evolving networks}, Phys. Rev. E, 83 (2011), 046120. |
| [21] | G. G. Grinstein, C. Plaisant, S. J. Laskowski, T. O’Connell, J. Scholtz, and M. A. Whiting, {\it Vast 2008 challenge: Introducing mini-challenges}, in Proceedings of the 2008 IEEE Symposium on Visual Analytics Science and Technology, IEEE, 2008, pp. 195-196. |
| [22] | P. Holme and J. Saramäki, {\it Temporal networks}, Phys. Rep., 519 (2012), pp. 97-125. |
| [23] | D. Huffaker, J. Wang, J. Treem, M. Ahmad, L. Fullerton, D. Williams, M. Poole, and N. Contractor, {\it The social behaviors of experts in massive multiplayer online role-playing games}, in Proceedings of the 2009 International Conference on Computational Science and Engineering, IEEE, 2009, pp. 326-331. |
| [24] | L. Katz, {\it A new index derived from sociometric data analysis}, Psychometrika, 18 (1953), pp. 39-43. · Zbl 0053.27606 |
| [25] | M. Kivelä, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno, and M. A. Porter, {\it Multilayer networks}, J. Complex Netw., 2 (2014), pp. 203-271. |
| [26] | T. G. Kolda and B. W. Bader, {\it Tensor decompositions and applications}, SIAM Rev., 51 (2009), pp. 455-500. · Zbl 1173.65029 |
| [27] | P. Laflin, A. V. Mantzaris, P. Grindrod, F. Ainley, A. Otley, and D. J. Higham, {\it Discovering and validating influence in a dynamic online social network}, Soc. Netw. Anal. Min., 3 (2013), pp. 1311-1323. |
| [28] | D. P. Laurie, {\it Anti-Gaussian quadrature formulas}, Math. Comp., 65 (1996), pp. 739-747. · Zbl 0843.41020 |
| [29] | A. V. Mantzaris and D. J. Higham, {\it Asymmetry through time dependency}, Eur. Phys. J. B, 89 (2016), pp. 1-8. |
| [30] | S. Ragnarsson and C. F. Van Loan, {\it Block tensor unfoldings}, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 149-169. · Zbl 1246.15028 |
| [31] | V. Sekara, A. Stopczynski, and S. Lehmann, {\it Fundamental structures of dynamic social networks}, Proc. Natl. Acad. Sci. USA, 113 (2016), pp. 9977-9982. |
| [32] | L. Solá, M. Romance, R. Criado, J. Flores, A. García del Amo, and S. Boccaletti, {\it Eigenvector centrality of nodes in multiplex networks}, Chaos, 23 (2013), 033131. · Zbl 1323.05117 |
| [33] | A. Taylor and D. J. Higham, {\it CONTEST: A controllable test matrix toolbox for MATLAB}, ACM Trans. Math. Software, 35 (2009), 26. |
| [34] | D. Taylor, S. A. Myers, A. Clauset, M. A. Porter, and P. J. Mucha, {\it Eigenvector-based centrality measures for temporal networks}, SIAM J. Multiscale Model. Simul., 15, pp. 537-574, . · Zbl 1386.91116 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
