On Modularity Clustering

Kurzanzeige
dc.contributor.authorBrandes, Ulrik
dc.contributor.authorDelling, Danieldeu
dc.contributor.authorGaertler, Marcodeu
dc.contributor.authorGörke, Robertdeu
dc.contributor.authorHoefer, Martindeu
dc.contributor.authorNikoloski, Zorandeu
dc.contributor.authorWagner, Dorotheadeu
dc.date.accessioned2011-03-24T16:00:42Zdeu
dc.date.available2011-03-24T16:00:42Zdeu
dc.date.issued2008deu
dc.description.abstractModularity 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 agglomerative approach.eng
dc.description.versionpublished
dc.format.mimetypeapplication/pdfdeu
dc.identifier.citationFirst publ. in: IEEE Transactions on Knowledge and Data Engineering ; 20 (2008), 2. - S. 172-188deu
dc.identifier.doi10.1109/TKDE.2007.190689
dc.identifier.ppn302443878deu
dc.identifier.urihttp://kops.uni-konstanz.de/handle/123456789/5853
dc.language.isoengdeu
dc.legacy.dateIssued2009deu
dc.rightsAttribution-NonCommercial-NoDerivs 2.0 Generic
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/2.0/
dc.subjectgraph clusteringdeu
dc.subjectgraph partitioningdeu
dc.subjectmodularitydeu
dc.subjectcommunity structuredeu
dc.subjectgreedy algorithmdeu
dc.subject.ddc004deu
dc.titleOn Modularity Clusteringeng
dc.typeJOURNAL_ARTICLEdeu
dspace.entity.typePublication
kops.citation.bibtex
@article{Brandes2008Modul-5853,
  year={2008},
  doi={10.1109/TKDE.2007.190689},
  title={On Modularity Clustering},
  number={2},
  volume={20},
  journal={IEEE Transactions on Knowledge and Data Engineering},
  pages={172--188},
  author={Brandes, Ulrik and Delling, Daniel and Gaertler, Marco and Görke, Robert and Hoefer, Martin and Nikoloski, Zoran and Wagner, Dorothea}
}
kops.citation.iso690BRANDES, Ulrik, Daniel DELLING, Marco GAERTLER, Robert GÖRKE, Martin HOEFER, Zoran NIKOLOSKI, Dorothea WAGNER, 2008. On Modularity Clustering. In: IEEE Transactions on Knowledge and Data Engineering. 2008, 20(2), pp. 172-188. Available under: doi: 10.1109/TKDE.2007.190689deu
kops.citation.iso690BRANDES, Ulrik, Daniel DELLING, Marco GAERTLER, Robert GÖRKE, Martin HOEFER, Zoran NIKOLOSKI, Dorothea WAGNER, 2008. On Modularity Clustering. In: IEEE Transactions on Knowledge and Data Engineering. 2008, 20(2), pp. 172-188. Available under: doi: 10.1109/TKDE.2007.190689eng
kops.citation.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/5853">
    <dc:creator>Nikoloski, Zoran</dc:creator>
    <dc:creator>Görke, Robert</dc:creator>
    <dc:creator>Gaertler, Marco</dc:creator>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/>
    <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 agglomerative approach.</dcterms:abstract>
    <dc:contributor>Wagner, Dorothea</dc:contributor>
    <dcterms:bibliographicCitation>First publ. in: IEEE Transactions on Knowledge and Data Engineering ; 20 (2008), 2. - S. 172-188</dcterms:bibliographicCitation>
    <dc:creator>Hoefer, Martin</dc:creator>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:contributor>Nikoloski, Zoran</dc:contributor>
    <dc:creator>Delling, Daniel</dc:creator>
    <dc:contributor>Gaertler, Marco</dc:contributor>
    <dc:format>application/pdf</dc:format>
    <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:42Z</dcterms:available>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:language>eng</dc:language>
    <dcterms:title>On Modularity Clustering</dcterms:title>
    <dc:contributor>Hoefer, Martin</dc:contributor>
    <dcterms:issued>2008</dcterms:issued>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5853/1/modularity.pdf"/>
    <dc:creator>Wagner, Dorothea</dc:creator>
    <dc:contributor>Delling, Daniel</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>Brandes, Ulrik</dc:creator>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5853/1/modularity.pdf"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5853"/>
    <dc:contributor>Görke, Robert</dc:contributor>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:42Z</dc:date>
    <dc:contributor>Brandes, Ulrik</dc:contributor>
  </rdf:Description>
</rdf:RDF>
kops.description.openAccessopenaccessgreen
kops.flag.knbibliographytrue
kops.identifier.nbnurn:nbn:de:bsz:352-opus-71790deu
kops.opus.id7179deu
kops.sourcefieldIEEE Transactions on Knowledge and Data Engineering. 2008, <b>20</b>(2), pp. 172-188. Available under: doi: 10.1109/TKDE.2007.190689deu
kops.sourcefield.plainIEEE Transactions on Knowledge and Data Engineering. 2008, 20(2), pp. 172-188. Available under: doi: 10.1109/TKDE.2007.190689deu
kops.sourcefield.plainIEEE Transactions on Knowledge and Data Engineering. 2008, 20(2), pp. 172-188. Available under: doi: 10.1109/TKDE.2007.190689eng
relation.isAuthorOfPublicationfa1660c9-a071-4d01-9bdd-7adcd0e2d7d7
relation.isAuthorOfPublication.latestForDiscoveryfa1660c9-a071-4d01-9bdd-7adcd0e2d7d7
source.bibliographicInfo.fromPage172
source.bibliographicInfo.issue2
source.bibliographicInfo.toPage188
source.bibliographicInfo.volume20
source.periodicalTitleIEEE Transactions on Knowledge and Data Engineering

Dateien

Originalbündel

Gerade angezeigt 1 - 1 von 1
Vorschaubild nicht verfügbar
Name:
modularity.pdf
Größe:
927.2 KB
Format:
Adobe Portable Document Format
modularity.pdf
modularity.pdfGröße: 927.2 KBDownloads: 5971

Sammlungen

Informatik und Informationswissenschaft: Publikationen