Solving Maximum Clique Problem in Stochastic Graphs Using Learning Automata

被引：0

作者：

Soleimani-Pouri, Mohammad ^{[1
]}

Rezvanian, Alireza ^{[2
]}

Meybodi, Mohammad Reza ^{[2
]}

机构：

[1] Islamic Azad Univ, Dept Elect Comp & Biomed Engn, Qazvin, Iran

[2] Amirkabir Univ Technol, Comp Engn & Informat Technol Dept, Tehran, Iran

来源：

2012 FOURTH INTERNATIONAL CONFERENCE ON COMPUTATIONAL ASPECTS OF SOCIAL NETWORKS (CASON) | 2012年

关键词：

maximum clique problem; NP-Hard; stochastic graph; learning automata; social networks; ALGORITHMS;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The maximum clique of a given graph G is the subgraph C of G such that two vertices in C are adjacent in G with maximum cardinality. Finding the maximum clique in an arbitrary graph is an NP-Hard problem, motivated by the social networks analysis. In the real world applications, the nature of interaction between nodes is stochastic and the probability distribution function of the vertex weight is unknown. In this paper a learning automata-based algorithm is proposed for solving maximum clique problem in the stochastic graph. The simulation results on stochastic graph demonstrate that the proposed algorithm outperforms standard sampling method in terms of the number of samplings taken by algorithm.

引用

页码：115 / 119

页数：5

共 17 条

[1]

Amiri F, 2013, ADV INTELL SYST COMP, V182, P443

[2] Utilizing distributed learning automata to solve stochastic shortest path problems [J].

Beigy, Hamid ;

Meybodi, M. R. .

INTERNATIONAL JOURNAL OF UNCERTAINTY FUZZINESS AND KNOWLEDGE-BASED SYSTEMS, 2006, 14 (05) :591-615

[3] R-EVO: A Reactive Evolutionary Algorithm for the Maximum Clique Problem [J].

Brunato, Mauro ;

Battiti, Roberto .

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2011, 15 (06) :770-782

[4] Incremental K-clique clustering in dynamic social networks [J].

Duan, Dongsheng ;

Li, Yuhua ;

Li, Ruixuan ;

Lu, Zhengding .

ARTIFICIAL INTELLIGENCE REVIEW, 2012, 38 (02) :129-147

[5]

Karp R.M., 1972, PLENUM PRESS SURV ST, P85, DOI 10.1007/978-1-4684-2001-2_9

[6] On the scalability of biocomputing algorithms: The case of the maximum clique problem [J].

Manrique, Daniel ;

Rodriguez-Paton, Alfonso ;

Sosik, Petr .

THEORETICAL COMPUTER SCIENCE, 2011, 412 (51) :7075-7086

[7] Cliques with maximum/minimum edge neighborhood and neighborhood density [J].

Martins, Pedro .

COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (03) :594-608

[8] CLICOM: Cliques for combining multiple clusterings [J].

Mimaroglu, Selim ;

Yagci, Murat .

EXPERT SYSTEMS WITH APPLICATIONS, 2012, 39 (02) :1889-1901

[9]

Narendra K. S., 1989, Learning Automata: An Introduction

[10]

Rezvanian A., 2010, 2010 Second World Congress on Nature and Biologically Inspired Computing (NaBIC 2011), P479, DOI 10.1109/NABIC.2010.5716360

← 1 2 →