Heuristics for Speeding Up Betweenness Centrality Computation

Zitieren

Dateien zu dieser Ressource

Dateien Größe Format Anzeige

Zu diesem Dokument gibt es keine Dateien.

PUZIS, Rami, Polina ZILBERMAN, Yuval ELOVICI, Shlomi DOLEV, Ulrik BRANDES, 2012. Heuristics for Speeding Up Betweenness Centrality Computation. 2012 ASE/IEEE International Conference on Social Computing and 2012 ASE/IEEE International Conference on Privacy, Security, Risk and Trust. Amsterdam, Netherlands, 3. Sep 2012 - 5. Sep 2012. In: 2012 International Conference on Privacy, Security, Risk and Trust and 2012 International Conference on Social Computing (PASSAT-SocialCom 2012). 2012 ASE/IEEE International Conference on Social Computing and 2012 ASE/IEEE International Conference on Privacy, Security, Risk and Trust. Amsterdam, Netherlands, 3. Sep 2012 - 5. Sep 2012. Piscataway, NJ:IEEE, pp. 302-311. ISBN 978-1-4673-5638-1

@inproceedings{Puzis2012-09Heuri-36929, title={Heuristics for Speeding Up Betweenness Centrality Computation}, year={2012}, doi={10.1109/SocialCom-PASSAT.2012.66}, isbn={978-1-4673-5638-1}, address={Piscataway, NJ}, publisher={IEEE}, booktitle={2012 International Conference on Privacy, Security, Risk and Trust and 2012 International Conference on Social Computing (PASSAT-SocialCom 2012)}, pages={302--311}, author={Puzis, Rami and Zilberman, Polina and Elovici, Yuval 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/36929"> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-01-24T13:33:47Z</dcterms:available> <dcterms:abstract xml:lang="eng">We propose and evaluate two complementary heuristics to speed up exact computation of the shortest-path between ness centrality. Both heuristics are relatively simple adaptations of the standard algorithm for between ness centrality. Consequently, they generalize the computation of edge between ness and most other variants, and can be used to further speed up between ness 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 between ness algorithm on the block-cut point tree and then compute the remaining contributions separately in each biconnected component. Experiments on a variety of large graphs illustrate the efficiency and complementarity of our heuristics.</dcterms:abstract> <dc:contributor>Puzis, Rami</dc:contributor> <dc:creator>Dolev, Shlomi</dc:creator> <dc:creator>Brandes, Ulrik</dc:creator> <dc:language>eng</dc:language> <dcterms:title>Heuristics for Speeding Up Betweenness Centrality Computation</dcterms:title> <dcterms:issued>2012-09</dcterms:issued> <dc:contributor>Zilberman, Polina</dc:contributor> <dc:creator>Elovici, Yuval</dc:creator> <dc:contributor>Dolev, Shlomi</dc:contributor> <dc:creator>Zilberman, Polina</dc:creator> <dc:contributor>Elovici, Yuval</dc:contributor> <dc:creator>Puzis, Rami</dc:creator> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/36929"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-01-24T13:33:47Z</dc:date> <dc:contributor>Brandes, Ulrik</dc:contributor> </rdf:Description> </rdf:RDF>

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto