nach oben

Soft Computing

Erschienen in:

03.08.2020 | Methodologies and Application

Algorithm for determining the mutual impact of nodes in weighted directed graphs

verfasst von: Dmytro Lande, Oleh Dmytrenko, Minglei Fu, Minchao Hu, Dmytro Manko, Andrei Snarskii

Erschienen in: Soft Computing | Ausgabe 2/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Assembly sequence optimization based on hybrid symbiotic organisms search and ant colony optimization

Nächster Artikel A new compound wind speed forecasting structure combining multi-kernel LSSVM with two-stage decomposition technique

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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

Axelrod R (1976) Structure of decision. The cognitive maps of political elites. Princeton University Press, Princeton

Bauer F, Lizier JT (2012) Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: a walk counting approach. EPL (Europhys Lett). https://doi.org/10.1209/0295-5075/99/68007CrossRef

Bavelas A (1950) Communication patterns in task-oriented groups. J Acoust Soc Am 22(6):725–730CrossRef

Benamina M, Atmani B, Benbelkacem S (2018) Diabetes diagnosis by case-based reasoning and fuzzy logic. Int J Interact Multimed Artif Intell 5(3):72–80. https://doi.org/10.9781/ijimai.2018.02.001CrossRef

Borgatti SP (2005) Centrality and network flow. Social Netw 27(1):55–71. https://doi.org/10.1016/j.socnet.2004.11.008MathSciNetCrossRef

Borgatti SP, Everett MG (2006) A graph-theoretic perspective on centrality. Social Netw 28(4):466–484. https://doi.org/10.1016/j.socnet.2005.11.005CrossRef

Brandes U (2001) A faster algorithm for betweenness centrality. J Math Sociol 25(2):163–177. https://doi.org/10.1080/0022250x.2001.9990249CrossRefMATH

Brandes U, Borgatti SP, Freeman LC (2016) Maintaining the duality of closeness and betweenness centrality. Social Netw 44:153–159. https://doi.org/10.1016/j.socnet.2015.08.003CrossRef

Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. Comput Netw ISDN Syst 30(1–7):107–117. https://doi.org/10.1016/s0169-7552(98)00110-xCrossRef

Butts CT (2006) Exact bounds for degree centralization. Social Netw 28(4):283–296. https://doi.org/10.1016/j.socnet.2005.07.003CrossRef

Coombs CH, Dawes RM, Tversky A (1970) Mathematical psychology: an elementary introduction. Prentice-Hall, Englewood Cliffs, N.J.MATH

Cueva-Fernandez G, Espada JP, García-Díaz V, Crespo RG (2016) Fuzzy system to adapt web voice interfaces dynamically in a vehicle sensor tracking application definition. Soft Comput 20(8):3321–3334. https://doi.org/10.1007/s00500-015-1709-2CrossRef

Da Silva RAP, Viana MP, da Fontoura Costa L (2012) Predicting epidemic outbreak from individual features of the spreaders. J Stat Mech Theory Exp. https://doi.org/10.1088/1742-5468/2012/07/p07005CrossRefMATH

Dmytrenko OO, Lande DV (2018) The algorithm of accumulated mutual influence of the nodes in semantic networks. arXiv:1804.07251

Ellinas C, Allan N, Durugbo C, Johansson A (2015) How robust is your project? From local failures to global catastrophes: a complex networks approach to project systemic risk. PloS One. https://doi.org/10.1371/journal.pone.0142469CrossRef

Faghani MR, Nguyen UT (2013) A study of XSS worm propagation and detection mechanisms in online social networks. IEEE Trans Inf Fore Secur 8(11):1815–1826. https://doi.org/10.1109/tifs.2013.2280884CrossRef

Fenton FH, Luther S, Cherry EM, Otani NF, Krinsky V, Pumir A, Bodensch ER, Gilmour RF (2009) Termination of atrial fibrillation using pulsed low-energy far-field stimulation. Circulation 120(6):467–476. https://doi.org/10.1161/circulationaha.108.825091CrossRef

