دانلود رایگان مقاله الگوریتم ژنتیک جدید سازگار برای تشخیص ساختار جامعه

چكيده

        ساختارهاي اجتماعي در شبكه‌اي وجود دارد كه داراي پيچيدگي‌هاي زيستي، اجتماعی، تکنولوژیکی و حاوی اطلاعات مهم باشد. ساختارهای شبکه و جامعه در سیستم‌های کامپیوتری به ترتیب توسط نمودارها و زیرگراف‌ها نمایش داده می‌شود. مسئله تشخیص ساختار جامعه یک مسئله‌‌ی NP سخت است، به ویژه نتایج نهایی بهترین ساختارهای اجتماعی برای شبکه‌های بزرگ پیچیده ناشناخته هستند. در این مقاله، برای حل مسئله تشخیص ساختار جامعه یک الگوریتم مبتنی بر الگوریتم ژنتیک، AGA-net که یکی از تکنیک‌های تکاملی است پیشنهاد شده است. این الگوریتم دارای ویژگی همگرایی سریعی به مقدار بهینه بدون اینکه در بهینه محلی به دام بیافتد است بنابراین توسط پارامترهای جدید پشتیبانی شده است. شبکه دنیای واقعی که اغلب در کارهای گذشته استفاده می‌شود به‌عنوان داده‌های آزمایشی مورد استفاده قرار گرفته و نتایج به دست آمده با10 الگوریتم متفاوت مقایسه شده است. پس از تجزیه‌وتحلیل نتایج آزمون مشاهده شده است که الگوریتم پیشنهادی نتایج خوبی در مورد شبکه‌های پیچیده ارائه می‌دهد.  

