An Algorithm and Metric for Network Decomposition from Similarity Matrices: Application to Positional Analyses
We present an algorithm for decomposing a social network into an optimal number of structurally equivalent classes. The k-means method is used to determine the best decomposition of the social network for various numbers of subgroups. The best number of subgroups into which to decompose a network is...
| Main Authors: | , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology. Engineering Systems Division
2016
|
| Online Access: | http://hdl.handle.net/1721.1/102890 |
| _version_ | 1826208042376495104 |
|---|---|
| author | Hsieh, Mo-Han Magee, Christopher L. |
| author_facet | Hsieh, Mo-Han Magee, Christopher L. |
| author_sort | Hsieh, Mo-Han |
| collection | MIT |
| description | We present an algorithm for decomposing a social network into an optimal number of structurally equivalent classes. The k-means method is used to determine the best decomposition of the social network for various numbers of subgroups. The best number of subgroups into which to decompose a network is determined by minimizing the intra-cluster variance of similarity subject to the constraint that the improvement in going to more subgroups is better than a random network would achieve. We also describe a decomposability metric that assesses how closely the derived decomposition approaches an ideal network having only structurally equivalent classes.
Three well known network data sets were used to demonstrate the algorithm and decomposability metric. These demonstrations indicate the utility of the approach and suggest how it can be used in a complementary way to the Generalized Blockmodeling. |
| first_indexed | 2024-09-23T13:59:36Z |
| format | Working Paper |
| id | mit-1721.1/102890 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:59:36Z |
| publishDate | 2016 |
| publisher | Massachusetts Institute of Technology. Engineering Systems Division |
| record_format | dspace |
| spelling | mit-1721.1/1028902019-04-12T16:24:35Z An Algorithm and Metric for Network Decomposition from Similarity Matrices: Application to Positional Analyses Hsieh, Mo-Han Magee, Christopher L. We present an algorithm for decomposing a social network into an optimal number of structurally equivalent classes. The k-means method is used to determine the best decomposition of the social network for various numbers of subgroups. The best number of subgroups into which to decompose a network is determined by minimizing the intra-cluster variance of similarity subject to the constraint that the improvement in going to more subgroups is better than a random network would achieve. We also describe a decomposability metric that assesses how closely the derived decomposition approaches an ideal network having only structurally equivalent classes. Three well known network data sets were used to demonstrate the algorithm and decomposability metric. These demonstrations indicate the utility of the approach and suggest how it can be used in a complementary way to the Generalized Blockmodeling. 2016-06-03T01:19:13Z 2016-06-03T01:19:13Z 2007-02 Working Paper http://hdl.handle.net/1721.1/102890 en_US ESD Working Papers;ESD-WP-2007-13 application/pdf Massachusetts Institute of Technology. Engineering Systems Division |
| spellingShingle | Hsieh, Mo-Han Magee, Christopher L. An Algorithm and Metric for Network Decomposition from Similarity Matrices: Application to Positional Analyses |
| title | An Algorithm and Metric for Network Decomposition from Similarity Matrices: Application to Positional Analyses |
| title_full | An Algorithm and Metric for Network Decomposition from Similarity Matrices: Application to Positional Analyses |
| title_fullStr | An Algorithm and Metric for Network Decomposition from Similarity Matrices: Application to Positional Analyses |
| title_full_unstemmed | An Algorithm and Metric for Network Decomposition from Similarity Matrices: Application to Positional Analyses |
| title_short | An Algorithm and Metric for Network Decomposition from Similarity Matrices: Application to Positional Analyses |
| title_sort | algorithm and metric for network decomposition from similarity matrices application to positional analyses |
| url | http://hdl.handle.net/1721.1/102890 |
| work_keys_str_mv | AT hsiehmohan analgorithmandmetricfornetworkdecompositionfromsimilaritymatricesapplicationtopositionalanalyses AT mageechristopherl analgorithmandmetricfornetworkdecompositionfromsimilaritymatricesapplicationtopositionalanalyses AT hsiehmohan algorithmandmetricfornetworkdecompositionfromsimilaritymatricesapplicationtopositionalanalyses AT mageechristopherl algorithmandmetricfornetworkdecompositionfromsimilaritymatricesapplicationtopositionalanalyses |