Publikation: Structural Similarity in Graphs : A Relaxation Approach for Role Assignment
Lade...
Dateien
Datum
2005
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
DOI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
FLEISCHER, Rudolf, ed., Gerhard TRIPPEN, ed.. Algorithms and Computation. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005, pp. 184-195. Lecture Notes in Computer Science. 3341. ISBN 978-3-540-24131-7. Available under: doi: 10.1007/978-3-540-30551-4_18
Zusammenfassung
Standard methods for role assignment partition the vertex set of a graph in such a way that vertices in the same class can be considered to have equivalent roles in the graph. Several classes of equivalence relations such as regular equivalence and equitable partitions have been proposed for role assignment, but they all suffer from the strictness of classifying vertices into being either equivalent or not. It is an open problem how to allow for varying degrees of similarity. Proposals include ad-hoc algorithmic approaches and optimization approaches which are computationally hard. In this paper we introduce the concept of structural similarity by relaxation of equitable partitions, thus providing a theoretical foundation for similarity measures which enjoys desirable properties with respect to existence, structure, and tractability.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690
BRANDES, Ulrik, Jürgen LERNER, 2005. Structural Similarity in Graphs : A Relaxation Approach for Role Assignment. In: FLEISCHER, Rudolf, ed., Gerhard TRIPPEN, ed.. Algorithms and Computation. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005, pp. 184-195. Lecture Notes in Computer Science. 3341. ISBN 978-3-540-24131-7. Available under: doi: 10.1007/978-3-540-30551-4_18BibTex
@inproceedings{Brandes2005Struc-5942,
year={2005},
doi={10.1007/978-3-540-30551-4_18},
title={Structural Similarity in Graphs : A Relaxation Approach for Role Assignment},
number={3341},
isbn={978-3-540-24131-7},
publisher={Springer Berlin Heidelberg},
address={Berlin, Heidelberg},
series={Lecture Notes in Computer Science},
booktitle={Algorithms and Computation},
pages={184--195},
editor={Fleischer, Rudolf and Trippen, Gerhard},
author={Brandes, Ulrik and Lerner, Jürgen}
}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/5942">
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5942/1/bl_ssg_04.pdf"/>
<dcterms:issued>2005</dcterms:issued>
<dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5942/1/bl_ssg_04.pdf"/>
<dc:contributor>Brandes, Ulrik</dc:contributor>
<dc:creator>Lerner, Jürgen</dc:creator>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:01:31Z</dcterms:available>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:01:31Z</dc:date>
<dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5942"/>
<dcterms:title>Structural Similarity in Graphs : A Relaxation Approach for Role Assignment</dcterms:title>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/>
<dcterms:bibliographicCitation>First publ. in: Proceedings of the 15th International Symposium Algorithms and Computation (ISAAC ´04) (LNCS 3341), 2004, pp. 184-195</dcterms:bibliographicCitation>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dcterms:abstract xml:lang="eng">Standard methods for role assignment partition the vertex set of a graph in such a way that vertices in the same class can be considered to have equivalent roles in the graph. Several classes of equivalence relations such as regular equivalence and equitable partitions have been proposed for role assignment, but they all suffer from the strictness of classifying vertices into being either equivalent or not. It is an open problem how to allow for varying degrees of similarity. Proposals include ad-hoc algorithmic approaches and optimization approaches which are computationally hard. In this paper we introduce the concept of structural similarity by relaxation of equitable partitions, thus providing a theoretical foundation for similarity measures which enjoys desirable properties with respect to existence, structure, and tractability.</dcterms:abstract>
<dc:language>eng</dc:language>
<dc:format>application/pdf</dc:format>
<dc:creator>Brandes, Ulrik</dc:creator>
<dc:contributor>Lerner, Jürgen</dc:contributor>
</rdf:Description>
</rdf:RDF>Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
