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.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 189681707 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Ultra-small world detection in networks: subgraphs with prescribed distance distributions. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Veremyev%2C+Alexander%22">Veremyev, Alexander</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> alexander.veremyev@ucf.edu</i><br /><searchLink fieldCode="AR" term="%22Boginski%2C+Vladimir%22">Boginski, Vladimir</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> vladimir.boginski@ucf.edu</i><br /><searchLink fieldCode="AR" term="%22Pasiliao%2C+Eduardo+L%2E%22">Pasiliao, Eduardo L.</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> eduardo.pasiliao@us.af.mil</i><br /><searchLink fieldCode="AR" term="%22Prokopyev%2C+Oleg+A%2E%22">Prokopyev, Oleg A.</searchLink><relatesTo>3</relatesTo> (AUTHOR)<i> oleg.prokopyev@business.uzh.ch</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Computational+Optimization+%26+Applications%22">Computational Optimization & Applications</searchLink>. Dec2025, Vol. 92 Issue 3, p1069-1121. 53p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Subgraphs%22">Subgraphs</searchLink><br /><searchLink fieldCode="DE" term="%22Graph+theory%22">Graph theory</searchLink><br /><searchLink fieldCode="DE" term="%22Mixed+integer+linear+programming%22">Mixed integer linear programming</searchLink><br /><searchLink fieldCode="DE" term="%22Empirical+research%22">Empirical research</searchLink><br /><searchLink fieldCode="DE" term="%22Euclidean+distance%22">Euclidean distance</searchLink><br /><searchLink fieldCode="DE" term="%22Spatial+analysis+%28Statistics%29%22">Spatial analysis (Statistics)</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=189681707 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s10589-024-00640-1 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 53 StartPage: 1069 Subjects: – SubjectFull: Subgraphs Type: general – SubjectFull: Graph theory Type: general – SubjectFull: Mixed integer linear programming Type: general – SubjectFull: Empirical research Type: general – SubjectFull: Euclidean distance Type: general – SubjectFull: Spatial analysis (Statistics) Type: general Titles: – TitleFull: Ultra-small world detection in networks: subgraphs with prescribed distance distributions. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Veremyev, Alexander – PersonEntity: Name: NameFull: Boginski, Vladimir – PersonEntity: Name: NameFull: Pasiliao, Eduardo L. – PersonEntity: Name: NameFull: Prokopyev, Oleg A. IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 12 Text: Dec2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 09266003 Numbering: – Type: volume Value: 92 – Type: issue Value: 3 Titles: – TitleFull: Computational Optimization & Applications Type: main |
| ResultId | 1 |
