TY - GEN
T1 - Robust optimization of graph partitioning and critical node detection in analyzing networks
AU - Fan, Neng
AU - Pardalos, Panos M.
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=78650827337&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78650827337&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-17458-2_15
DO - 10.1007/978-3-642-17458-2_15
M3 - Conference contribution
AN - SCOPUS:78650827337
SN - 3642174574
SN - 9783642174575
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 170
EP - 183
BT - Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Proceedings
T2 - 4th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2010
Y2 - 18 December 2010 through 20 December 2010
ER -