Robust optimization of graph partitioning and critical node detection in analyzing networks

Neng Fan, Panos M. Pardalos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

32 Scopus citations

Abstract

The graph partitioning problem (GPP) consists of partitioning the vertex set of a graph into several disjoint subsets so that the sum of weights of the edges between the disjoint subsets is minimized. The critical node problem (CNP) is to detect a set of vertices in a graph whose deletion results in the graph having the minimum pairwise connectivity between the remaining vertices. Both GPP and CNP find many applications in identification of community structures or influential individuals in social networks, telecommunication networks, and supply chain networks. In this paper, we use integer programming to formulate GPP and CNP. In several practice cases, we have networks with uncertain weights of links. Some times, these uncertainties have no information of probability distribution. We use robust optimization models of GPP and CNP to formulate the community structures or influential individuals in such networks.

Original languageEnglish (US)
Title of host publicationCombinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Proceedings
Pages170-183
Number of pages14
EditionPART 1
DOIs
StatePublished - 2010
Externally publishedYes
Event4th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2010 - Kailua-Kona, HI, United States
Duration: Dec 18 2010Dec 20 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume6508 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other4th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2010
Country/TerritoryUnited States
CityKailua-Kona, HI
Period12/18/1012/20/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Robust optimization of graph partitioning and critical node detection in analyzing networks'. Together they form a unique fingerprint.

Cite this