Modularity-based graph partitioning using conditional expected models
Modularity-based partitioning methods divide networks into modules by comparing their structure against random networks conditioned to have the same number of nodes, edges, and degree distribution. We propose a novel way to measure modularity and divide graphs, based on conditional probabilities of...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
American Physical Society
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121393 |
| _version_ | 1826189886841946112 |
|---|---|
| author | Pantazis, Dimitrios Chang, Yu-Teng Leahy, Richard M. |
| author2 | McGovern Institute for Brain Research at MIT |
| author_facet | McGovern Institute for Brain Research at MIT Pantazis, Dimitrios Chang, Yu-Teng Leahy, Richard M. |
| author_sort | Pantazis, Dimitrios |
| collection | MIT |
| description | Modularity-based partitioning methods divide networks into modules by comparing their structure against random networks conditioned to have the same number of nodes, edges, and degree distribution. We propose a novel way to measure modularity and divide graphs, based on conditional probabilities of the edge strength of random networks. We provide closed-form solutions for the expected strength of an edge when it is conditioned on the degrees of the two neighboring nodes, or alternatively on the degrees of all nodes comprising the network. We analytically compute the expected network under the assumptions of Gaussian and Bernoulli distributions. When the Gaussian distribution assumption is violated, we prove that our expression is the best linear unbiased estimator. Finally, we investigate the performance of our conditional expected model in partitioning simulated and real-world networks. |
| first_indexed | 2024-09-23T08:27:29Z |
| format | Article |
| id | mit-1721.1/121393 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:27:29Z |
| publishDate | 2019 |
| publisher | American Physical Society |
| record_format | dspace |
| spelling | mit-1721.1/1213932022-09-23T12:40:58Z Modularity-based graph partitioning using conditional expected models Pantazis, Dimitrios Chang, Yu-Teng Leahy, Richard M. McGovern Institute for Brain Research at MIT Pantazis, Dimitrios Pantazis, Dimitrios Modularity-based partitioning methods divide networks into modules by comparing their structure against random networks conditioned to have the same number of nodes, edges, and degree distribution. We propose a novel way to measure modularity and divide graphs, based on conditional probabilities of the edge strength of random networks. We provide closed-form solutions for the expected strength of an edge when it is conditioned on the degrees of the two neighboring nodes, or alternatively on the degrees of all nodes comprising the network. We analytically compute the expected network under the assumptions of Gaussian and Bernoulli distributions. When the Gaussian distribution assumption is violated, we prove that our expression is the best linear unbiased estimator. Finally, we investigate the performance of our conditional expected model in partitioning simulated and real-world networks. National Institutes of Health (U.S.) (Grant 5R01EB000473) National Institutes of Health (U.S.) (Grant P41 RR013642) National Institutes of Health (U.S.) (Grant R01 EB002010) 2019-06-24T17:27:38Z 2019-06-24T17:27:38Z 2011-10 2012-01 Article http://purl.org/eprint/type/JournalArticle 1539-3755 https://hdl.handle.net/1721.1/121393 Chang, Yu-Teng, et al. “Modularity-Based Graph Partitioning Using Conditional Expected Models.” Physical Review E, 85, 1 (January 2012): n. pag. © 2012 American Physical Society en_US http://dx.doi.org/10.1103/PhysRevE.85.016109 Physical Review E Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf application/pdf American Physical Society APS |
| spellingShingle | Pantazis, Dimitrios Chang, Yu-Teng Leahy, Richard M. Modularity-based graph partitioning using conditional expected models |
| title | Modularity-based graph partitioning using conditional expected models |
| title_full | Modularity-based graph partitioning using conditional expected models |
| title_fullStr | Modularity-based graph partitioning using conditional expected models |
| title_full_unstemmed | Modularity-based graph partitioning using conditional expected models |
| title_short | Modularity-based graph partitioning using conditional expected models |
| title_sort | modularity based graph partitioning using conditional expected models |
| url | https://hdl.handle.net/1721.1/121393 |
| work_keys_str_mv | AT pantazisdimitrios modularitybasedgraphpartitioningusingconditionalexpectedmodels AT changyuteng modularitybasedgraphpartitioningusingconditionalexpectedmodels AT leahyrichardm modularitybasedgraphpartitioningusingconditionalexpectedmodels |