Fast computing betweenness centrality with virtual nodes on large sparse networks.

Betweenness centrality is an essential index for analysis of complex networks. However, the calculation of betweenness centrality is quite time-consuming and the fastest known algorithm uses O(N(M + N log N)) time and O(N + M) space for weighted networks, where N and M are the number of nodes and ed...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Jing Yang, Yingwu Chen
Formato:	article
Lenguaje:	EN
Publicado:	Public Library of Science (PLoS) 2011
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/c4e426ed314c4748bdc5a10617296591
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:c4e426ed314c4748bdc5a10617296591
record_format	dspace
spelling	oai:doaj.org-article:c4e426ed314c4748bdc5a106172965912021-11-18T06:49:17ZFast computing betweenness centrality with virtual nodes on large sparse networks.1932-620310.1371/journal.pone.0022557https://doaj.org/article/c4e426ed314c4748bdc5a106172965912011-01-01T00:00:00Zhttps://www.ncbi.nlm.nih.gov/pmc/articles/pmid/21818337/pdf/?tool=EBIhttps://doaj.org/toc/1932-6203Betweenness centrality is an essential index for analysis of complex networks. However, the calculation of betweenness centrality is quite time-consuming and the fastest known algorithm uses O(N(M + N log N)) time and O(N + M) space for weighted networks, where N and M are the number of nodes and edges in the network, respectively. By inserting virtual nodes into the weighted edges and transforming the shortest path problem into a breadth-first search (BFS) problem, we propose an algorithm that can compute the betweenness centrality in O(wDN2) time for integer-weighted networks, where w is the average weight of edges and D is the average degree in the network. Considerable time can be saved with the proposed algorithm when w < log N/D + 1, indicating that it is suitable for lightly weighted large sparse networks. A similar concept of virtual node transformation can be used to calculate other shortest path based indices such as closeness centrality, graph centrality, stress centrality, and so on. Numerical simulations on various randomly generated networks reveal that it is feasible to use the proposed algorithm in large network analysis.Jing YangYingwu ChenPublic Library of Science (PLoS)articleMedicineRScienceQENPLoS ONE, Vol 6, Iss 7, p e22557 (2011)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Jing Yang Yingwu Chen Fast computing betweenness centrality with virtual nodes on large sparse networks.
description	Betweenness centrality is an essential index for analysis of complex networks. However, the calculation of betweenness centrality is quite time-consuming and the fastest known algorithm uses O(N(M + N log N)) time and O(N + M) space for weighted networks, where N and M are the number of nodes and edges in the network, respectively. By inserting virtual nodes into the weighted edges and transforming the shortest path problem into a breadth-first search (BFS) problem, we propose an algorithm that can compute the betweenness centrality in O(wDN2) time for integer-weighted networks, where w is the average weight of edges and D is the average degree in the network. Considerable time can be saved with the proposed algorithm when w < log N/D + 1, indicating that it is suitable for lightly weighted large sparse networks. A similar concept of virtual node transformation can be used to calculate other shortest path based indices such as closeness centrality, graph centrality, stress centrality, and so on. Numerical simulations on various randomly generated networks reveal that it is feasible to use the proposed algorithm in large network analysis.
format	article
author	Jing Yang Yingwu Chen
author_facet	Jing Yang Yingwu Chen
author_sort	Jing Yang
title	Fast computing betweenness centrality with virtual nodes on large sparse networks.
title_short	Fast computing betweenness centrality with virtual nodes on large sparse networks.
title_full	Fast computing betweenness centrality with virtual nodes on large sparse networks.
title_fullStr	Fast computing betweenness centrality with virtual nodes on large sparse networks.
title_full_unstemmed	Fast computing betweenness centrality with virtual nodes on large sparse networks.
title_sort	fast computing betweenness centrality with virtual nodes on large sparse networks.
publisher	Public Library of Science (PLoS)
publishDate	2011
url	https://doaj.org/article/c4e426ed314c4748bdc5a10617296591
work_keys_str_mv	AT jingyang fastcomputingbetweennesscentralitywithvirtualnodesonlargesparsenetworks AT yingwuchen fastcomputingbetweennesscentralitywithvirtualnodesonlargesparsenetworks
_version_	1718424378264256512

Fast computing betweenness centrality with virtual nodes on large sparse networks.

Ejemplares similares