The gravity of an edge
Abstract ■■■ We describe a methodology for characterizing the relative structural importance of an arbitrary network edge by exploiting the properties of a k-shortest path algorithm. We introduce the metric Edge Gravity, measuring how often an edge occurs in any possible network path, as well as k-G...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2018-05-01
|
| Series: | Applied Network Science |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1007/s41109-018-0063-6 |
| _version_ | 1828388732737159168 |
|---|---|
| author | Mary E. Helander Sarah McAllister |
| author_facet | Mary E. Helander Sarah McAllister |
| author_sort | Mary E. Helander |
| collection | DOAJ |
| description | Abstract ■■■ We describe a methodology for characterizing the relative structural importance of an arbitrary network edge by exploiting the properties of a k-shortest path algorithm. We introduce the metric Edge Gravity, measuring how often an edge occurs in any possible network path, as well as k-Gravity, a lower bound based on paths enumerated while solving the k-shortest path problem. The methodology is demonstrated using Granovetter’s original strength of weak ties network examples as well as the well-known Florentine families of the Italian Renaissance and the Krebs 2001 terrorist networks. The relationship to edge betweenness is established. It is shown that important edges, i.e. ones with a high Edge Gravity, are not necessarily adjacent to nodes of importance as identified by standard centrality metrics, and that key nodes, i.e. ones with high centrality, often have their importance bolstered by being adjacent to bridges to nowhere–e.g. ones with low Edge Gravity. It is also demonstrated that Edge Gravity distinguishes critically important bridges or local bridges from those of lesser structural importance. |
| first_indexed | 2024-12-10T06:18:29Z |
| format | Article |
| id | doaj.art-0927891f89974d41a7c6b617140c52e1 |
| institution | Directory Open Access Journal |
| issn | 2364-8228 |
| language | English |
| last_indexed | 2024-12-10T06:18:29Z |
| publishDate | 2018-05-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | Applied Network Science |
| spelling | doaj.art-0927891f89974d41a7c6b617140c52e12022-12-22T01:59:24ZengSpringerOpenApplied Network Science2364-82282018-05-013113510.1007/s41109-018-0063-6The gravity of an edgeMary E. Helander0Sarah McAllister1IBM T. J. Watson Research Center, Applied Data ScienceCUNY Borough of Manhattan Community College, Department of MathematicsAbstract ■■■ We describe a methodology for characterizing the relative structural importance of an arbitrary network edge by exploiting the properties of a k-shortest path algorithm. We introduce the metric Edge Gravity, measuring how often an edge occurs in any possible network path, as well as k-Gravity, a lower bound based on paths enumerated while solving the k-shortest path problem. The methodology is demonstrated using Granovetter’s original strength of weak ties network examples as well as the well-known Florentine families of the Italian Renaissance and the Krebs 2001 terrorist networks. The relationship to edge betweenness is established. It is shown that important edges, i.e. ones with a high Edge Gravity, are not necessarily adjacent to nodes of importance as identified by standard centrality metrics, and that key nodes, i.e. ones with high centrality, often have their importance bolstered by being adjacent to bridges to nowhere–e.g. ones with low Edge Gravity. It is also demonstrated that Edge Gravity distinguishes critically important bridges or local bridges from those of lesser structural importance.http://link.springer.com/article/10.1007/s41109-018-0063-6Bridges to nowhereEdge betweennessk-shortest path (KSP)Edge Gravityk-GravityNode centrality |
| spellingShingle | Mary E. Helander Sarah McAllister The gravity of an edge Applied Network Science Bridges to nowhere Edge betweenness k-shortest path (KSP) Edge Gravity k-Gravity Node centrality |
| title | The gravity of an edge |
| title_full | The gravity of an edge |
| title_fullStr | The gravity of an edge |
| title_full_unstemmed | The gravity of an edge |
| title_short | The gravity of an edge |
| title_sort | gravity of an edge |
| topic | Bridges to nowhere Edge betweenness k-shortest path (KSP) Edge Gravity k-Gravity Node centrality |
| url | http://link.springer.com/article/10.1007/s41109-018-0063-6 |
| work_keys_str_mv | AT maryehelander thegravityofanedge AT sarahmcallister thegravityofanedge AT maryehelander gravityofanedge AT sarahmcallister gravityofanedge |