Publikation:

On Finding Graph Clusterings with Maximum Modularity

Vorschaubild

Dateien

bdgghnw_fgcmm_07.pdf
bdgghnw_fgcmm_07.pdfGröße: 497.64 KBDownloads: 800

Datum

2007

Autor:innen

Delling, Daniel
Gaertler, Marco
Görke, Robert
Hoefer, Martin
Nikoloski, Zoran
Wagner, Dorothea

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-77644
DOI (zitierfähiger Link)
https://doi.org/10.1007/978-3-540-74839-7_12
ArXiv-ID

Internationale Patentnummer

Link zur Lizenz
Urheberrechtlich geschützt

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Green

Sammlungen

Informatik und Informationswissenschaft: Publikationen
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

BRANDSTÄDT, Andreas, ed., Dieter KRATSCH, ed., Haiko MÜLLER, ed.. Graph-Theoretic Concepts in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 121-132. Lecture Notes in Computer Science. ISBN 978-3-540-74838-0. Available under: doi: 10.1007/978-3-540-74839-7_12

Zusammenfassung

Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, and in particular in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts, and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomaration approach.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Verknüpfte Datensätze

Zitieren

ISO 690BRANDES, Ulrik, Daniel DELLING, Marco GAERTLER, Robert GÖRKE, Martin HOEFER, Zoran NIKOLOSKI, Dorothea WAGNER, 2007. On Finding Graph Clusterings with Maximum Modularity. In: BRANDSTÄDT, Andreas, ed., Dieter KRATSCH, ed., Haiko MÜLLER, ed.. Graph-Theoretic Concepts in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 121-132. Lecture Notes in Computer Science. ISBN 978-3-540-74838-0. Available under: doi: 10.1007/978-3-540-74839-7_12
BibTex
@inproceedings{Brandes2007Findi-5883,
  year={2007},
  doi={10.1007/978-3-540-74839-7_12},
  title={On Finding Graph Clusterings with Maximum Modularity},
  isbn={978-3-540-74838-0},
  publisher={Springer Berlin Heidelberg},
  address={Berlin, Heidelberg},
  series={Lecture Notes in Computer Science},
  booktitle={Graph-Theoretic Concepts in Computer Science},
  pages={121--132},
  editor={Brandstädt, Andreas and Kratsch, Dieter and Müller, Haiko},
  author={Brandes, Ulrik and Delling, Daniel and Gaertler, Marco and Görke, Robert and Hoefer, Martin and Nikoloski, Zoran and Wagner, Dorothea}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/5883">
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>Gaertler, Marco</dc:creator>
    <dc:contributor>Wagner, Dorothea</dc:contributor>
    <dcterms:abstract xml:lang="eng">Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, and in particular in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts, and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomaration approach.</dcterms:abstract>
    <dc:creator>Wagner, Dorothea</dc:creator>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5883"/>
    <dc:rights>terms-of-use</dc:rights>
    <dc:contributor>Hoefer, Martin</dc:contributor>
    <dcterms:issued>2007</dcterms:issued>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5883/1/bdgghnw_fgcmm_07.pdf"/>
    <dcterms:title>On Finding Graph Clusterings with Maximum Modularity</dcterms:title>
    <dc:language>eng</dc:language>
    <dcterms:bibliographicCitation>First publ. in: Proceedings of the 33rd International Workshop Graph-Theoretic Concepts in Computer Science (WG ´07) (LNCS 4769), 2007, pp. 121-132</dcterms:bibliographicCitation>
    <dc:creator>Delling, Daniel</dc:creator>
    <dc:format>application/pdf</dc:format>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:57Z</dcterms:available>
    <dc:contributor>Nikoloski, Zoran</dc:contributor>
    <dc:contributor>Görke, Robert</dc:contributor>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:57Z</dc:date>
    <dc:contributor>Delling, Daniel</dc:contributor>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Brandes, Ulrik</dc:creator>
    <dc:creator>Nikoloski, Zoran</dc:creator>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5883/1/bdgghnw_fgcmm_07.pdf"/>
    <dc:creator>Görke, Robert</dc:creator>
    <dc:creator>Hoefer, Martin</dc:creator>
    <dc:contributor>Gaertler, Marco</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:contributor>Brandes, Ulrik</dc:contributor>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen