kth.sePublikationer KTH
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Finding Densest Subgraphs with Edge-Color Constraints
KTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.ORCID-id: 0000-0002-2526-8762
KTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.
KTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.ORCID-id: 0000-0002-5211-112X
2024 (Engelska)Ingår i: WWW 2024 - Proceedings of the ACM Web Conference, Association for Computing Machinery (ACM) , 2024, s. 936-947Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

We consider a variant of the densest subgraph problem in networks with single or multiple edge attributes. For example, in a social network, the edge attributes may describe the type of relationship between users, such as friends, family, or acquaintances, or different types of communication. For conceptual simplicity, we view the attributes as edge colors. The new problem we address is to find a diverse densest subgraph that fulfills given requirements on the numbers of edges of specific colors. When searching for a dense social network community, our problem will enforce the requirement that the community is diverse according to criteria specified by the edge attributes. We show that the decision versions for finding exactly, at most, and at least h colored edges densest subgraph, where h is a vector of color requirements, are NP-complete, for already two colors. For the problem of finding a densest subgraph with at least h colored edges, we provide a linear-time constant-factor approximation algorithm when the input graph is sparse. On the way, we introduce the related at least h (non-colored) edges densest subgraph problem, show its hardness, and also provide a linear-time constant-factor approximation. In our experiments, we demonstrate the efficacy and efficiency of our new algorithms.

Ort, förlag, år, upplaga, sidor
Association for Computing Machinery (ACM) , 2024. s. 936-947
Nyckelord [en]
densest subgraph, density, diversity, social networks
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:kth:diva-347330DOI: 10.1145/3589334.3645647Scopus ID: 2-s2.0-85194105710OAI: oai:DiVA.org:kth-347330DiVA, id: diva2:1867263
Konferens
33rd ACM Web Conference, WWW 2024, Singapore, Singapore, May 13 2024 - May 17 2024
Anmärkning

Part of ISBN [9798400701719]QC 20240612

Tillgänglig från: 2024-06-10 Skapad: 2024-06-10 Senast uppdaterad: 2024-12-03Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Oettershagen, LutzWang, HongliangGionis, Aristides

Sök vidare i DiVA

Av författaren/redaktören
Oettershagen, LutzWang, HongliangGionis, Aristides
Av organisationen
Teoretisk datalogi, TCS
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 92 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf