kth.sePublications KTH
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Discovering Dense Correlated Subgraphs in Dynamic Networks
ISI Fdn, Turin, Italy..
Amazon, Tokyo, Japan..
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5211-112X
Univ Trento, Utrecht, Netherlands.;Univ Utrecht, Utrecht, Netherlands..
2021 (English)In: Advances In Knowledge Discovery And Data Mining, PAKDD 2021, Pt I / [ed] Karlapalem, K Cheng, H Ramakrishnan, N Agrawal, RK Reddy, PK Srivastava, J Chakraborty, T, Springer Nature , 2021, Vol. 12712, p. 395-407Conference paper, Published paper (Refereed)
Abstract [en]

Given a dynamic network, where edges appear and disappear over time, we are interested in finding sets of edges that have similar temporal behavior and form a dense subgraph. Formally, we define the problem as the enumeration of the maximal subgraphs that satisfy specific density and similarity thresholds. To measure the similarity of the temporal behavior, we use the correlation between the binary time series that represent the activity of the edges. For the density, we study two variants based on the average degree. For these problem variants we enumerate the maximal subgraphs and compute a compact subset of subgraphs that have limited overlap. We propose an approximate algorithm that scales well with the size of the network, while achieving a high accuracy. We evaluate our framework on both real and synthetic datasets. The results of the synthetic data demonstrate the high accuracy of the approximation and show the scalability of the framework.

Place, publisher, year, edition, pages
Springer Nature , 2021. Vol. 12712, p. 395-407
Series
Lecture Notes in Artificial Intelligence, ISSN 0302-9743
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-306446DOI: 10.1007/978-3-030-75762-5_32ISI: 000719253600032Scopus ID: 2-s2.0-85111157988OAI: oai:DiVA.org:kth-306446DiVA, id: diva2:1624849
Conference
25th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), MAY 11-14, 2021, Int Inst Informat Technol Hyderabad, ELECTR NETWORK
Note

QC 20220105

Conference ISBN: 978-3-030-75762-5; 978-3-030-75761-8

Available from: 2022-01-05 Created: 2022-01-05 Last updated: 2025-01-27Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Gionis, Aristides

Search in DiVA

By author/editor
Gionis, Aristides
By organisation
Theoretical Computer Science, TCS
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 33 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf