Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2018 | OriginalPaper | Chapter

1. Introduction

Authors : Lijun Chang, Lu Qin

Published in: Cohesive Subgraph Computation over Large Sparse Graphs

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
next chapter Linear Heap Data Structures
Footnotes
Literature
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.
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.
Metadata
Title
Introduction
Authors
Lijun Chang
Lu Qin
Copyright Year
2018
Book
Cohesive Subgraph Computation over Large Sparse Graphs

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

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

Copyright Year: 2018

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

Premium Partner

    Image Credits