1. معرفی

           درک شبکه‌ها اطلاعات مهمی درباره استخراج اطلاعات معنی‌دار از سیستم‌های پیچیده ارائه می‌دهد. در بیان معنی‌دار اطلاعات از این شبکه‌ها، اهمیت ساختارهایی که با عنوان ساختارهای اجتماعی نامگذاری شده‌اند، زیاد است. ساختارهای گراف برای ارائه شبکه‌های جهان واقعی استفاده می‌شوند. ساختارهای اجتماعی یا خوشه‌ها می‌تواند به‌عنوان زیرگراف محسوب شود  که در ساختارهای گراف به طور جزئی یا کاملا مستقل از یکدیگر هستند. به‌عنوان مثال، بافت یا اندام‌هایی که در بدن انسان نقش مشابه‌ای دارند به‌عنوان خوشه‌ها در نظر گرفته می‌شوند [1]. تشخیص ساختار جامعه (CSD) برای درک شبکه‌های زیست‌شناسی، اقتصادی، اجتماعی، فن‌آوری و غیره مهم است. این شبکه‌ها می‌توانند شبکه‌های مصنوعی یا دنیای واقعی باشند. در دنیای واقعی شبکه‌ها می‌توانند از نمونه‌هایی مانند شبکه‌های ساختار اقتصادی [2]، شبکه‌های غذایی [3]، شبکه‌های تعامل شیمیایی بین پروتئین‌ها و مولکول‌ها در سلول‌‎ها [4-6] و شبکه‌های اجتماعی مانند شبکه‌های تعیین دوستی در گروه‌ها، شبکه‌های تحلیل رابطه و شبکه‌های تشخیص حملات تروریستی باشند [7].  

         اشیاء و اتصالات در شبکه‌ها به ترتیب با گره‌ها و لبه‌ها ارائه می‌شوند. ساختارهای گراف که برای نشان دادن شبکه‌های داده شده مورد استفاده قرار می‌گیرند به‌عنوان ساده‌ترین شکل از شبکه‌های نامنظم نامیده می‌شوند [8].

         مسئله کاوش جامعه (CMP) به کشف زیرگراف معنی‌دار در بسیاری از داده‌های شبکه‌های پیچیده اشاره دارد [9]. در این مقاله، بسیاری از داده‌های دنیای واقعی توسط CMP تجزیه‌وتحلیل شده و نتایج به دست آمده در بخش نتایج تجربی نشان داده شده است.  

          روش‌های متعددی برای تشخیص ساختارهای جامعه در شبکه‌های پیچیده کشور ایجاد شده است. این روش‌ها براساس بسیاری از  ویژگی‌ها که در عین تعریف در مورد به دست آوردن بهترین نتیجه به دست نمی‌آیند، نتایج موفقیت‌آمیزی به همراه داشته‌اند. کارآیی الگوریتم‌های کارهای پیشین در شبکه‌های بزرگ بسیار پایین است. علاوه براین، برای تشخیص جامعه، الگوریتم‌های بسیاری نیاز به دانش قبلی مانند تعداد جوامع دارند. گروه‌بندی مطلوب در شبکه یک مشکل بسیار دشوار است.  بنابراین، مسئله CSD یک مسئله سخت در زمان چندجمله‌های غیردقیق (NP-H) است  [10، 11].  

          معمولا برای حل مسائل پیچیده مانند CSD دو روش متفاوت پیشنهاد می‌شود.  این روش‌ها دقیق و (متا) اکتشافی هستند [12]. از این دو روش، روش(متا) اکتشافی می‌تواند راه‌حل‌های راحت‌تری را برای مسائل پیچیده از روش‌های دقیق فراهم آورد. الگوریتم‌هایی مانند ممتیک و ژنتیک با روش‌های متا اکتشافی تحت پوشش قرار می‌گیرند و به عنوان الگوریتم‌های الهام گرفته از زیست‌شناسی شناخته می‌شوند [12]. این الگوریتم‌ها از معیارهای مختلف جامعه بنابه روش‌های خود در مسائل CSD استفاده می‌کنند. رایج‌ترین معیار اندازه‌گیری که اخیرا توسط گیرمان و نیومن استفاده شده است، معیار modularity Q است [13، 14].  

           الگوریتم شناخته شده‌ای که وجود دارد، الگوریتم تشخیص جامعه Girman-Newman  (GN) است[13، 15]. الگوریتم Fast Newman  (FN) یک الگوریتم براساس حداکثر ماژولار بودن Q [16] است. به‌طورمشابه، الگوریتم دیگری براساس حداکثر ماژول Q است که، الگوریتم سریع انحلال (fast unfolding)  نامیده می‌شود [17]. علاوه براین الگوریتم‌هایی مانند Random Walks [18]، Eigenvectors [19]، انتشار علامت (LP) [20] روش Spin Glass Type Potts [21] و الگوریتم LTE (گسترش انسجام محلی)  [22] در کارهای پیشین استفاده شده است. FN [16]، الگوریتم تشخیص جامعه برای شبکه‌های بزرگ است که توسط Clauseset و همکارانش ارائه شده است [23]، الگوریتم بهینه‌سازی فوق‌العاده [24] و الگوریتم‌های دیگری مانند این‌ها دارای پیچیدگی O (e3) از نظر پیچیدگی زمانی هستند. در اینجا e به تعداد لبه‌ها اشاره دارد [25].  

          پیچیدگی زمانی در حجم بزرگ مانند اندازه شبکه افزایش می‌یابد. در شبکه‌های کوچک یا منظم، تشخیص جامعه می‌تواند به راحتی با الگوریتم‌های ارائه شده در بالا انجام شود، اما هنگامی‌که اندازه شبکه افزایش می‌یابد، الگوریتم‌های موجود از لحاظ عملکرد و موفقیت کافی نیستند. همچنین هنگامی که ورود دانش پیشین به این الگوریتم‌ها اجباری باشد، کشف الگوریتم جدید و کارآمد اجتناب‌ناپذیر است. با توجه به این نیاز، مسائل CSD  برای حل با الگوریتم‌هایی مانند الگوریتم ژنتیک، الگوریتم بهینه‌سازی ذرات ،  الگوریتم بهینه‌سازی کلونی مورچه، الگوریتم‌های ممتیکی مورد آزمایش قرار گرفته‌اند. در این مقاله الگوریتم ژنتیک که یکی از الگوریتم‌های فوق است ساختار اصلی الگوریتم پیشنهادی را تشکیل می‌دهد. در حال حاضر الگوریتم ژنتیک از نظر محاسبات، پیچیدگی زمان و همگرایی در مسائل NP سخت بسیار موفق عمل کرده است و تقریبا در اکثر مسائل در کارهای پیشین مورد استفاده قرار گرفته است.  برای اولین بار Tasgin و همکارانش [26] از الگوریتم ژنتیک در مسئله CSD استفاده کردند. روشی که آنها توسعه دادند باعنوان GATB (یا GATHB [27] نامگذاری شده است) [25]. بعد از آن شروع به استفاده‌ی گسترده از الگوریتم ژنتیک در مسائل CSD شد. به‌طورخاص، برای به‌دست آوردن مقدار مطلوب Q به روشی ارزان‌تر نیاز است که، روش‌های بسیاری با چندین تغییر در روش ژنتیک توسعه یافته، مانند جهش (mutation)، ترکیب (crossover)، انتخاب و غیره این کار را انجام داده‌‌اند.  

            Shi و همکارانش برای حل مسئله CSD با استفاده از الگوریتم ژنتیک مبتنی بر الگوریتم GACD [28] تلاش کردند. آنها روش خود را با شبکه‌های دنیای واقعی که در کارهای گذشته بسیار زیادی استفاده شده بود آزمایش کردند و نتایج را با GN [13]،  GN Fast [23] و GATB [25] مقایسه کردند. هنگامی که نتایج به دست آمده تجزیه و تحلیل شد، دریافتند که الگوریتم‌های مبتنی بر الگوریتم ژنتیک مانند GACD و GATB برای حل مسائل CSD کاملا موثر هستند. روش‌های توسعه یافته مبتنی بر الگوریتم ژنتیک مزایای بسیاری دارد. به عنوان مثال GATB [25] دارای پیچیدگی زمانی O (e) است و هیچ دانش قبلی برای CSD نیاز ندارد. در این  مقاله، یک رویکرد جدید مبتنی بر الگوریتم ژنتیک ارائه شده است که بانام AGA-net نامگذاری شده است. AGA-net دارای پیچیدگی زمان O (e) است و نیاز به دانش قبلی ندارد. الگوریتم پیشنهاد شده مبتنی بر طراحی سازگاری از الگوریتم ژنتیک برای دستیابی به مناسب‌ترین راه‌حل در زمان کمتری برای مسئله CSD است. AGA-net در شبکه‌های داده شده در بخش 3 مورد آزمایش قرار گرفته و نتایج بدست آمده با برخی از الگوریتم‌های موجود در کارهای پیشین مقایسه شد (بخش 3 را ببینید). 

