در اینجا تمام سورس ها و کدهای پایان نامه ارشدم رو به اشتراک گذاشتم تا کمکی باشه به افرادی که در حوزه پیشگویی پیوند کار می کنند. روش پیشنهادی ما پیشگویی پیوند منفی برای گراف های وزن دار و بدون وزن است.
الگوریتم های که پیاده سازی شده:
-
CN = Common Neighbors
-
JC = Jaccard’s Coefficient
-
AA = Adamic Adar
-
PA = Preferential Attachment
-
DC = Degree Centrality
-
EC = Eigenvector Centrality
-
CC = Closeness Centrality
-
BC = Betweenness Centrality
-
RW = Random Walk Betweenness Centrality
-
LC = Load Centrality
-
BC = Betweenness Centrality
-
Ktz = Katz
-
ACC = Accuracy
-
PRE = Precision
-
REC = recall
-
F = f-score
-
Line Graph
We also proposed a new approach for weighted negative link predictionand a new method for adding the anomolus links into weighted graphs. Anomaly detection is a very important and vital task, and it has many applications in various fields such as security, health, finance, health care and law enforcement. In recent years, many techniques for diagnosing abnormalities or discarded data have been proposed in non-structured sets of multidimensional data, some of which have focused on graph structure. This thesis is based on the detection of edge anomaly in the graph. Two methods have been proposed based on negative link prediction for the detection of edge anomalies. The first methods are for simple graphs and the second one is for weighted graphs. In both methods anomalous edges are removed from the graph based on the negative link prediction algorithm. For both proposed methods, four unsupervised basic link prediction algorithms, the Jaccard’s Coefficient, Preferential Attachment, Common Neighbors, Adamic/Ader were used. We also used four standard dataset Dolphins, Trinity100, Netscience and Email networks for simple graphs, and four Lesmis, King James, Netscience and Adolescent networks for weighted graphs. In order to evaluate the first proposed method, we added some anomaly nodes to the graph and employed eight extra competitor meaures in order to find them. The evaluation metric was precision, recall and f-measure. For the second method, we got help from community detection improvement for evaluation. Two community detection algorithms, Asynchronous Label Propagation and optimized Girvan-Newman were used. Evalution metric for quality of the community detection methods was modularity, performance and coverage. We also proposed a new approach for weighted negative link predictionand a new method for adding the anomolus links into weighted graphs. Results show the superiority of the proposed methods. Future works can deploy other link prediction algorithms and other graph types.
Keyword: Anomaly Detection, Anomaly Detection edge, Anomlay Detection Graph, Link prediction, Negative link prediction
تشخیص ناهنجاری در دادهها یک کار بسیار مهم و حیاتی است و کاربردهای زیادی در حوزههای مختلف از جمله امنیت، سلامت، امور مالی، مراقبتهای بهداشتی و اجرای قانون دارد. در سالهای اخیر روشهای زیادی برای تشخیص ناهنجاری یا دادههای پرت در مجموعههای بدون ساختار دادههای چند بعدی ارائه شده است که بعضی از این روشها روی ساختار گراف متمرکز شدهاند. در این پایان نامه بر روی تشخیص ناهنجاری یال در گراف کار شده و دو روش بر اساس پیشگویی پیوند منفی برای تشخیص ناهنجاری یال پیشنهاد شده است. روش اول برای گرافهای بدون وزن و روش دوم برای گرافهای وزندار ارائه شده و بر اساس عملکرد این روشها، یالهای ناهنجار در گراف با الگوریتم پیشگویی پیوند منفی تشخیص داده شده است. در دو روش پیشنهادی، از چهار الگوریتم پیشگویی پیوند، شاخص جاکارد، پیوست امتیازدهی، همسایههای مشترک و آدمیک-آدر به صورت بدون نظارت و مجزا استفاده شده است. همچنین از چهار مجموعه داده استاندارد دلفین، جاز، ایمیل و ترینیتی برای گرافهای بدون وزن و از چهار مجموعه داده لسمیس ،1پادشاه جیمز ،2شبکه علمی 3و نوجوان 4برای گرافهای وزندار استفاده شده است. به منظور ارزیابی و کارایی روش پیشنهادی اول، چند درصد از کل یالهای گراف، یال ناهنجار به گرافها اضافه شد و با استفاده از روش پیشنهادی و هشت الگوریتم دیگر سعی شده که یالهای ناهنجار تشخیص و نتایج روشها باهم مقایسه گردد. نتیاج با معیاریهای صحت، دقت، فراخوانی و معیار F1ارزیابی شده است. برای روش پیشنهادی دوم، سعی شده است که با حذف یالهای ناهنجار جوامع بهتری به وجود بیاید و جهت ارزیابی دو الگوریتم برچسب گذاری نامتقارن5و الگوریتم وزندار بهینهسازی شده گروین- نیومن مورد استفاده قرار گرفته است. سپس برای تعیین بهبود جوامع از سه تابع کیفیت اجتماعات، ماژولاریتی، کارایی 6و کاوریج ،7استفاده میشود البته نیاز به ابداع روشی برای پیشگویی پیوند منفی در گرافهای وزندار و همچنین روشی برای اضافه کردن یالهای ناهنجار به گرافهای بدون وزن نیز وجود داشت که انجام شد.
کلمات کلیدی: تشخیص ناهنجاری، تشخیص ناهنجاری یال، تشخیص ناهنجاری در گراف، پیشگویی پیوند، پیشگویی پیوند منفی
