Publikation: A Faster Algorithm for Betweenness Centrality
Lade...
Dateien
Datum
2001
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
Analyse und Visualisierung sozialer Netzwerke
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published
Erschienen in
Journal of Mathematical Sociology. 2001, 25(2), pp. 163-177. Available under: doi: 10.1080/0022250X.2001.9990249
Zusammenfassung
The betweenness centrality index is essential in the analysis of social networks, but costly to compute. Currently, the fastest known algorithms require Theta(n3) time and Theta(n2) space, where n is the number of actors in the network. Motivated by the fast-growing need to compute centrality indices on large, yet very sparse, networks, new algorithms for betweenness are introduced in this paper. They require O(n + m) space and run in O(nm) and O(nm + n2 log n) time on unweighted and weighted networks, respectively, where m is the number of links. Experimental evidence is provided that this substantially increases the range of networks for which centrality analysis is feasible.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
social networks, betweenness centrality, algorithms
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690
BRANDES, Ulrik, 2001. A Faster Algorithm for Betweenness Centrality. In: Journal of Mathematical Sociology. 2001, 25(2), pp. 163-177. Available under: doi: 10.1080/0022250X.2001.9990249BibTex
@article{Brandes2001Faste-5739, year={2001}, doi={10.1080/0022250X.2001.9990249}, title={A Faster Algorithm for Betweenness Centrality}, number={2}, volume={25}, journal={Journal of Mathematical Sociology}, pages={163--177}, author={Brandes, Ulrik} }
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/5739"> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:59:42Z</dc:date> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:59:42Z</dcterms:available> <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/> <dc:creator>Brandes, Ulrik</dc:creator> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5739/1/algorithm.pdf"/> <dc:language>eng</dc:language> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dcterms:issued>2001</dcterms:issued> <dc:format>application/pdf</dc:format> <dc:contributor>Brandes, Ulrik</dc:contributor> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5739"/> <dcterms:title>A Faster Algorithm for Betweenness Centrality</dcterms:title> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5739/1/algorithm.pdf"/> <dcterms:abstract xml:lang="eng">The betweenness centrality index is essential in the analysis of social networks, but costly to compute. Currently, the fastest known algorithms require Theta(n3) time and Theta(n2) space, where n is the number of actors in the network. Motivated by the fast-growing need to compute centrality indices on large, yet very sparse, networks, new algorithms for betweenness are introduced in this paper. They require O(n + m) space and run in O(nm) and O(nm + n2 log n) time on unweighted and weighted networks, respectively, where m is the number of links. Experimental evidence is provided that this substantially increases the range of networks for which centrality analysis is feasible.</dcterms:abstract> <dcterms:bibliographicCitation>First publ. in: Journal of Mathematical Sociology ; 25 (2001), 2. - S. 163-177</dcterms:bibliographicCitation> </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
Nein