Generation of networks with prescribed degree-dependent clustering

Chrysanthos E. Gounaris, Karthikeyan Rajendran, Ioannis G. Kevrekidis, Christodoulos A. Floudas

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

We propose a systematic, rigorous mathematical optimization methodology for the construction, "on demand," of network structures that are guaranteed to possess a prescribed collective property: the degree-dependent clustering. The ability to generate such realizations of networks is important not only for creating artificial networks that can perform desired functions, but also to facilitate the study of networks as part of other algorithms. This problem exhibits large combinatorial complexity and is difficult to solve with off-the-shelf commercial optimization software. To that end, we also present a customized preprocessing algorithm that allows us to judiciously fix certain problem variables and, thus, significantly reduce computational times. Results from the application of the framework to data sets resulting from simulations of an acquaintance network formation model are presented.

Original languageEnglish (US)
Pages (from-to)435-451
Number of pages17
JournalOptimization Letters
Volume5
Issue number3
DOIs
StatePublished - Aug 1 2011

All Science Journal Classification (ASJC) codes

  • Control and Optimization

Keywords

  • Clustering
  • Graph theory
  • Mathematical optimization
  • Networks

Fingerprint Dive into the research topics of 'Generation of networks with prescribed degree-dependent clustering'. Together they form a unique fingerprint.

  • Cite this

    Gounaris, C. E., Rajendran, K., Kevrekidis, I. G., & Floudas, C. A. (2011). Generation of networks with prescribed degree-dependent clustering. Optimization Letters, 5(3), 435-451. https://doi.org/10.1007/s11590-011-0319-x