Topology manipulations for speeding betweenness centrality computation

Zitieren

Dateien zu dieser Ressource

Dateien Größe Format Anzeige

Zu diesem Dokument gibt es keine Dateien.

PUZIS, Rami, Yuval ELOVICI, Polina ZILBERMAN, Shlomi DOLEV, Ulrik BRANDES, 2015. Topology manipulations for speeding betweenness centrality computation. In: Journal of Complex Networks. 3(1), pp. 84-112. ISSN 2051-1310. eISSN 2051-1329

@article{Puzis2015Topol-30388, title={Topology manipulations for speeding betweenness centrality computation}, year={2015}, doi={10.1093/comnet/cnu015}, number={1}, volume={3}, issn={2051-1310}, journal={Journal of Complex Networks}, pages={84--112}, author={Puzis, Rami and Elovici, Yuval and Zilberman, Polina and Dolev, Shlomi and Brandes, Ulrik} }

<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:dcterms="http://purl.org/dc/terms/" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/rdf/resource/123456789/30388"> <dc:language>eng</dc:language> <dcterms:abstract xml:lang="eng">We propose and evaluate two complementary heuristics to speed up exact computation of the shortest-path betweenness centrality (BC). Both heuristics are relatively simple adaptations of the standard algorithm for BC. Consequently, they generalize the computation of edge betweenness and most other variants, and can be used to further speed up betweenness estimation algorithms, as well. In the first heuristic, structurally equivalent vertices are contracted based on the observation that they have the same centrality and also contribute equally to the centrality of others. In the second heuristic, we first apply a linear-time betweenness algorithm on the block-cut-point tree and then compute the remaining contributions separately in each bi-connected component. Experiments on a variety of large graphs illustrate the efficiency and complementarity of our heuristics.</dcterms:abstract> <dc:creator>Brandes, Ulrik</dc:creator> <dc:creator>Dolev, Shlomi</dc:creator> <dc:creator>Puzis, Rami</dc:creator> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2015-03-18T12:58:12Z</dcterms:available> <dc:contributor>Puzis, Rami</dc:contributor> <dc:contributor>Elovici, Yuval</dc:contributor> <dc:contributor>Brandes, Ulrik</dc:contributor> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/30388"/> <dc:contributor>Zilberman, Polina</dc:contributor> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2015-03-18T12:58:12Z</dc:date> <dc:creator>Zilberman, Polina</dc:creator> <dc:creator>Elovici, Yuval</dc:creator> <dcterms:title>Topology manipulations for speeding betweenness centrality computation</dcterms:title> <dcterms:issued>2015</dcterms:issued> <dc:contributor>Dolev, Shlomi</dc:contributor> </rdf:Description> </rdf:RDF>

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto