This preprint is under consideration at BMC Bioinformatics. 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 article
Phillip C-Y. Sheu
University of California Irvine
Corresponding Author
ORCiD: https://orcid.org/0000-0003-2036-850X
License:
This work is licensed under a CC BY 4.0 License. Read Full License
Background
Graph theory has been widely applied to the studies in biomedicine such as structural measures including betweenness centrality. However, if the network size is too large, the result of betweenness centrality would be difficult to obtain in a reasonable amount of time.
Result
In this paper, we describe an approach, 1+ɛ lossy graph reduction algorithm, to computing betweenness centrality on large graphs. The approach is able to guarantee a bounded approximation result. We use GSE48216, a breast cancer cell line co-expression network, to show that our algorithms can achieve a higher reduction rate with a trade-off of some bounded errors in query results. Furthermore, by comparing the betweenness centrality of the original graph and the reduced graph, it can be shown that a higher reduction rate does not sacrifice the accuracy of betweenness centrality when providing faster execution time.
Conclusions
Our proposed 1+ɛ lossy graph reduction algorithm is validated by the experiment results which show that the approach achieves a faster execution within a bounded error rate.
Keywords
Graph, Betweenness Centrality, Graph Reduction
Figure 1
Figure 2
Figure 3
Figure 4
The full text of this article is available to read as a PDF.
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 Revision
Version 1
Posted 11 Nov, 2020
No community comments so far
Review #4 received
Received 02 Dec, 2020
Editorial decision: Major revision
On 02 Dec, 2020
Review #3 received
Received 23 Nov, 2020
Review #1 received
Received 22 Nov, 2020
Review #2 received
Received 19 Nov, 2020
Reviewer #9 agreed
On 18 Nov, 2020
Reviewer #10 agreed
On 18 Nov, 2020
Reviewer #11 agreed
On 18 Nov, 2020
Reviewer #8 agreed
On 18 Nov, 2020
Review #9 received
Received 18 Nov, 2020
Review #5 received
Received 18 Nov, 2020
Reviewer #7 agreed
On 17 Nov, 2020
Reviewer #4 agreed
On 15 Nov, 2020
Reviewer #5 agreed
On 15 Nov, 2020
Reviewer #6 agreed
On 15 Nov, 2020
Reviewer #2 agreed
On 15 Nov, 2020
Reviewer #3 agreed
On 15 Nov, 2020
Reviewers invited
Invitations sent on 15 Nov, 2020
Reviewer #1 agreed
On 15 Nov, 2020
Editor assigned
On 11 Nov, 2020
Submission checks complete
On 09 Nov, 2020
Editor invited
On 08 Nov, 2020
Metrics
Comments: 0
PDF Downloads: ...
HTML Views: ...
Subject Areas
Bioinformatics
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 BMC Bioinformatics. 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 article
Phillip C-Y. Sheu
University of California Irvine
Corresponding Author
ORCiD: https://orcid.org/0000-0003-2036-850X
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 Revision
Version 1
Posted 11 Nov, 2020
No community comments so far
Review #4 received
Received 02 Dec, 2020
Editorial decision: Major revision
On 02 Dec, 2020
Review #3 received
Received 23 Nov, 2020
Review #1 received
Received 22 Nov, 2020
Review #2 received
Received 19 Nov, 2020
Reviewer #9 agreed
On 18 Nov, 2020
Reviewer #10 agreed
On 18 Nov, 2020
Reviewer #11 agreed
On 18 Nov, 2020
Reviewer #8 agreed
On 18 Nov, 2020
Review #9 received
Received 18 Nov, 2020
Review #5 received
Received 18 Nov, 2020
Reviewer #7 agreed
On 17 Nov, 2020
Reviewer #4 agreed
On 15 Nov, 2020
Reviewer #5 agreed
On 15 Nov, 2020
Reviewer #6 agreed
On 15 Nov, 2020
Reviewer #2 agreed
On 15 Nov, 2020
Reviewer #3 agreed
On 15 Nov, 2020
Reviewers invited
Invitations sent on 15 Nov, 2020
Reviewer #1 agreed
On 15 Nov, 2020
Editor assigned
On 11 Nov, 2020
Submission checks complete
On 09 Nov, 2020
Editor invited
On 08 Nov, 2020
Metrics
Comments: 0
PDF Downloads: ...
HTML Views: ...
Subject Areas
Bioinformatics
License:
This work is licensed under a CC BY 4.0 License. Read Full License
Background
Graph theory has been widely applied to the studies in biomedicine such as structural measures including betweenness centrality. However, if the network size is too large, the result of betweenness centrality would be difficult to obtain in a reasonable amount of time.
Result
In this paper, we describe an approach, 1+ɛ lossy graph reduction algorithm, to computing betweenness centrality on large graphs. The approach is able to guarantee a bounded approximation result. We use GSE48216, a breast cancer cell line co-expression network, to show that our algorithms can achieve a higher reduction rate with a trade-off of some bounded errors in query results. Furthermore, by comparing the betweenness centrality of the original graph and the reduced graph, it can be shown that a higher reduction rate does not sacrifice the accuracy of betweenness centrality when providing faster execution time.
Conclusions
Our proposed 1+ɛ lossy graph reduction algorithm is validated by the experiment results which show that the approach achieves a faster execution within a bounded error rate.
Figure 1
Figure 2
Figure 3
Figure 4
The full text of this article is available to read as a PDF.
Loading...