This preprint is under consideration at Journal of Big Data. A preprint is a preliminary version of a manuscript that has not completed peer review at a journal. Research Square does not conduct peer review prior to posting preprints. The posting of a preprint on this server should not be interpreted as an endorsement of its validity or suitability for dissemination as established information or for guiding clinical practice.
Learn more about In Review
A new preprint design is coming!
We have improved readability, clarity, accessibility, and opportunities for engagement.
Research
Cecile Daniel
Gustave Eiffel University: Universite Gustave Eiffel
Corresponding Author
ORCiD: https://orcid.org/0000-0001-7519-1962
License:
This work is licensed under a CC BY 4.0 License. Read Full License
Nowadays a large amount of data is originated by complex systems, such as social networks, transportation systems, computer and service networks. These systems can be modeled by using graphs and studied by exploiting graph metrics, such as Betweenness Centrality (BC), a popular metric to analyze node centrality of graphs. In spite of its great potential, this metric requires long computation time, especially for large graphs.
In this paper, we present a very fast algorithm to compute BC of undirected graphs by exploiting clustering. The algorithm leverages structural properties of graphs to find classes of equivalent nodes: by selecting one representative node for each class, we are able to compute BC by significantly reducing the number of single-source shortest path explorations adopted by Brandes' algorithm. We formally prove the graph properties that we exploit to define the algorithm and present an implementation based on Scala for both sequential and parallel map-reduce executions.
The experimental evaluation of both versions, conducted with synthetic and real graphs, reveals that our solution largely outperforms Brandes' algorithm and significantly improves known heuristics.
Keywords
Complex networks analysis, Betweenness centrality, Distributed computation, Big data processing
Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10
Figure 11
Figure 12
Figure 13
Loading...
Badges
Prescreen
This manuscript passed our Prescreen assessment
Complete author information
Appropriate declaration statements
Potential risks to human health
Prescreen
Peer Review Timeline
CURRENT STATUS: Under Review
Version 1
Posted 23 Mar, 2021
No community comments so far
Editorial decision: Major Revision
On 30 Apr, 2021
Review #3 received
Received 16 Apr, 2021
Review #2 received
Received 16 Apr, 2021
Review #4 received
Received 09 Apr, 2021
Reviewer #10 agreed
On 07 Apr, 2021
Reviewer #6 agreed
On 04 Apr, 2021
Reviewer #7 agreed
On 04 Apr, 2021
Reviewer #8 agreed
On 04 Apr, 2021
Reviewer #9 agreed
On 04 Apr, 2021
Reviews received
Received 04 Apr, 2021
Review #6 received
Received 04 Apr, 2021
Reviewer #5 agreed
On 04 Apr, 2021
Review #1 received
Received 04 Apr, 2021
Review #5 received
Received 04 Apr, 2021
Review #7 received
Received 04 Apr, 2021
Reviewer #2 agreed
On 03 Apr, 2021
Reviewer #3 agreed
On 03 Apr, 2021
Reviewer #4 agreed
On 03 Apr, 2021
Reviewer #1 agreed
On 03 Apr, 2021
Reviewers invited
Invitations sent on 03 Apr, 2021
Editor assigned
On 12 Mar, 2021
Submission checks complete
On 12 Mar, 2021
Editor invited
On 12 Mar, 2021
First submitted
On 11 Mar, 2021
Metrics
Comments: 0
PDF Downloads: ...
HTML Views: ...
Subject Areas
Computer Architecture and Engineering
Learn more about our company.
A new preprint design is coming!
We have improved readability, clarity, accessibility, and opportunities for engagement.
This preprint is under consideration at Journal of Big Data. A preprint is a preliminary version of a manuscript that has not completed peer review at a journal. Research Square does not conduct peer review prior to posting preprints. The posting of a preprint on this server should not be interpreted as an endorsement of its validity or suitability for dissemination as established information or for guiding clinical practice.
Learn more about In Review
Research
Cecile Daniel
Gustave Eiffel University: Universite Gustave Eiffel
Corresponding Author
ORCiD: https://orcid.org/0000-0001-7519-1962
Badges
Prescreen
This manuscript passed our Prescreen assessment
Complete author information
Appropriate declaration statements
Potential risks to human health
Prescreen
Peer Review Timeline
CURRENT STATUS: Under Review
Version 1
Posted 23 Mar, 2021
No community comments so far
Editorial decision: Major Revision
On 30 Apr, 2021
Review #3 received
Received 16 Apr, 2021
Review #2 received
Received 16 Apr, 2021
Review #4 received
Received 09 Apr, 2021
Reviewer #10 agreed
On 07 Apr, 2021
Reviewer #6 agreed
On 04 Apr, 2021
Reviewer #7 agreed
On 04 Apr, 2021
Reviewer #8 agreed
On 04 Apr, 2021
Reviewer #9 agreed
On 04 Apr, 2021
Reviews received
Received 04 Apr, 2021
Review #6 received
Received 04 Apr, 2021
Reviewer #5 agreed
On 04 Apr, 2021
Review #1 received
Received 04 Apr, 2021
Review #5 received
Received 04 Apr, 2021
Review #7 received
Received 04 Apr, 2021
Reviewer #2 agreed
On 03 Apr, 2021
Reviewer #3 agreed
On 03 Apr, 2021
Reviewer #4 agreed
On 03 Apr, 2021
Reviewer #1 agreed
On 03 Apr, 2021
Reviewers invited
Invitations sent on 03 Apr, 2021
Editor assigned
On 12 Mar, 2021
Submission checks complete
On 12 Mar, 2021
Editor invited
On 12 Mar, 2021
First submitted
On 11 Mar, 2021
Metrics
Comments: 0
PDF Downloads: ...
HTML Views: ...
Subject Areas
Computer Architecture and Engineering
License:
This work is licensed under a CC BY 4.0 License. Read Full License
Nowadays a large amount of data is originated by complex systems, such as social networks, transportation systems, computer and service networks. These systems can be modeled by using graphs and studied by exploiting graph metrics, such as Betweenness Centrality (BC), a popular metric to analyze node centrality of graphs. In spite of its great potential, this metric requires long computation time, especially for large graphs.
In this paper, we present a very fast algorithm to compute BC of undirected graphs by exploiting clustering. The algorithm leverages structural properties of graphs to find classes of equivalent nodes: by selecting one representative node for each class, we are able to compute BC by significantly reducing the number of single-source shortest path explorations adopted by Brandes' algorithm. We formally prove the graph properties that we exploit to define the algorithm and present an implementation based on Scala for both sequential and parallel map-reduce executions.
The experimental evaluation of both versions, conducted with synthetic and real graphs, reveals that our solution largely outperforms Brandes' algorithm and significantly improves known heuristics.
Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10
Figure 11
Figure 12
Figure 13
Loading...