A Faster Algorithm for Betweenness Centrality

Lade...
Vorschaubild
Dateien
algorithm.pdf
algorithm.pdfGröße: 305.94 KBDownloads: 11597
Datum
2001
Autor:innen
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
ArXiv-ID
Internationale Patentnummer
EU-Projektnummer
DFG-Projektnummer
Angaben zur Forschungsförderung (Freitext)
Projekt
Analyse und Visualisierung sozialer Netzwerke
Open Access-Veröffentlichung
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
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 690BRANDES, 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.9990249
BibTex
@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
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
Nein
Begutachtet
Diese Publikation teilen