28566

پيش بيني ويژگي هاي يك گراف با استفاده از روش هاي داده كاوي

دكتري تخصصي (PhD)

رياضي- جبر

1399

1402/4/24

مهدي علائيان

دانشكده رياضي

پوچي يك گراف وجود تعداد صفرها به عنوان مقدار ويژه در طيف آن است. محاسبات پوچي به طور گسترده براي تعيين پايداري يك مولكول شيميايي استفاده مي شود. براي محاسبه عدد پوچي فرمول‌هايي براي گراف هاي خاص ارائه شده اند، اما به خاطر سپردن فرمول هر گراف خاص چالش برانگيز است و براي همه انواع گراف ها فرمول وجود ندارد. اما با استفاده از رتبه گراف مي توان عدد پوچي را محاسبه كرد. ولي، زمان پردازش با رشد تعداد رئوس گراف ها افزايش مي يابد. اكثر ويژگي هاي گراف، از جمله كمر، عدد خوشه و عدد استقلال مشكل ياد شده را دارا هستند. لذا، در اين پايان نامه، با بررسي روش هاي يادگيري ماشين براي محاسبه مقادير ويژگي هاي گراف، ازجمله پوچي، كمر، عدد خوشه و عدد استقلال راهكاري پيشنهاد مي كند. در اين راستا، از روش‌هاي توليد گرافهاي تصادفي براي جمع‌آوري نمونه‌ هاي تحت آموزش استفاده مي شود. دقت نتايج تجربي حاصله بر روي مجموعه داده هاي جمع آوري شده برابر با 91.33، 90.51، 91.61 و 99.98 در صد به ترتيب براي طبقه‌ بندي دودويي مقدار پوچي، عدد خوشه، كمر وعدد استقلال حاصل شده است. همچنين، ضريب همبستگي بهترين نتايج تجربي حاصله بر روي مجموعه داده هاي جمع آوري شده برابر با 0.95، 0.9703، 0.9393 و 0.992 به ترتيب براي پيش ‌بيني مقدار پوچي، عدد خوشه، كمر و عدد استقلال حاصل شده است.

1402/05/07

Predict the properties of a graph Using Data mining techniques

7/14/2024 12:00:00 AM

The nullity of a graph is the existence of zeros as eigenvalues in its spectrum. Nullity calculations are widely used to determine the stability of a chemical molecule. To calculate the nullity, formulas have been presented for specific graphs, but memorizing the formula of each specific graph is challenging and there is no formula for all types of graphs. But by using the rank of the graph, one can calculate the nullity. However, processing time increases with the growth of the number of vertices of graphs. Most graph properties, including girth, clique number and independence set number, have the same problem. Therefore, in this thesis, by examining machine learning methods for calculating graph property values, including nullity, girth, clique number and independence set number, a solution is proposed. In this regard, random graph generation methods are used to collect training samples. The accuracy of the experimental results obtained on the collected data sets is 91.33, 90.51, 91.61 and 99.98 percentage for binary classification of nullity, clique number, girth and independence set number, respectively. Also, the correlation coefficient of the best experimental results obtained on the collected data sets is 0.95, 0.9703, 0.9393 and 0.992 for predicting the value of nullity, clique number, girth and independence set number, respectively.

يادگيري ماشين , پوچي يك گراف , عدد استقلال , عدد خوشه اي , كمر

Machine Learning , Nullity of graph , Independent number , clique number , girth

Karrar Khazir

Dr. Mehdi Alaeiyan