Graph theoretic generalizations of clique: optimization and extensions
Graph theoretic generalizations of clique: optimization and extensions
复制标题
派系的图论概括：优化和扩展
DOI：
10.1007/bf02019432
复制
发表时间：
2009
影响因子：
0.8
通讯作者：
Balabhaskar Balasundaram
中科院分区：
文献类型：
--
作者：
Balabhaskar Balasundaram
团的图论推广：优化和扩展。（2007年8月）Balabhaskar Balasundaram，B. Tech，印度理工学院-马德拉斯咨询委员会主席：Sergiy Butenko博士这篇论文认为最大团问题的图论推广。最初在社会网络分析文献中提出的模型，首次从数学规划的角度进行了研究。社交网络通常用图来表示，派系是社交网络中“紧密结合的群体”的第一个模型，被称为有凝聚力的子群体。集团是理想化的模型，其过度限制的性质促使集团放松的发展，放松集团的不同方面。识别社交网络中的大型内聚子群传统上用于犯罪网络分析，以研究恐怖主义、毒品和洗钱等有组织犯罪。最近的应用是在聚类和数据挖掘无线网络，生物网络以及数据库和互联网的图形模型。这项研究有可能影响国土安全，生物信息学，互联网研究和电信行业等。本论文的重点是一个基于度的松弛称为k-plex。本文还研究了一种基于距离的松弛算法k-clique和一种基于直径的松弛算法kclub。我们提出了第一个系统的研究这些问题的复杂性方面和应用数学规划技术解决这些问题。该模型的图论属性被识别并用于理论和算法的发展。与这三个模型相关的优化问题被公式化为双-
Graph Theoretic Generalizations of Clique: Optimization and Extensions. (August 2007) Balabhaskar Balasundaram, B.Tech., Indian Institute of Technology – Madras Chair of Advisory Committee: Dr. Sergiy Butenko This dissertation considers graph theoretic generalizations of the maximum clique problem. Models that were originally proposed in social network analysis literature, are investigated from a mathematical programming perspective for the first time. A social network is usually represented by a graph, and cliques were the first models of “tightly knit groups” in social networks, referred to as cohesive subgroups. Cliques are idealized models and their overly restrictive nature motivated the development of clique relaxations that relax different aspects of a clique. Identifying large cohesive subgroups in social networks has traditionally been used in criminal network analysis to study organized crimes such as terrorism, narcotics and money laundering. More recent applications are in clustering and data mining wireless networks, biological networks as well as graph models of databases and the internet. This research has the potential to impact homeland security, bioinformatics, internet research and telecommunication industry among others. The focus of this dissertation is a degree-based relaxation called k-plex. A distance-based relaxation called k-clique and a diameter-based relaxation called kclub are also investigated in this dissertation. We present the first systematic study of the complexity aspects of these problems and application of mathematical programming techniques in solving them. Graph theoretic properties of the models are identified and used in the development of theory and algorithms. Optimization problems associated with the three models are formulated as bi-