Abstract

           Community structures exist in networks which has complex biological, social, technological and so on structures and contain important information. Networks and community structures in computer systems are presented by graphs and subgraphs respectively. Community structure detection problem is NP-hard problem and especially final results of the best community structures for large-complex networks are unknown. In this paper, to solve community structure detection problem a genetic algorithm-based algorithm, AGA-net, which is one of evolutionary techniques has been proposed. This algorithm which has the property of fast convergence to global best value without being trapped to local optimum has been supported by new parameters. Real-world network which are frequently used in literature has been used as test data and obtained results have been compared with 10 different algorithms. After analyzing the test results it has been observed that the proposed algorithm gives successful results for determination of meaningful communities from complex networks.

1 Introduction

          Understanding networks provides us very important information about the extraction of meaningful information from complex systems. In eliciting meaningful information from these networks the importance of structures which are named as community structures is huge. The graph structures are used to present the realworld networks. Community structures or clusters can be considered as subgraphs which are partially or completely independent from each other in graph structures.

          As an example, tissues or organs which have the same role in the human body can be considered as clusters [1]. Community structure detection (CSD) is important to an understanding of the biological, economic, social, technological and so on networks. These networks can be synthetic or real-world networks. For real-world networks we can give some example like economic structure networks [2], food networks [3], networks of chemical interaction between proteins and molecules in cells [4-6] and social networks like networks of determination of friendship in groups, relation analysis networks and networks of detection of terrorist attacks [7].

         Objects and connections in networks are presented with nodes and edges respectively. Graph structures which are used to represent the above given networks are referred to as simplest form of undirected networks [8].

         Community mining problem (CMP) refers to discovery of meaningful subgraph in many complex networks data [9]. In this paper, many real-world data were analyzed by CMP and the obtained results are given in the experimental results section.

           Many methods have been developed for detection of community structures in complex networks. These methods give successful results according to many properties yet generalizations about obtaining the best result cannot be made. Performances of the algorithms in literature are very low on large networks. In addition, for detection of community, many algorithms need prior knowledge like community number. Optimal grouping in network is a very difficult problem. Therefore, CSD problem is a nondeterministic polynomial time - hard problem [10, 11].

          Usually to solve complex problems like CSD two different methods are proposed. These are exact and (meta-)heuristic methods [12]. From these two methods (meta-)heuristic method can offer more convenient solutions for difficult and complex problems than exact methods. Algorithms like memetic and genetic are covered by (meta-)heuristic methods and are also known as bio-inspired algorithms [12]. These algorithms use various community calculating measures according to their own methods in the CSD problems. The most common calculation measure used recently which is recommended by Girman and Newman is modularity Q measure [13, 14].

          So far the most well-known community detection algorithm is GirmanNewman (GN) algorithm [13, 15]. Fast Newman (FN) algorithm is an algorithm based on the maximum modularity Q [16]. Similarly, another algorithm based on maximum modularity Q is called Fast Unfolding algorithm [17]. In addition to these, algorithms like Random Walks [18], Eigenvectors [19], Label Propagation (LP) [20] with Spin Glass Type Potts method [21] and LTE (Local Tightness Expansion) algorithm [22] are used in the literature. FN [16], community detection algorithm for large networks which is proposed by Clauset et al. [23], Extremal Optimization [24] and other algorithms like this have O(e3 ) complexity in terms of time complexity. Here the e refers to the number of edges [25].

           Time complexity increases in a huge amount as the size of the network increases. In small or regular size networks community detection can be done very easily with algorithms given above but as the network size get larger existing algorithms are inadequate in terms of both performance and success. Also when inclusion of prior knowledge to these algorithms become mandatory, discovery of new and efficient algorithms are inevitable. Due to this need, CSD problems are tried to solve with algorithms like genetic algorithms, particle swarm optimization algorithm, ant colony optimization algorithm, memetic algorithms, and differential algorithm. In this paper genetic algorithm which is one of the above algorithms constitutes the basic structure of the proposed algorithm. Genetic algorithm is already very successful in terms of computation, time complexity and solution convergence in NP-hard problems and it is almost used in most problems in literature. For the first time Tasgin et al. [26] used genetic algorithms in CSD problem. The method that they developed was named as GATB (or GATHB [27]) [25]. After that both genetic and other algorithms started to be used widely in CSD problems. In particular, to find the optimal Q value in the most economical way, many methods have been developed by making several changes on methods of genetic algorithm like mutation, crossover, selection and so on.

           Shi et al. tried to solve the CSD problem by using genetic algorithm based GACD [28] algorithm. They tested their own method with real-world networks which are used quite a lot in the literature and compare the results with GN [13], GN Fast [23] and GATB [25] results. When the obtained results were analyzed, it was stated that genetic algorithm-based algorithms such as GACD and GATB were quite effective to solve CSD problems. There are many advantages of the developed methods based on genetic algorithm. For example GATB [25] has a time complexity of O(e) and does not require any prior knowledge for CSD. In this paper, a new approach based on genetic algorithms has been proposed and has been named as AGA-net. AGA-net has a time complexity of O(e) and does not require any prior knowledge. The proposed algorithm is based on adaptive design of genetic algorithm to reach the most appropriate solution in less time for CSD problem. AGA-net was tested in networks given in section 3 and the obtained results were compared with some existing algorithms in literature (see section 3).

چكيده

1. معرفی

1.1 تشخیص ساختار جامعه  

1.2 الگوریتم ژنتیک

2. الگوریتم پیشنهادی

2.1 نحوه نمایش ژنتیک  

2.2 جمعیت اولیه 

2.3 تابع برازندگی  

2.4 عملگرهای ژنتیک

3. نتایج تجربی  

4. نتیجه‌گیری  

منابع

Abstract

1 Introduction

1.1 Community Structure Detection

1.2 Genetic Algorithm

2 The Proposed Algorithm

2.1 Genetic Representation

2.2 Population Initialization

2.3 Fitness Function

2.4 Genetic Operators

3 Experimental Results

4 Conclusions

References