An extremely fast algorithm for identifying high closeness centrality vertices in large-scale networks

Vladimir Ufimtsev; Sanjukta Bhowmick

doi:10.1109/IA3.2014.12

An extremely fast algorithm for identifying high closeness centrality vertices in large-scale networks

Vladimir Ufimtsev, Sanjukta Bhowmick

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Scopus citations

Abstract

The significance of an entity in a network is generally given by the centrality value of its vertex. For most analysis purposes, only the high ranked vertices are required. However, most algorithms calculate the centrality values of all the vertices. We present an extremely fast and scalable algorithm for identifying the high closeness centrality vertices, using group testing. We show that our approach is significantly faster (bestcase over 50 times, worst-case over 7 times) than the currently used methods. We can also use group testing to identify networks that are sensitive to edge perturbation.

Original language	English (US)
Title of host publication	Proceedings of IA3 2014 - 4th Workshop on Irregular Applications
Subtitle of host publication	Architectures and Algorithms, Held in conjunction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis
Publisher	Association for Computing Machinery, Inc
Pages	53-56
Number of pages	4
ISBN (Electronic)	9781479970568
DOIs	https://doi.org/10.1109/IA3.2014.12
State	Published - Nov 16 2014
Event	4th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2014 - New Orleans, United States Duration: Nov 16 2014 → Nov 21 2014

Publication series

Name	Proceedings of IA3 2014 - 4th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis

Other

Other	4th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2014
Country/Territory	United States
City	New Orleans
Period	11/16/14 → 11/21/14

ASJC Scopus subject areas

Computer Science Applications
Hardware and Architecture
Modeling and Simulation

Access to Document

10.1109/IA3.2014.12

Cite this

Ufimtsev, V., & Bhowmick, S. (2014). An extremely fast algorithm for identifying high closeness centrality vertices in large-scale networks. In Proceedings of IA3 2014 - 4th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis (pp. 53-56). (Proceedings of IA3 2014 - 4th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis). Association for Computing Machinery, Inc. https://doi.org/10.1109/IA3.2014.12

An extremely fast algorithm for identifying high closeness centrality vertices in large-scale networks. / Ufimtsev, Vladimir; Bhowmick, Sanjukta.
Proceedings of IA3 2014 - 4th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis. Association for Computing Machinery, Inc, 2014. p. 53-56 (Proceedings of IA3 2014 - 4th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Ufimtsev, V & Bhowmick, S 2014, An extremely fast algorithm for identifying high closeness centrality vertices in large-scale networks. in Proceedings of IA3 2014 - 4th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis. Proceedings of IA3 2014 - 4th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis, Association for Computing Machinery, Inc, pp. 53-56, 4th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2014, New Orleans, United States, 11/16/14. https://doi.org/10.1109/IA3.2014.12

Ufimtsev V, Bhowmick S. An extremely fast algorithm for identifying high closeness centrality vertices in large-scale networks. In Proceedings of IA3 2014 - 4th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis. Association for Computing Machinery, Inc. 2014. p. 53-56. (Proceedings of IA3 2014 - 4th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis). doi: 10.1109/IA3.2014.12

Ufimtsev, Vladimir ; Bhowmick, Sanjukta. / An extremely fast algorithm for identifying high closeness centrality vertices in large-scale networks. Proceedings of IA3 2014 - 4th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis. Association for Computing Machinery, Inc, 2014. pp. 53-56 (Proceedings of IA3 2014 - 4th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis).

@inproceedings{88541d525a2b4b82bc81d27719ecb107,

title = "An extremely fast algorithm for identifying high closeness centrality vertices in large-scale networks",

abstract = "The significance of an entity in a network is generally given by the centrality value of its vertex. For most analysis purposes, only the high ranked vertices are required. However, most algorithms calculate the centrality values of all the vertices. We present an extremely fast and scalable algorithm for identifying the high closeness centrality vertices, using group testing. We show that our approach is significantly faster (bestcase over 50 times, worst-case over 7 times) than the currently used methods. We can also use group testing to identify networks that are sensitive to edge perturbation.",

author = "Vladimir Ufimtsev and Sanjukta Bhowmick",

year = "2014",

month = nov,

day = "16",

doi = "10.1109/IA3.2014.12",

language = "English (US)",

series = "Proceedings of IA3 2014 - 4th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis",

publisher = "Association for Computing Machinery, Inc",

pages = "53--56",

booktitle = "Proceedings of IA3 2014 - 4th Workshop on Irregular Applications",

note = "4th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2014 ; Conference date: 16-11-2014 Through 21-11-2014",

}

TY - GEN

T1 - An extremely fast algorithm for identifying high closeness centrality vertices in large-scale networks

AU - Ufimtsev, Vladimir

AU - Bhowmick, Sanjukta

PY - 2014/11/16

Y1 - 2014/11/16

N2 - The significance of an entity in a network is generally given by the centrality value of its vertex. For most analysis purposes, only the high ranked vertices are required. However, most algorithms calculate the centrality values of all the vertices. We present an extremely fast and scalable algorithm for identifying the high closeness centrality vertices, using group testing. We show that our approach is significantly faster (bestcase over 50 times, worst-case over 7 times) than the currently used methods. We can also use group testing to identify networks that are sensitive to edge perturbation.

AB - The significance of an entity in a network is generally given by the centrality value of its vertex. For most analysis purposes, only the high ranked vertices are required. However, most algorithms calculate the centrality values of all the vertices. We present an extremely fast and scalable algorithm for identifying the high closeness centrality vertices, using group testing. We show that our approach is significantly faster (bestcase over 50 times, worst-case over 7 times) than the currently used methods. We can also use group testing to identify networks that are sensitive to edge perturbation.

UR - http://www.scopus.com/inward/record.url?scp=84979681615&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84979681615&partnerID=8YFLogxK

U2 - 10.1109/IA3.2014.12

DO - 10.1109/IA3.2014.12

M3 - Conference contribution

AN - SCOPUS:84979681615

T3 - Proceedings of IA3 2014 - 4th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2014: The International Conference for High Performance Computing, Networking, Storage and Analysis

SP - 53

EP - 56

BT - Proceedings of IA3 2014 - 4th Workshop on Irregular Applications

PB - Association for Computing Machinery, Inc

T2 - 4th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2014

Y2 - 16 November 2014 through 21 November 2014

ER -

An extremely fast algorithm for identifying high closeness centrality vertices in large-scale networks

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this