Edge Importance in Complex Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909242192035840 |
|---|---|
| author | Noschese, Silvia Reichel, Lothar |
| author_facet | Noschese, Silvia Reichel, Lothar |
| contents | Complex networks are made up of vertices and edges. The latter connect the vertices. There are several ways to measure the importance of the vertices, e.g., by counting the number of edges that start or end at each vertex, or by using the subgraph centrality of the vertices. It is more difficult to assess the importance of the edges. One approach is to consider the line graph associated with the given network and determine the importance of the vertices of the line graph, but this is fairly complicated except for small networks. This paper compares two approaches to estimate the importance of edges of medium-sized to large networks. One approach computes partial derivatives of the total communicability of the weights of the edges, where a partial derivative of large magnitude indicates that the corresponding edge may be important. Our second approach computes the Perron sensitivity of the edges. A high sensitivity signals that the edge may be important. The performance of these methods and some computational aspects are discussed. Applications of interest include to determine whether a network can be replaced by a network with fewer edges with about the same communicability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_16862 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Edge Importance in Complex Networks Noschese, Silvia Reichel, Lothar Physics and Society Social and Information Networks 05C82, 15A16, 65F15 Complex networks are made up of vertices and edges. The latter connect the vertices. There are several ways to measure the importance of the vertices, e.g., by counting the number of edges that start or end at each vertex, or by using the subgraph centrality of the vertices. It is more difficult to assess the importance of the edges. One approach is to consider the line graph associated with the given network and determine the importance of the vertices of the line graph, but this is fairly complicated except for small networks. This paper compares two approaches to estimate the importance of edges of medium-sized to large networks. One approach computes partial derivatives of the total communicability of the weights of the edges, where a partial derivative of large magnitude indicates that the corresponding edge may be important. Our second approach computes the Perron sensitivity of the edges. A high sensitivity signals that the edge may be important. The performance of these methods and some computational aspects are discussed. Applications of interest include to determine whether a network can be replaced by a network with fewer edges with about the same communicability. |
| title | Edge Importance in Complex Networks |
| topic | Physics and Society Social and Information Networks 05C82, 15A16, 65F15 |
| url | https://arxiv.org/abs/2404.16862 |