Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Soft Computing
Erschienen in: Soft Computing 19/2017

11.08.2016 | Foundations

Critical node identification for complex network based on a novel minimum connected dominating set

verfasst von: Fahong Yu, Xiaoyun Xia, Wenping Li, Jiang Tao, Longhua Ma, Zhao-quan Cai

Erschienen in: Soft Computing | Ausgabe 19/2017

Einloggen

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

search-config
loading …

Abstract

Identifying critical nodes in complex networks aims to fragment a graph \(G = (V, E)\) by removing a set of vertices R with cardinality \(\left| R \right| \le \) k, such that the residual graph has minimum pairwise connectivity. Existing optimization algorithms are incapable of finding a good set R in complex networks. By investigating the role of nodes, a minimum dominating set approach is considered in controlling a network. This paper presents an algorithmic procedure to compute the critical nodes using a novel minimum connected dominating set, in which the critical nodes are identified based on the number of close subsequences. Through experimental verification on some randomly generated networks and comparing with the similar algorithms, the results showed that the proposed algorithm has high capability of identifying the critical nodes and low time complexity.
Vorheriger Artikel Using mixed mode programming to parallelize an indicator-based evolutionary algorithm for inferring multiobjective phylogenetic histories
Nächster Artikel The decomposition of linearly ordered pseudo-hoops

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
Literatur
Agrawal D, Budak C, Abbadi AE (2011) Information diffusion in social networks: observing and influencing societal interests. In: 2011 Proceedings of the VLDB endowment. IEEE, pp 1512–1518
Balaji S, Revathi N (2012) An efficient heuristic for the minimum connected dominating set problem on ad hoc wireless networks. World Acad Sci Eng Technol 6(9):8–22
Barabsi A-L, Bonabeau E (2003) Scale-free networks. Sci Am 6(9):50–59
Callaway DS, Newman MEJ, Strogatz SH, Watts DJ (2000) Network robustness and fragility: percolation on random graphs. Phys Rev Lett 85(25):5468–5471CrossRef
Cao YJ, Ding LJ, Wang GZ, Bao ZJ, Han ZX (2009) Analysis on cascading failure and self-organized criticality in evolving power grids. Autom Electr Power Syst 33(5):1–6
Chakradhar P, Yogesh P (2014) Energy efficient minimum connected dominating set algorithm for manets. Int Conf Recent Trends Inf Technol 7(9):270–282
Chamodrakas I, Martakos D (2015) An improved algorithm for minimum connected dominating sets in ad hoc networks. ICIC Express Lett 13(5):202–209
Chen H, Xu J, Wang G, Qin Y, Chau M, Chung W (2004) Crime data mining: a general framework and some examples. Computer 4(37):50–56CrossRef
Dan X, Xiao-Fan W, Xiang L (2010) An investigation on local area control of virus spreading in complex networks. Acta Phys 13(3):1313–1317
Ding D (2012) Identification of crucial nodes in biological networks. Netw Biol 15(3):118–127
Firmani D, Italiano GF, Laura L (2015) The (not so) critical nodes of criminal networks. Soc Inf 8(3):87–96
Freeman LC (1998) Centrality in social networks. Soc Netw 14(7):1170–1182
Girvan M, Newman MEJ (2006) Community structure in social and biological networks. PhysRevE 8(4):147–160MATH
Kinney R, Albert R, Latora V, Crucitti P (2005) Modeling cascading failures in the North American power grid. Eur Phys J B 46(9):101–107
Lu TYXWYHSB, Piao XF (2012) Energy efficient minimum connected dominating set algorithm for manets. Acta Phys 61(9):170–179
Nguyen DT, Shen Y, Thai MT (2013) Detecting critical nodes in interdependent power networks for vulnerability assessment. IEEE Trans Smart Grid 11(9):151–159CrossRef
Shen Y, Nguyen NP, Xuan Y, Thai MT (2014) On the discovery of critical links and nodes for assessing network vulnerability. IEEE/ACM Trans Netw 21(3):963–973CrossRef
Sweet N, Kanefsky S (2013) The c2 constellation air force network centric warfare program. In: 2013 Command and control research and technology symposium. IEEE, pp 563–571
Ventresca M, Aleman D (2015) Efficiently identifying critical nodes in large complex networks. Comput Soc Netw 6(2):179–188
Ventresca M, Ombuki-Berman BM, Harrison KR (2015) An experimental evaluation of multi-objective evolutionary algorithms for detecting critical nodes in complex networks. Appl Evol Comput 7(3):164–176
Veremyev A, Pasiliao EL, Boginski V (2014) Exact identification of critical nodes in sparse networks via new compact formulations. Optim Lett 8(5):1245–1259MathSciNetCrossRefMATH
Vida R, Cuenda S, Galeano J (2013) Identifying critical nodes in multi-layered networks under multi-vector malware attack. Int J Complex Syst Sci 3(5):97–105
Wang XG (2014) An algorithm for critical nodes problem in social networks based on owen value. Sci World J 15(10):72–82
Wang P, Lu J, Yu X (2014) Identification of important nodes in artificial bio-molecular networks. In: 2014 IEEE international symposium on circuits and systems. IEEE, pp 1267–1276
Xu J, Chen H (2005) Criminal network analysis and visualization. Commun ACM 48(6):100–107
Xu Y, Gao Z, Xiao B, Meng F, Lin Z (2013) key nodes evaluation with multi-criteria in complex networks based on ahp analysis. In: Proceedings of IEEE IC-BNMT2013. IEEE, pp 175–182
Yan-Chao Z, Hai-Feng Z, Hui C, Fei X, Yun L (2011) The research of information dissemination model on online social network. Acta Phys 60(16):171–179
Yan R, Tang J, Liu X, Shan D, Li X (2012) Citation count prediction: learning to estimate future citations for literature. In: Proceedings of the 20th ACM international conference on Information and knowledge management. IEEE, pp 1247–1252
Yong XXH (2015) Research on the dynamics of opinion spread based on social network services. Acta Phys 15(9):973–979
Yu G (2011) Novel connected dominating set algorithm based on minimum spanning tree. J Comput Appl 26(9):327–335
Zachary WW (1977) An information flow model for conflict and fission in small groups. J Anthropol Res 11(2):452–473CrossRef
Zhongtai C, Xiaohuan W, Ning M, Xiuqing S (2015) Key nodes identify in the peasants social network based on structural hole theory. Int J Hybrid Inf Technol 8(2):251–258
Zhu J, Yang XJ (2015) Recognizing key nodes in area communication network. Electron Inf Warf Technol 64(7):46–52
Metadaten
Titel
Critical node identification for complex network based on a novel minimum connected dominating set
verfasst von
Fahong Yu
Xiaoyun Xia
Wenping Li
Jiang Tao
Longhua Ma
Zhao-quan Cai
Publikationsdatum
11.08.2016
Verlag
Springer Berlin Heidelberg
Erschienen in
Soft Computing / Ausgabe 19/2017
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-016-2303-y

Weitere Artikel der Ausgabe 19/2017

Soft Computing 19/2017 Zur Ausgabe

Methodologies and Application

EL-hyperstructures associated to n-ary relations

Foundations

Convex congruences

Focus

Using mixed mode programming to parallelize an indicator-based evolutionary algorithm for inferring multiobjective phylogenetic histories

Methodologies and Application

Detection of content-aware image resizing based on Benford’s law

Focus

Since CEC 2005 competition on real-parameter optimisation: a decade of research, progress and comparative analysis’s weakness

Focus

Networks of picture processors as problem solvers