Cliques in Regular Graphs and the Core-Periphery Problem in Social Networks

Lade...
Vorschaubild
Dateien
Brandes_0-386674.pdf
Brandes_0-386674.pdfGröße: 427.26 KBDownloads: 535
Datum
2016
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
CHAN, T-H. Hubert, ed. and others. Combinatorial Optimization and Applications : 10th International Conference, COCOA 2016, Hong Kong, China, December 16-18, 2016, Proceedings. Cham: Springer, 2016, pp. 175-186. Lecture Notes in Computer Science. 10043. ISSN 1611-3349. eISSN 1611-3349. ISBN 978-3-319-48748-9. Available under: doi: 10.1007/978-3-319-48749-6_13
Zusammenfassung

The existence of a densely knit core surrounded by a loosely connected periphery is a common macro-structural feature of social networks. Formally, the CorePeriphery problem is to partition the nodes of an undirected graph G=(V,E) such that a subset X⊂V, the core, induces a dense subgraph, and its complement V∖X , the periphery, induces a sparse subgraph. Split graphs represent the ideal case in which the core induces a clique and the periphery forms an independent set. The number of missing and superfluous edges in the core and the periphery, respectively, can be minimized in linear time via edit distance to the closest split graph. We show that the CorePeriphery becomes intractable for standard notions of density other than the absolute number of misclassified pairs. Our main tool is a regularization procedure that transforms a given graph with maximum degree d into a d-regular graph with the same clique number by adding at most d⋅n new nodes. This is of independent interest because it implies that finding a maximum clique in a regular graph is NP-hard to approximate to within a factor of n1/2−ε for all ε>0 . We gratefully acknowledge financial support from Deutsche Forschungsgemeinschaft (DFG) under grants Br 2158/6-1 and Ka 3042/3-1. This work is partially supported by the Zukunftskolleg of the University of Konstanz, and the Max Planck Center for Visual Computing and Communication (www.mpc-vcc.org).

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
COCOA 2016: Combinatorial Optimization and Applications, 16. Dez. 2016 - 18. Dez. 2016, Hong Kong
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690BRANDES, Ulrik, Eugenia HOLM, Andreas KARRENBAUER, 2016. Cliques in Regular Graphs and the Core-Periphery Problem in Social Networks. COCOA 2016: Combinatorial Optimization and Applications. Hong Kong, 16. Dez. 2016 - 18. Dez. 2016. In: CHAN, T-H. Hubert, ed. and others. Combinatorial Optimization and Applications : 10th International Conference, COCOA 2016, Hong Kong, China, December 16-18, 2016, Proceedings. Cham: Springer, 2016, pp. 175-186. Lecture Notes in Computer Science. 10043. ISSN 1611-3349. eISSN 1611-3349. ISBN 978-3-319-48748-9. Available under: doi: 10.1007/978-3-319-48749-6_13
BibTex
@inproceedings{Brandes2016-10-31Cliqu-36733,
  year={2016},
  doi={10.1007/978-3-319-48749-6_13},
  title={Cliques in Regular Graphs and the Core-Periphery Problem in Social Networks},
  number={10043},
  isbn={978-3-319-48748-9},
  issn={1611-3349},
  publisher={Springer},
  address={Cham},
  series={Lecture Notes in Computer Science},
  booktitle={Combinatorial Optimization and Applications : 10th International Conference, COCOA 2016, Hong Kong, China, December 16-18, 2016, Proceedings},
  pages={175--186},
  editor={Chan, T-H. Hubert},
  author={Brandes, Ulrik and Holm, Eugenia and Karrenbauer, Andreas}
}
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/36733">
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/52"/>
    <dc:contributor>Brandes, Ulrik</dc:contributor>
    <dc:rights>terms-of-use</dc:rights>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/36733"/>
    <dc:creator>Brandes, Ulrik</dc:creator>
    <dc:creator>Karrenbauer, Andreas</dc:creator>
    <dc:language>eng</dc:language>
    <dcterms:title>Cliques in Regular Graphs and the Core-Periphery Problem in Social Networks</dcterms:title>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-01-17T12:39:48Z</dc:date>
    <dcterms:abstract xml:lang="eng">The existence of a densely knit core surrounded by a loosely connected periphery is a common macro-structural feature of social networks. Formally, the CorePeriphery problem is to partition the nodes of an undirected graph G=(V,E) such that a subset X⊂V, the core, induces a dense subgraph, and its complement V∖X , the periphery, induces a sparse subgraph. Split graphs represent the ideal case in which the core induces a clique and the periphery forms an independent set. The number of missing and superfluous edges in the core and the periphery, respectively, can be minimized in linear time via edit distance to the closest split graph. We show that the CorePeriphery becomes intractable for standard notions of density other than the absolute number of misclassified pairs. Our main tool is a regularization procedure that transforms a given graph with maximum degree d into a d-regular graph with the same clique number by adding at most d⋅n new nodes. This is of independent interest because it implies that finding a maximum clique in a regular graph is NP-hard to approximate to within a factor of n&lt;sup&gt;1/2−ε&lt;/sup&gt; for all ε&gt;0 . We gratefully acknowledge financial support from Deutsche Forschungsgemeinschaft (DFG) under grants Br 2158/6-1 and Ka 3042/3-1. This work is partially supported by the Zukunftskolleg of the University of Konstanz, and the Max Planck Center for Visual Computing and Communication (www.mpc-vcc.org).</dcterms:abstract>
    <dc:contributor>Karrenbauer, Andreas</dc:contributor>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/52"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-01-17T12:39:48Z</dcterms:available>
    <dcterms:issued>2016-10-31</dcterms:issued>
    <dc:creator>Holm, Eugenia</dc:creator>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:contributor>Holm, Eugenia</dc:contributor>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/36733/1/Brandes_0-386674.pdf"/>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/36733/1/Brandes_0-386674.pdf"/>
  </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