Freeman LC (1977) A set of measures of centrality based on betweenness. Sociometry 40(1):35–41CrossRef

Freeman LC (1978) Centrality in social networks conceptual clarification. Social Netw 1(3):215–239CrossRef

Homenda W, Jastrzebska A, Pedrycz W (2014) Time series modeling with fuzzy cognitive maps: simplification strategies. Computer Information Systems and Industrial Management. Springer, Berlin. https://doi.org/10.1007/978-3-662-45237-0_38CrossRefMATH

Jordan LA, Maguire SM, Hofmann HA, Kohda M (2016) The social and ecological costs of an ‘over-extended’ phenotype. Proc R Soc B Biol Sci. https://doi.org/10.1098/rspb.2015.2359CrossRef

Katz L (1953) A new status index derived from sociometric analysis. Psychometrika 18(1):39–43. https://doi.org/10.1007/bf02289026CrossRefMATH

Kleinberg JM (1998) Authoritative sources in a hyperlinked environment. Proc ACM-SIAM Symp Discrete Algorithms 46(5):604–632MathSciNetMATH

Klemm K, Serrano MÁ, Eguíluz VM, San Miguel M (2012) A measure of individual role in collective dynamics. Sci Rep 2:292. https://doi.org/10.1038/srep00292CrossRef

Kulinich AA (2014) Software systems for situation analysis and decision support on the basis of cognitive maps: approaches and methods. Autom Remote Control 75(7):1337–1355. https://doi.org/10.1134/s0005117914070157CrossRefMATH

Langville AN, Meyer CD (2011) Google’s PageRank and beyond: the science of searchengine rankings. Princeton University Press. https://doi.org/10.1007/bf02985759CrossRefMATH

Lawyer G (2014) Technical report: performance of the expected force on AS-level inernet topologies. Preprint arXiv:1406.4785

Lawyer G (2015) Understanding the influence of all nodes in a network. Sci Rep. https://doi.org/10.1038/srep08665CrossRef

Lawyer G (2016) Measuring the potential of individual airports for pandemic spread over the world airline network. BMC Infect Dis 16(1):70. https://doi.org/10.1186/s12879-016-1350-4CrossRef

Leskovec J, Anand R, Jeffrey DU (2014) Mining of massive datasets. Cambridge University Press. https://doi.org/10.1017/cbo9781139924801.002CrossRef

Maio CD, Fenza G, Loia V, Orciuoli F (2017) Making sense of cloud-sensor data streams via fuzzy cognitive maps and temporal fuzzy concept analysis. Neurocomputing. https://doi.org/10.1016/j.neucom.2016.06.090CrossRefMATH

Maruyama M (1963) The second cybernetics: deviation-amplifying mutual causal processes. Am Sci 51(2):164–179. https://doi.org/10.2307/27838689CrossRef

Milkau U, Bott J (2015) Digitalisation in payments: from interoperability to centralised models? J Paym Strategy Syst 9(3):321–340

Negre CF, Morzan UN, Hendrickson HP, Pal R, Lisi GP, Loria JP, Batista VS (2018) Eigenvector centrality for characterization of protein allosteric pathways. Proc Natl Acad Sci 115(52):E12201–E12208. https://doi.org/10.1073/pnas.1810452115CrossRef

Newman ME (2003) The structure and function of complex networks. SIAM Review 45(2):167–256. https://doi.org/10.1137/s003614450342480MathSciNetCrossRefMATH

Özesmi U, Özesmi SL (2004) Ecological models based on people’s knowledge: a multi-step fuzzy cognitive mapping approach. Ecol Model 176(1–2):43–64. https://doi.org/10.1016/j.ecolmodel.2003.10.027CrossRef

Page L, Brin S, Motwani R, Winograd T (1997) PageRank: bringing order to the web, Stanford Digital Libraries Working Paper, vol 72

