15043

13540

كارشناسي ارشد

رياضي كاربردي (گراف تركيبيات)

اصفهان : دانشگاه صنعتي اصفهان

1398

شش، 100ص. :مصور، نمودار

رامين جوادي جورتاني

غلامرضا اميدي، بهناز عمومي

1398/06/25

كتابنامه

رياضي

رياضي

1398/06/25

2559251

MCL Algorithm in Graph Clustering Behzad Yazdani b yazdani@math iut ac ir June 24 2019 Master of Science Thesis in Farsi Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156 8311 IranSupervisor Dr Ramin Javadi rjavadi@cc iut ac irAdvisor 2010 MSC 91C20 62H30 60J05Keywords Graph clustering Random walk MCL algorithm Diagonal similar and Equilibrium state Abstract This M Sc thesis is based on the following papers S M Graph Clustering by Flow Simulation PhD thesis Utrecht University of Utrecht V D 2000 S E Graph clustering Computer science review 2007 SGraph clustering is in fact a technique to analyze a considerable amount of data modeled by graphs in a more preciseand convenient way As a matter of fact graph clustering has received a lot of attention because of its ability tocreate collections of data in which the data involved have certain similar characteristics Moreover this science hassignificant number of applications in various other fields such as genetics image processing facial recognition recommender systems social media machine learning etc in this dissertation our goal is to survey the science of graph clustering and its features and provide an overview ofseveral algorithms including k means clustering algorithm which has a wide range of applications in statistics Amajor part of this the sis deals with MCL algorithm and the analysis of their outputs and the relationship between thisalgorithm and graph clustering Furthermore a number of criteria for the relative comparison of different types of clusterings on a graph have beenintroduced which can be of use in choosing an appropriate algorithm regarding the kind of the problem in hand The first chapter is devoted to the elementary definitions and concepts so that the reader may gain a better and deeperunderstanding of the science of clusterings In the second chapter several algorithms are introduced and some of their characteristics are analyzed Chapters 3and 4 are devoted to the introduction of MCL algorithm and analysis of its outputs The stability of the algorithmis discussed in those chapters too In chapter 5 a special type of matrices is introduced and their structure and theirrelation to MCL algorithm is analyzed Finally in the last chapter some criteria to compare different clusterings on agraph are given This thesis can be a first step for any one interested in carrying out research in this field of science and its applicationsin real world

رامين جوادي جورتاني

غلامرضا اميدي، بهناز عمومي