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
Knowledge and Information Systems
Erschienen in: Knowledge and Information Systems 1/2019

19.12.2018 | Regular Paper

Scalable approximations to k-cycle transversal problems on dynamic networks

verfasst von: Alan Kuhnle, Victoria G. Crawford, My T. Thai

Erschienen in: Knowledge and Information Systems | Ausgabe 1/2019

Einloggen

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

search-config
loading …

Abstract

We study scalable approximation algorithms for the k-cycle transversal problem, which is to find a minimum-size set of edges that intersects all simple cycles of length k in a network. This problem is relevant to network reliability through the important metric of network clustering coefficient of order k. We formulate two algorithms to be both scalable and have good solution quality in practice: CARL and DARC. DARC is able to efficiently update its solution under dynamic node and edge insertion and removal to the network. In our experimental evaluation, we demonstrate that DARC is able to run on networks with billions of 3-cycles within 2 h and is able to dynamically update its solution in microseconds.
Vorheriger Artikel Autonomic workload performance tuning in large-scale data repositories
Nächster Artikel Two-hop privacy-preserving nearest friend searches

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
Fußnoten
1
The conference version of this paper studied the 3-cycle (triangle) version of this problem [15].
 
Literatur
1.
Arulselvan A, Commander CW, Elefteriadou L, Pardalos PM (2009) Detecting critical nodes in sparse graphs. Comput Oper Res 36(7):2193–2200MathSciNetCrossRefMATH
2.
Bafna V, Berman P, Fujito T (1999) A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J Discrete Math 12(3):289–297MathSciNetCrossRefMATH
3.
Barclay KJ, Edling C, Rydgren J (2013) Peer clustering of exercise and eating behaviours among young adults in Sweden: a cross-sectional study of egocentric network data. BMC Public Health 13:1–3CrossRef
4.
Bhattacharya S (2017) Fully dynamic approximate maximum matching and minimum vertex cover in O ( log 3 n ) worst case update time. In: Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete algorithms (SODA’17), (340506), pp 470–489
5.
Bhattacharya S, Henzinger M, Italiano GF (2015) Design of dynamic algorithms via primal–dual method. In: International colloquium on automata, languages, and programming. Lecture notes in computer science, vol 9134, pp 206–218
6.
Caldarelli G, Pastor-Satorras R, Vespignani A (2004) Structure of cycles and local ordering in complex networks. Eur Phys J B 38(2):183–186CrossRef
7.
Centola D (2010) The spread of behavior in an online social network experiment. Science 329(5996):1194–1197CrossRef
8.
Centola D (2011) An experimental study of homophily in the adoption of health behavior. Science 334(December):1269–1272CrossRef
9.
Cui Y, Xiao D, Loguinov D (2016) On efficient external-memory triangle listing. In: IEEE 16th international conference on data mining. IEEEj
10.
Grubesic TH, Matisziw TC, Murray AT, Snediker D (2008) Comparative approaches for assessing network vulnerability. Int Reg Sci Rev 31(1):88–112CrossRef
11.
Gupta A, Krishnaswamy R, Kumar A, Panigrahi D (2017) Online and dynamic algorithms for set cover. In: Symposium on the theory of computing (STOC), pp 537–550
12.
Guruswami V, Lee E (2014) Inapproximability of feedback vertex set for bounded length cycles. In: Electronic colloquium on computation complexity (ECCC), vol 21, p 2
13.
14.
15.
Kuhnle A, Crawford VG, Thai MT (2017a) Scalable and adaptive algorithms for the triangle interdiction problem on billion-scale networks. In: IEEE international conference on data mining (ICDM)
16.
Kuhnle A, Pan T, Crawford VG, Alim MA, Thai MT (2017b) Pseudo-separation for assessment of structural vulnerability of a network. In: Proceedings of the 2017 ACM SIGMETRICS/international conference on measurement and modeling of computer systems
17.
Kuhnle A, Nguyen NP, Dinh TN, Thai MT (2017c) Vulnerability of clustering under node failure in complex networks. Soc Netw Anal Min 7:8
18.
19.
20.
Lind PG, Gonzãlez MC, Herrmann HJ (2005) Cycles and clustering in bipartite networks. Phys Rev E Stat Nonlinear Soft Matter Phys 72(5):1–9
21.
Myers SA, Leskovec J (2014) The bursty dynamics of the Twitter information network. In: Proceedings of the 23rd international conference on world wide web, pp 913–924
22.
Nguyen HT, Nguyen NP, Vu T, Hoang HX, Dinh TN (2017) Transitivity demolition and the fall of social networks. IEEE Access 5:15913–15926CrossRef
23.
Nguyen NP, Dinh TN, Shen Y, Thai MT (2014) Dynamic social community detection and its applications. PLoS ONE 9(4):e91431CrossRef
24.
Onnela JP, Saramäki J, Kertész J, Kaski K (2005) Intensity and coherence of motifs in weighted complex networks. Phys Rev E Stat Nonlinear Soft Matter Phys 71(6):1–4CrossRef
25.
O’Sullivan DJP, O’Keeffe GJ, Fennell PG, Gleeson JP (2015) Mathematical modeling of complex contagion on clustered networks. Front Phys 3:71
26.
Ponton J, Wei P, Sun D (2013) Weighted clustering coefficient maximization for air transportation networks. In: IEEE European control conference (ECC)
27.
Schank T, Wagner D (2005) Finding, counting and listing all triangles in large graphs, an experimental study. In: International workshop on experimental and efficient algorithms 2. Springer, Berlin, pp 606–609
28.
Tsourakakis CE (2008) Fast counting of triangles in large real networks. In: Eighth IEEE international conference on data mining (ICDM). IEEE
29.
Vazirani VV (2003) Approximation algorithms, 1st edn. Springer, BerlinCrossRef
30.
Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks. Nature 393(6684):440–442CrossRefMATH
31.
Zaki N, Efimov D, Berengueres J (2013) Protein complex detection using interaction reliability assessment and weighted clustering coefficient. BMC Bioinform 14(1):1–9CrossRef
Metadaten
Titel
Scalable approximations to k-cycle transversal problems on dynamic networks
verfasst von
Alan Kuhnle
Victoria G. Crawford
My T. Thai
Publikationsdatum
19.12.2018
Verlag
Springer London
Erschienen in
Knowledge and Information Systems / Ausgabe 1/2019
Print ISSN: 0219-1377
Elektronische ISSN: 0219-3116
DOI
https://doi.org/10.1007/s10115-018-1296-5

Weitere Artikel der Ausgabe 1/2019

Knowledge and Information Systems 1/2019 Zur Ausgabe

Regular Paper

HIME: discovering variable-length motifs in large-scale time series

Regular Paper

Conditional adjacency anonymity in social graphs under active attacks

Regular Paper

Coordination with erroneous communication: results of an agent-based simulation

Regular Paper

AutoRepair: an automatic repairing approach over multi-source data

Regular Paper

Effective and efficient location influence mining in location-based social networks

Regular Paper

A graph-based meta-model for heterogeneous data management