Algorithm for determining the mutual impact of nodes in weighted directed graphs. (English) Zbl 1491.05184
Summary: We propose an algorithm for computing the influence matrix and rank distribution of nodes of a weighted directed graph by calculating the nodes’ mutual impact. The algorithm of accumulative impact solves problems of dimension and computational complexity arising in the analysis of large complex systems. The algorithm calculates the mutual impact of each pair of vertices, making it possible to rank the nodes according to their importance within the system and to determine the most influential components. It produces results similar to those of the commonly used impulse method when applied to graphs that are impulse-stable in an impulse process, while overcoming the disadvantages of the impulse method in other situations. Results are always obtained regardless of impulse stability; they do not depend on the initial impulse, so that the initial values of the weights affect the calculation results. When elements in the adjacency matrix of the weighted directed graph are multiplied by a constant factor, scale invariance is not violated, and the full affect for each of the nodes scales proportionally. Several examples of analyses of weighted directed graphs, including one related to the practical problem of urban solid waste removal, are provided to demonstrate the advantages of the proposed algorithm.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C22 | Signed and weighted graphs |
Keywords:
complex system; weighted directed graph; influence matrix; accumulative impact; rank distribution of nodesReferences:
| [1] | Austin D (2006) How Google finds your needle in the web’s haystack. Am Math Soc. http://www.ams.org/publicoutreach/feature-column/fcarc-pagerank |
| [2] | Axelrod, R., Structure of decision. The cognitive maps of political elites (1976), Princeton: Princeton University Press, Princeton |
| [3] | Bauer, F.; Lizier, JT, Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: a walk counting approach, EPL (Europhys Lett) (2012) · doi:10.1209/0295-5075/99/68007 |
| [4] | Bavelas, A., Communication patterns in task-oriented groups, J Acoust Soc Am, 22, 6, 725-730 (1950) · doi:10.1121/1.1906679 |
| [5] | Benamina, M.; Atmani, B.; Benbelkacem, S., Diabetes diagnosis by case-based reasoning and fuzzy logic, Int J Interact Multimed Artif Intell, 5, 3, 72-80 (2018) · doi:10.9781/ijimai.2018.02.001 |
| [6] | Borgatti, SP, Centrality and network flow, Social Netw, 27, 1, 55-71 (2005) · doi:10.1016/j.socnet.2004.11.008 |
| [7] | Borgatti, SP; Everett, MG, A graph-theoretic perspective on centrality, Social Netw, 28, 4, 466-484 (2006) · doi:10.1016/j.socnet.2005.11.005 |
| [8] | Brandes, U., A faster algorithm for betweenness centrality, J Math Sociol, 25, 2, 163-177 (2001) · Zbl 1051.91088 · doi:10.1080/0022250x.2001.9990249 |
| [9] | Brandes, U.; Borgatti, SP; Freeman, LC, Maintaining the duality of closeness and betweenness centrality, Social Netw, 44, 153-159 (2016) · doi:10.1016/j.socnet.2015.08.003 |
| [10] | Brin, S.; Page, L., The anatomy of a large-scale hypertextual web search engine, Comput Netw ISDN Syst, 30, 1-7, 107-117 (1998) · doi:10.1016/s0169-7552(98)00110-x |
| [11] | Butts, CT, Exact bounds for degree centralization, Social Netw, 28, 4, 283-296 (2006) · doi:10.1016/j.socnet.2005.07.003 |
| [12] | Coombs, CH; Dawes, RM; Tversky, A., Mathematical psychology: an elementary introduction (1970), Englewood Cliffs, N.J.: Prentice-Hall, Englewood Cliffs, N.J. · Zbl 0205.23701 |
| [13] | Cueva-Fernandez, G.; Espada, JP; García-Díaz, V.; Crespo, RG, Fuzzy system to adapt web voice interfaces dynamically in a vehicle sensor tracking application definition, Soft Comput, 20, 8, 3321-3334 (2016) · doi:10.1007/s00500-015-1709-2 |
| [14] | Da Silva, RAP; Viana, MP; da Fontoura Costa, L., Predicting epidemic outbreak from individual features of the spreaders, J Stat Mech Theory Exp (2012) · doi:10.1088/1742-5468/2012/07/p07005 |
| [15] | Dmytrenko OO, Lande DV (2018) The algorithm of accumulated mutual influence of the nodes in semantic networks. arXiv:1804.07251 |
| [16] | Ellinas, C.; Allan, N.; Durugbo, C.; Johansson, A., How robust is your project? From local failures to global catastrophes: a complex networks approach to project systemic risk, PloS One (2015) · doi:10.1371/journal.pone.0142469 |
| [17] | Faghani, MR; Nguyen, UT, A study of XSS worm propagation and detection mechanisms in online social networks, IEEE Trans Inf Fore Secur, 8, 11, 1815-1826 (2013) · doi:10.1109/tifs.2013.2280884 |
| [18] | Fenton, FH; Luther, S.; Cherry, EM; Otani, NF; Krinsky, V.; Pumir, A.; Bodensch, ER; Gilmour, RF, Termination of atrial fibrillation using pulsed low-energy far-field stimulation, Circulation, 120, 6, 467-476 (2009) · doi:10.1161/circulationaha.108.825091 |
| [19] | Freeman, LC, A set of measures of centrality based on betweenness, Sociometry, 40, 1, 35-41 (1977) · doi:10.2307/3033543 |
| [20] | Freeman, LC, Centrality in social networks conceptual clarification, Social Netw, 1, 3, 215-239 (1978) · doi:10.1016/0378-8733(78)90021-7 |
| [21] | Homenda, W.; Jastrzebska, A.; Pedrycz, W., Time series modeling with fuzzy cognitive maps: simplification strategies (2014), Berlin: Springer, Berlin · Zbl 1410.91170 · doi:10.1007/978-3-662-45237-0_38 |
| [22] | Jordan, LA; Maguire, SM; Hofmann, HA; Kohda, M., The social and ecological costs of an ‘over-extended’ phenotype, Proc R Soc B Biol Sci (2016) · doi:10.1098/rspb.2015.2359 |
| [23] | Katz, L., A new status index derived from sociometric analysis, Psychometrika, 18, 1, 39-43 (1953) · Zbl 0053.27606 · doi:10.1007/bf02289026 |
| [24] | Kleinberg, JM, Authoritative sources in a hyperlinked environment, Proc ACM-SIAM Symp Discrete Algorithms, 46, 5, 604-632 (1998) · Zbl 1065.68660 |
| [25] | Klemm, K.; Serrano, MÁ; Eguíluz, VM; San Miguel, M., A measure of individual role in collective dynamics, Sci Rep, 2, 292 (2012) · doi:10.1038/srep00292 |
| [26] | Kulinich, AA, Software systems for situation analysis and decision support on the basis of cognitive maps: approaches and methods, Autom Remote Control, 75, 7, 1337-1355 (2014) · Zbl 1325.93020 · doi:10.1134/s0005117914070157 |
| [27] | Langville, AN; Meyer, CD, Google’s PageRank and beyond: the science of searchengine rankings, Princeton University Press (2011) · Zbl 1270.68005 · doi:10.1007/bf02985759 |
| [28] | Lawyer G (2014) Technical report: performance of the expected force on AS-level inernet topologies. Preprint arXiv:1406.4785 |
| [29] | Lawyer, G., Understanding the influence of all nodes in a network, Sci Rep (2015) · doi:10.1038/srep08665 |
| [30] | Lawyer, G., Measuring the potential of individual airports for pandemic spread over the world airline network, BMC Infect Dis, 16, 1, 70 (2016) · doi:10.1186/s12879-016-1350-4 |
| [31] | Leskovec, J.; Anand, R.; Jeffrey, DU, Mining of massive datasets, Cambridge University Press (2014) · doi:10.1017/cbo9781139924801.002 |
| [32] | Maio, CD; Fenza, G.; Loia, V.; Orciuoli, F., Making sense of cloud-sensor data streams via fuzzy cognitive maps and temporal fuzzy concept analysis, Neurocomputing (2017) · Zbl 1429.91099 · doi:10.1016/j.neucom.2016.06.090 |
| [33] | Maruyama, M., The second cybernetics: deviation-amplifying mutual causal processes, Am Sci, 51, 2, 164-179 (1963) · doi:10.2307/27838689 |
| [34] | Milkau, U.; Bott, J., Digitalisation in payments: from interoperability to centralised models?, J Paym Strategy Syst, 9, 3, 321-340 (2015) |
| [35] | Negre, CF; Morzan, UN; Hendrickson, HP; Pal, R.; Lisi, GP; Loria, JP; Batista, VS, Eigenvector centrality for characterization of protein allosteric pathways, Proc Natl Acad Sci, 115, 52, E12201-E12208 (2018) · doi:10.1073/pnas.1810452115 |
| [36] | Newman, ME, The structure and function of complex networks, SIAM Review, 45, 2, 167-256 (2003) · Zbl 1029.68010 · doi:10.1137/s003614450342480 |
| [37] | Özesmi, U.; Özesmi, SL, Ecological models based on people’s knowledge: a multi-step fuzzy cognitive mapping approach, Ecol Model, 176, 1-2, 43-64 (2004) · doi:10.1016/j.ecolmodel.2003.10.027 |
| [38] | Page L, Brin S, Motwani R, Winograd T (1997) PageRank: bringing order to the web, Stanford Digital Libraries Working Paper, vol 72 |
| [39] | Pereira, VH; Gama, MCT; Sousa, FAB; Lewis, TG; Gobatto, CA; Manchado-Gobatto, FB, Complex network models reveal correlations among network metrics, exercise intensity and role of body changes in the fatigue process, Sci Rep (2015) · doi:10.1038/srep10489 |
| [40] | Piraveenan, M.; Prokopenko, M.; Hossain, L., Percolation centrality: quantifying graph-theoretic impact of nodes during percolation in networks, PloS One (2013) · doi:10.1371/journal.pone.0053095 |
| [41] | Revanasiddappa, MB; Harish, BS, A new feature selection method based on intuitionistic fuzzy entropy to categorize text documents, Int J Interact Multimed Artif Intell, 5, 6, 106-117 (2018) · doi:10.9781/ijimai.2018.04.002 |
| [42] | Roberts, F., Discrete mathematical models with applications to social, biological, and environmental problems, Am Math Mon (1976) · Zbl 0363.90002 · doi:10.2307/2322080 |
| [43] | Romanenko V, Milyavsky Y (2017) Combined control of impulse processes in complex systems’ cognitive maps with multirate sampling. In: IEEE international conference on intelligent data acquisition and advanced computing systems: technology and applications, IEEE, pp 8-13. doi:10.1109/idaacs.2017.8094500 |
| [44] | Rueda, DF; Calle, E.; Marzo, JL, Robustness comparison of 15 real telecommunication networks: structural and centrality measurements, J Netw Syst Manage, 25, 2, 269-289 (2017) · doi:10.1007/s10922-016-9391-y |
| [45] | Sabidussi, G., The centrality index of a graph, Psychometrika, 31, 4, 581-603 (1966) · Zbl 0152.22703 · doi:10.1007/BF02289527 |
| [46] | Sadovnichiy, VA; Zgurovsky, MZ, Advances in dynamical systems and control (2016), Cham: Springer, Cham · Zbl 1357.00036 · doi:10.1007/978-3-319-40673-2 |
| [47] | Snarskii AA, Zorinets DI, Lande DV, Levchenko AV (2016) K-method of cognitive mapping analysis. arXiv:1605.08243 |
| [48] | Snarskii, AA; Lande, DV; Manko, DY, A new method (K-method) of calculating the mutual influence of nodes indirected weight complex networks, Phys A Stat Mech Appl (2019) · Zbl 07566407 · doi:10.1016/j.physa.2019.04.135 |
| [49] | Travençolo, BAN; Costa, LDF, Accessibility in complex networks, Phys Lett A, 373, 1, 89-95 (2008) · Zbl 1226.05233 · doi:10.1016/j.physleta.2008.10.069 |
| [50] | Viana, MP; Batista, JL; Costa, LDF, Effective number of accessed nodes in complex networks, Phys Rev E (2012) · doi:10.1103/physreve.85.036105 |
| [51] | Zgurovsky, MZ; Romanenko, VD; Milyavsky, YL, Adaptive control of impulse processes in complex systems cognitive maps with multirate coordinates sampling, 363-374 (2016), Cham: Springer, Cham · Zbl 1359.93253 · doi:10.1007/978-3-319-40673-2_19 |
| [52] | Zhang, H.; Liu, G.; Li, S.; Ye, J., Single-atom catalysts: emerging multifunctional materials in heterogeneous catalysis, Adv Energy Mater (2018) · doi:10.1002/aenm.201701343 |
| [53] | Zhao, X.; Liu, FA; Wang, J.; Li, T., Evaluating influential nodes in social networks by local centrality with a coefficient, ISPRS Int J Geo-Inf, 6, 2, 35 (2017) · doi:10.3390/ijgi6020035 |
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.
