Ultra-small world detection in networks: subgraphs with prescribed distance distributions.
Saved in:
| Title: | Ultra-small world detection in networks: subgraphs with prescribed distance distributions. |
|---|---|
| Authors: | Veremyev, Alexander1 (AUTHOR) alexander.veremyev@ucf.edu, Boginski, Vladimir1 (AUTHOR) vladimir.boginski@ucf.edu, Pasiliao, Eduardo L.2 (AUTHOR) eduardo.pasiliao@us.af.mil, Prokopyev, Oleg A.3 (AUTHOR) oleg.prokopyev@business.uzh.ch |
| Source: | Computational Optimization & Applications. Dec2025, Vol. 92 Issue 3, p1069-1121. 53p. |
| Subjects: | Subgraphs, Graph theory, Mixed integer linear programming, Empirical research, Euclidean distance, Spatial analysis (Statistics) |
| Abstract: | We introduce a class of distance-based clique relaxation models, which enforce certain distributions on vertex pairwise distances in the corresponding induced subgraphs. Both "local" and "global" versions of the proposed approach are studied. For the global case, the distribution of distances is considered for all vertex pairs in the subgraph. For the local (and, in a sense, more restrictive) case, the required property must be satisfied for any vertex with respect to its distances to the other vertices in the subgraph. We refer to the proposed clique relaxations as global and local γ -ultra-small worlds, respectively, where parameter γ controls the required distance distributions. Our modeling approach has several meaningful interpretations; in particular, it is closely related to the concept of an "effective" graph diameter. Furthermore, density- and degree-based quasi-cliques are two well-known special cases of the proposed concept. We exploit these relationships to develop mixed integer programs (MIPs) that can be used with an off-the-shelf solver for finding maximum global and local ultra-small worlds. Then, we outline a simple-to-implement algorithm that iteratively solves feasibility versions of our MIPs for each possible subgraph size within some lower and upper bounds; we derive one non-trivial upper bound using the linear programming relaxations. Our modeling approach also generalizes the k-club concept; hence, some links to this well-known distance-based clique relaxation are also explored. Finally, to illustrate the obtained results, we perform a computational study on graphs representing various types of real-world datasets and systems. Some interesting empirical observations and insights are provided. [ABSTRACT FROM AUTHOR] |
| Copyright of Computational Optimization & Applications is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | We introduce a class of distance-based clique relaxation models, which enforce certain distributions on vertex pairwise distances in the corresponding induced subgraphs. Both "local" and "global" versions of the proposed approach are studied. For the global case, the distribution of distances is considered for all vertex pairs in the subgraph. For the local (and, in a sense, more restrictive) case, the required property must be satisfied for any vertex with respect to its distances to the other vertices in the subgraph. We refer to the proposed clique relaxations as global and local γ -ultra-small worlds, respectively, where parameter γ controls the required distance distributions. Our modeling approach has several meaningful interpretations; in particular, it is closely related to the concept of an "effective" graph diameter. Furthermore, density- and degree-based quasi-cliques are two well-known special cases of the proposed concept. We exploit these relationships to develop mixed integer programs (MIPs) that can be used with an off-the-shelf solver for finding maximum global and local ultra-small worlds. Then, we outline a simple-to-implement algorithm that iteratively solves feasibility versions of our MIPs for each possible subgraph size within some lower and upper bounds; we derive one non-trivial upper bound using the linear programming relaxations. Our modeling approach also generalizes the k-club concept; hence, some links to this well-known distance-based clique relaxation are also explored. Finally, to illustrate the obtained results, we perform a computational study on graphs representing various types of real-world datasets and systems. Some interesting empirical observations and insights are provided. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 09266003 |
| DOI: | 10.1007/s10589-024-00640-1 |
