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
Erschienen in:
Buchtitelbild

2018 | OriginalPaper | Buchkapitel

1. Introduction

verfasst von : Lijun Chang, Lu Qin

Erschienen in: Cohesive Subgraph Computation over Large Sparse Graphs

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

With the rapid development of information technology such as social media, online communities, and mobile communications, huge volumes of digital data are accumulated with data entities involving complex relationships. These data are usually modelled as graphs in view of the simple yet strong expressive power of graph model; that is, entities are represented by vertices and relationships are represented by edges.

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 "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

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
Nächstes Kapitel Linear Heap Data Structures
Fußnoten
Literatur
1.
James Abello, Mauricio G. C. Resende, and Sandra Sudarsky. Massive quasi-clique detection. In Proc. of LATIN’02, pages 598–612, 2002.
3.
Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. Linear-time enumeration of maximal k-edge-connected subgraphs in large networks by random contraction. In Proc. CIKM’13, pages 909–918, 2013.
4.
Albert Angel, Nick Koudas, Nikos Sarkas, and Divesh Srivastava. Dense subgraph maintenance under streaming edge weight updates for real-time story identification. PVLDB, 5(6):574–585, 2012.
10.
Fei Bi, Lijun Chang, Xuemin Lin, and Wenjie Zhang. An optimal and progressive approach to online search of top-k influential communities. PVLDB, 11(9):1056–1068, 2018.
11.
S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang. Complex networks: Structure and dynamics. Physics Reports, 424(4–5):175–308, 2006.MathSciNetCrossRef
12.
Paolo Boldi and Sebastiano Vigna. The WebGraph framework I: Compression techniques. In Proc. of WWW’04, pages 595–601, 2004.
16.
Lijun Chang, Xuemin Lin, Lu Qin, Jeffrey Xu Yu, and Wenjie Zhang. Index-based optimal algorithms for computing Steiner components with maximum connectivity. In Proc. of SIGMOD’15, 2015.
17.
Lijun Chang, Jeffrey Xu Yu, Lu Qin, Xuemin Lin, Chengfei Liu, and Weifa Liang. Efficiently computing k-edge connected components via graph decomposition. In Proc. SIGMOD’13, pages 205–216, 2013.
18.
Moses Charikar. Greedy approximation algorithms for finding dense components in a graph. In Proc. APPROX’00, pages 84–95, 2000.
22.
Jonathan Cohen. Trusses: Cohesive subgraphs for social network analysis, 2008.
23.
Alessio Conte, Donatella Firmani, Caterina Mordente, Maurizio Patrignani, and Riccardo Torlone. Fast enumeration of large k-plexes. In Proc. of KDD’17, pages 115–124, 2017.
24.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009.
33.
David Gibson, Ravi Kumar, and Andrew Tomkins. Discovering large dense subgraphs in massive graphs. In Proc. of VLDB’05, pages 721–732, 2005.
35.
A. V. Goldberg. Finding a maximum density subgraph. Technical report, Berkeley, CA, USA, 1984.
41.
Xin Huang, Hong Cheng, Lu Qin, Wentao Tian, and Jeffrey Xu Yu. Querying k-truss community in large and dynamic graphs. In Proc. of SIGMOD’14, pages 1311–1322, 2014.
42.
Xin Huang, Laks V. S. Lakshmanan, and Jianliang Xu. Community search over big graphs: Models, algorithms, and opportunities. In Proc. of ICDE’17, pages 1451–1454, 2017.
46.
M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, and H. A. Makse. Identification of influential spreaders in complex networks. Nature Physics, 6:888–893, 2010.CrossRef
48.
Victor E. Lee, Ning Ruan, Ruoming Jin, and Charu C. Aggarwal. A survey of algorithms for dense subgraph discovery. In Managing and Mining Graph Data, pages 303–336. 2010.
49.
55.
F. D. Malliaros, M.-E. G. Rossi, and M. Vazirgiannis. Locating influential nodes in complex networks. Scientific Reports, 6, 2016.
57.
Fragkiskos D. Malliaros and Michalis Vazirgiannis. Graph-based text representations: Boosting text mining, nlp and information retrieval with graphs. In Proc. of EMNLP’17, 2017.
59.
David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. J. ACM, 30(3):417–427, 1983.MathSciNetCrossRef
71.
Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In Proc. of AAAI’15, 2015.
72.
François Rousseau and Michalis Vazirgiannis. Main core retention on graph-of-words for single-document keyword extraction. In Proc. of ECIR’15, pages 382–393, 2015.
73.
Yousef Saad. Iterative methods for sparse linear systems. SIAM, 2003.CrossRef
76.
Ahmet Erdem Sariyüce and Ali Pinar. Fast hierarchy construction for dense subgraphs. PVLDB, 10(3):97–108, 2016.
80.
Pablo San Segundo, Alvaro Lopez, and Panos M. Pardalos. A new exact maximum clique algorithm for large and massive sparse graphs. Computers & Operations Research, 66:81–94, 2016.MathSciNetCrossRef
81.
82.
Stephen B. Seidman and Brian L. Foster. A graph-theoretic generalization of the clique concept. The Journal of Mathematical Sociology, 6(1):139–154, 1978.MathSciNetCrossRef
84.
Mauro Sozio and Aristides Gionis. The community-search problem and how to plan a successful cocktail party. In Proc. of KDD’10, pages 939–948, 2010.
88.
Antoine J.-P. Tixier, Fragkiskos D. Malliaros, and Michalis Vazirgiannis. A graph degeneracy-based approach to keyword extraction. In Proc. of EMNLP’16, pages 1860–1870, 2016.
89.
Charalampos E. Tsourakakis. The k-clique densest subgraph problem. In Proc. of WWW’15, pages 1122–1132, 2015.
91.
Michalis Vazirgiannis. Graph of words: Boosting text mining tasks with graphs. In Proc. of WWW’17, page 1181, 2017.
92.
Jia Wang and James Cheng. Truss decomposition in massive networks. PVLDB, 5(9):812–823, 2012.
93.
Jim Webber. The top 5 use cases of graph databases (white paper), 2015.
99.
Long Yuan, Lu Qin, Xuemin Lin, Lijun Chang, and Wenjie Zhang. I/O efficient ECC graph decomposition via graph reduction. PVLDB, 9(7):516–527, 2016.
102.
Rui Zhou, Chengfei Liu, Jeffrey Xu Yu, Weifa Liang, Baichen Chen, and Jianxin Li. Finding maximal k-edge-connected subgraphs from a large graph. In Proc. of EDBT’12, 2012.
Metadaten
Titel
Introduction
verfasst von
Lijun Chang
Lu Qin
Copyright-Jahr
2018
Buch
Cohesive Subgraph Computation over Large Sparse Graphs

Print ISBN: 978-3-030-03598-3

Electronic ISBN: 978-3-030-03599-0

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-030-03599-0_1