A Fast and Exact Greedy Algorithm for the Core–Periphery Problem
The core−periphery structure is one of the key concepts in the structural analysis of complex networks. It consists of a partitioning of the node set of a given graph or network into two groups, called core and periphery, where the core nodes induce a well-connected subgraph and share conn...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-01-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/12/1/94 |
| _version_ | 1811186176510394368 |
|---|---|
| author | Dario Fasino Franca Rinaldi |
| author_facet | Dario Fasino Franca Rinaldi |
| author_sort | Dario Fasino |
| collection | DOAJ |
| description | The core−periphery structure is one of the key concepts in the structural analysis of complex networks. It consists of a partitioning of the node set of a given graph or network into two groups, called core and periphery, where the core nodes induce a well-connected subgraph and share connections with peripheral nodes, while the peripheral nodes are loosely connected to the core nodes and other peripheral nodes. We propose a polynomial-time algorithm to detect core−periphery structures in networks having a symmetric adjacency matrix. The core set is defined as the solution of a combinatorial optimization problem, which has a pleasant symmetry with respect to graph complementation. We provide a complete description of the optimal solutions to that problem and an exact and efficient algorithm to compute them. The proposed approach is extended to networks with loops and oriented edges. Numerical simulations are carried out on both synthetic and real-world networks to demonstrate the effectiveness and practicability of the proposed algorithm. |
| first_indexed | 2024-04-11T13:41:19Z |
| format | Article |
| id | doaj.art-e278528b1e924ac493addf6905654ea7 |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-04-11T13:41:19Z |
| publishDate | 2020-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-e278528b1e924ac493addf6905654ea72022-12-22T04:21:14ZengMDPI AGSymmetry2073-89942020-01-011219410.3390/sym12010094sym12010094A Fast and Exact Greedy Algorithm for the Core–Periphery ProblemDario Fasino0Franca Rinaldi1Department of Mathematics, Computer Science and Physics, University of Udine, 33100 Udine, ItalyDepartment of Mathematics, Computer Science and Physics, University of Udine, 33100 Udine, ItalyThe core−periphery structure is one of the key concepts in the structural analysis of complex networks. It consists of a partitioning of the node set of a given graph or network into two groups, called core and periphery, where the core nodes induce a well-connected subgraph and share connections with peripheral nodes, while the peripheral nodes are loosely connected to the core nodes and other peripheral nodes. We propose a polynomial-time algorithm to detect core−periphery structures in networks having a symmetric adjacency matrix. The core set is defined as the solution of a combinatorial optimization problem, which has a pleasant symmetry with respect to graph complementation. We provide a complete description of the optimal solutions to that problem and an exact and efficient algorithm to compute them. The proposed approach is extended to networks with loops and oriented edges. Numerical simulations are carried out on both synthetic and real-world networks to demonstrate the effectiveness and practicability of the proposed algorithm.https://www.mdpi.com/2073-8994/12/1/94complex networkscore–periphery structurecombinatorial optimizationgreedy algorithmpower-law networks |
| spellingShingle | Dario Fasino Franca Rinaldi A Fast and Exact Greedy Algorithm for the Core–Periphery Problem Symmetry complex networks core–periphery structure combinatorial optimization greedy algorithm power-law networks |
| title | A Fast and Exact Greedy Algorithm for the Core–Periphery Problem |
| title_full | A Fast and Exact Greedy Algorithm for the Core–Periphery Problem |
| title_fullStr | A Fast and Exact Greedy Algorithm for the Core–Periphery Problem |
| title_full_unstemmed | A Fast and Exact Greedy Algorithm for the Core–Periphery Problem |
| title_short | A Fast and Exact Greedy Algorithm for the Core–Periphery Problem |
| title_sort | fast and exact greedy algorithm for the core periphery problem |
| topic | complex networks core–periphery structure combinatorial optimization greedy algorithm power-law networks |
| url | https://www.mdpi.com/2073-8994/12/1/94 |
| work_keys_str_mv | AT dariofasino afastandexactgreedyalgorithmforthecoreperipheryproblem AT francarinaldi afastandexactgreedyalgorithmforthecoreperipheryproblem AT dariofasino fastandexactgreedyalgorithmforthecoreperipheryproblem AT francarinaldi fastandexactgreedyalgorithmforthecoreperipheryproblem |