Pereira VH, Gama MCT, Sousa FAB, Lewis TG, Gobatto CA, Manchado-Gobatto FB (2015) Complex network models reveal correlations among network metrics, exercise intensity and role of body changes in the fatigue process. Sci Rep. https://doi.org/10.1038/srep10489CrossRef

Piraveenan M, Prokopenko M, Hossain L (2013) Percolation centrality: quantifying graph-theoretic impact of nodes during percolation in networks. PloS One. https://doi.org/10.1371/journal.pone.0053095CrossRef

Revanasiddappa MB, Harish BS (2018) A new feature selection method based on intuitionistic fuzzy entropy to categorize text documents. Int J Interact Multimed Artif Intell 5(6):106–117. https://doi.org/10.9781/ijimai.2018.04.002CrossRef

Roberts F (1976) Discrete mathematical models with applications to social, biological, and environmental problems. Am Math Mon. https://doi.org/10.2307/2322080CrossRefMATH

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. https://doi.org/10.1109/idaacs.2017.8094500

Rueda DF, Calle E, Marzo JL (2017) Robustness comparison of 15 real telecommunication networks: structural and centrality measurements. J Netw Syst Manage 25(2):269–289. https://doi.org/10.1007/s10922-016-9391-yCrossRef

Sabidussi G (1966) The centrality index of a graph. Psychometrika 31(4):581–603MathSciNetCrossRef

Sadovnichiy VA, Zgurovsky MZ (2016) Advances in dynamical systems and control. Springer, Cham. https://doi.org/10.1007/978-3-319-40673-2CrossRefMATH

Snarskii AA, Zorinets DI, Lande DV, Levchenko AV (2016) K-method of cognitive mapping analysis. arXiv:1605.08243

Snarskii AA, Lande DV, Manko DY (2019) A new method (K-method) of calculating the mutual influence of nodes indirected weight complex networks. Phys A Stat Mech Appl. https://doi.org/10.1016/j.physa.2019.04.135CrossRef

Travençolo BAN, Costa LDF (2008) Accessibility in complex networks. Phys Lett A 373(1):89–95. https://doi.org/10.1016/j.physleta.2008.10.069CrossRefMATH

Viana MP, Batista JL, Costa LDF (2012) Effective number of accessed nodes in complex networks. Phys Rev E. https://doi.org/10.1103/physreve.85.036105CrossRef

Zgurovsky MZ, Romanenko VD, Milyavsky YL (2016) Adaptive control of impulse processes in complex systems cognitive maps with multirate coordinates sampling. Advances in Dynamical Systems and Control. Springer, Cham, pp 363–374. https://doi.org/10.1007/978-3-319-40673-2_19CrossRefMATH

Zhang H, Liu G, Li S, Ye J (2018) Single-atom catalysts: emerging multifunctional materials in heterogeneous catalysis. Adv Energy Mater. https://doi.org/10.1002/aenm.201701343CrossRef

Zhao X, Liu FA, Wang J, Li T (2017) Evaluating influential nodes in social networks by local centrality with a coefficient. ISPRS Int J Geo-Inf 6(2):35. https://doi.org/10.3390/ijgi6020035CrossRef

Titel: Algorithm for determining the mutual impact of nodes in weighted directed graphs
verfasst von: Dmytro Lande
Oleh Dmytrenko
Minglei Fu
Minchao Hu
Dmytro Manko
Andrei Snarskii
Publikationsdatum: 03.08.2020
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 2/2021
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-020-05232-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2021

Entropy measure and TOPSIS method based on correlation coefficient using complex q-rung orthopair fuzzy information and its application to multi-attribute decision making

A general approach to fuzzy regression models based on different loss functions

Population-based Tabu search with evolutionary strategies for permutation flow shop scheduling problems under effects of position-dependent learning and linear deterioration

A novel two-stage optimized model for logo-based document image retrieval based on a soft computing framework

Locally -complete and locally complete EMV-algebras

Development of smart controller for demand side management in smart grid using reactive power optimization

Premium Partner