22666

ارايه ي روشي جهت برچسب گذاري گره هاي گراف شبكه اجتماعي با استفاده از ساختار همسايگي گره ها

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

نرم افزار

1394

1397/9/21

دكتر عين اله خنجري

كامپيوتر

چكيده با رشد روز افزون شبكه¬هاي اجتماعي و نيز نقش آن¬ها در تبادل اطلاعات، امروزه در اين حوزه با حجم بسيار بالاي داده¬ها مواجه هستيم. با توجه به نامشخص بودن داده¬هاي شبكه به دلايلي همچون وارد نكردن اطلاعات به طور كامل توسط كاربر، برچسب بسياري از كاربران مشخص نمي‌باشد. ازآنجاكه تعيين برچسب داده¬ها منجر به يافتن الگوهاي خاص و باارزش در زمينه¬هاي كاربردي مختلف همچون بازاريابي و كسب‌وكار مي¬شود لذا روش¬هاي كاوش از جمله رده¬بندي به‌منظور تعيين برچسب اين داده¬ها موردنياز مي¬باشند. آنچه كه در طراحي يك رده¬بند خودكار از اهميت بالايي برخوردار است، پايگاه داده¬اي است كه در فاز آمورش استفاده مي‌شود. پايگاه داده آموزشي موجود متشكل از داده¬هاي برچسب‌دار و بدون برچسب مي‌باشد. جمع‌آوري نمونه-هاي برچسب¬دار معمولاً سخت، هزينه¬بر و زمان¬بر هستند. درحالي‌كه جمع¬آوري داده¬هاي بدون برچسب نسبتاً آسان و كم‌هزينه مي¬باشد. در روش¬هاي سنتي رده¬بندي فقط مجموعه داده¬هاي برچسب¬دار به عنوان داده¬هاي آموزشي جهت آموزش رده¬بند¬ها مورد استفاده قرار مي¬گرفتند. اما نحوه توزيع نمونه‌هاي بدون برچسب در كنار نمونه‌هاي برچسب¬دار باعث بهبود دقت رده‌بندي مي‌شوند. بنابراين در سازوكار پيشنهادي جهت رده¬بندي از روش نيمه¬نظارتي مبتني بر گراف استفاده شده است. يكي از روش¬هاي مهم نيمه¬نظارتي مبتني برگراف الگوريتم انتشار برچسب مي¬باشد. روش انتشار برچسب بر روي يك گراف شباهت اعمال مي¬شود كه تنها از ويژگي¬هاي پروفايلي براي محاسبه شباهت دو گره استفاده شده است ما در روش ارائه شده در اين سازوكار از هر دو ويژگي ساختاري و پروفايلي جهت ساخت گراف شباهت استفاده مي¬كنيم. مسئله ديگر وجود ناهمگوني در كلاس برچسب مي¬باشد كه در جهان واقعي دو نوع ارتباط بين دو فرد با برچسب مشابه ومتفاوت وجود دارد درحالي كه در روش پيشين تنها نوع مشابه را در نظر گرفته-اند. بنابراين عدم توجه به اين مهم خود موجب كاهش دقت رده¬بند خواهد شد براي حل اين چالش در سازوكار پيشنهادي جهت تعيين ميزان اثر برچسب انتقالي با توجه به نوع ارتباط پيش رو از ماتريسي تحت عنوان ماتريس وابستگي استفاده شده است. كه اين ماتريس با استفاده از دو نوع ارتباط محاسبه شده است. با اعمال سازوكار پيشنهادي بر روي مجموعه داده Pokec ملاحظه شد كه سازوكار پيشنهادي تا حد مطلوبي موجب افزايش دقت رده¬بندي شده است. واژه¬هاي كليدي: رده¬بندي نيمه نظارتي، مبتني بر گراف، ويژگي ساختاري، انتشار برچسب

1398/07/17

Design and Implementaion of a Mechanism for labeling of Social Network Graph’s Nodes using Structural Neighborhood of Nodes

12/12/2018 12:00:00 AM

Abstract With the growing growth of social networks and the role they play in data exchange, today we are faced with a huge amount of data. Due to the uncertainty of the network data due to reasons such as the lack of complete information by the user, the label of many users is not specified. Since the identification of data labels leads to the search for specific and valuable patterns in various applications such as marketing and business, mining methods, including classification, are needed to determine the label of these data. What is important in designing an automated classification is the database used in its phase. The existing educational database consists of labeled and unlabeled data. Collecting sample labels is usually hard, costly and time consuming. While collecting unlabeled data is relatively easy and inexpensive. In traditional classification methods, only labeled data sets were used as training data for classifications. But the distribution of unlabeled samples along with labeled samples improves the classification accuracy. Therefore, in the proposed mechanism for classification a graph-based semi- supervised method is used. One of the important algorithms for graph based semi- supervised algorithms is label propagation. The label propagation method is applied to a similarity graph, which uses only profile attributes to calculate the similarity of the two nodes. In the method presented in this mechanism, we use both structural and profile properties to construct the similarity graph. Another issue is the existence of heterogeneity in the label class. Which is in the real world, there are two types of communication between two individuals with similar and dissimilar labels, while in the previous method, they only consider the similar type. Therefore, the lack of attention to this will reduce the accuracy of the classification. To solve this challenge, for determining the effect of the transfer label in the proposed mechanism, based on the kind of forward-looking relationship matrix called the dependency matrix has been used. Where this matrix is calculated using two types of relationships. Keywords: Classification semi-supervised, graph-based, structural characteristics, label propagation