بهبود الگوريتم DeepWalk براي پيش‌بيني پيوند در شبكه‌هاي اجتماعي

Improving the DeepWalk Algorithm for Link Prediction in Social Networks

رشد روزافزون شبكه‌هاي اجتماعي توجه محققان را به پيش‌بيني پيوند جلب كرده است و در بسياري از زمينه‌ها از جمله علوم كامپيوتر، علم اطلاعات و انسان‌شناسي مورد استفاده قرار گرفته است. يكي از جديدترين روش‌هاي پيش‌بيني پيوند، روش‌هاي جاسازي گراف است كه براي توليد بردار ويژگي براي هر گره از گراف و يافتن پيوندهاي ناشناخته استفاده مي‌شود. الگوريتم DeepWalk يكي از محبوب‌ترين روش‌هاي جاسازي گراف است كه ساختار شبكه را با استفاده از گام تصادفي با احتمال يكسان، حفظ مي‌كند. در اين مقاله يك نسخه اصلاح‌شده از الگوريتم DeepWalk پيشنهاد شده است كه از يك مدل جديد گام تصادفي براي حل مسئله پيش‌بيني پيوند استفاده مي‌كند. درواقع در روش پيشنهادي مقدار اندازه شباهت ساختاري و شباهت ويژگي‌هاي مهم گره‌ها، با هم تركيب مي‌شوند. نتايج نشان مي‌دهد كه دو گره در صورت داشتن ساختار و ويژگي‌هاي مهم مشابه، احتمال بيشتري براي ايجاد پيوند دارند. براي ارزيابي روش پيشنهادي، آزمايش‌ها بر روي پنج مجموعه داده، انجام شده است. نتايج آزمايش حاكي از بهبود نسبي در نتايج به دست آمده است.

The increasing growth of social networks has drawn researchers attention to link prediction, and it has been used in many fields, including computer science, information science, and anthropology. One of the newest link prediction methods is graph embedding methods, which are used to generate a feature vector for each node of the graph and find unknown links. The DeepWalk algorithm is one of the most popular graph embedding methods that captures the network structure using a random walk with equal probability. In this paper, a modified version of the DeepWalk algorithm is proposed, which uses a new random walk model to solve the link prediction problem. In fact, in the proposed method, the amount of structural similarity and the similarity of important features of nodes are combined. The results show that two nodes are more likely to form a link if they have similar structure and important features. To evaluate the proposed method, experiments have been conducted on five datasets. The test results indicate a relative improvement in the results obtained.