25676

پايش تغييرات ساختاري شبكه هاي اجتماعي با استفاده از مدلسازي گراف تصادفي

دكتري

مهندسي صنايع

1394

1400/06/28

دكتر رسول نورالسنا

دكتر احمد ماكوئي- دكتر ياسر صميمي

مهندسي صنايع

شبكه‌ها ابزاري قدرتمند براي مدلسازي روابط بين موجوديت‌ها در حوزه‌هاي مختلف سيستم‌هاي فيزيكي، زيستي، سايبري و اجتماعي هستند. هر پديده در چارچوب اين‌گونه سيستم‌ها را مي‌توان به عنوان تغيير در ساختار شبكه‌هاي متناظر با آن سيستم تعبير كرد. در اين رساله، روش‌هاي پايش شبكه‌هاي اجتماعي جهت كشف تغيير در ساختار آن‌ها توسعه داده شده و كارايي روش‌هاي پيشنهادي در كشف انواع تغيير ساختاري در شبكه اجتماعي مورد بررسي قرار مي‌گيرد. در بخش اول، يك مدل گراف تصادفي براي مدلسازي رفتار بازيگران شبكه در طول زمان توسعه داده شده كه وابستگي زماني ارتباطات افراد در زمان‌هاي مختلف در شبكه را مدلسازي مي‌كند. همچنين روشي به منظور كشف تغييرات در ساختار وابستگي زماني شبكه طراحي شده است. روش پيشنهادي وزن‌هاي يال‌ها را ناديده گرفته و بنابراين بخشي از اطلاعات مرتبط با شبكه اجتماعي از دست مي‌رود. در نتيجه به منظور استفاده بيشينه از اطلاعات موجود مرتبط با شبكه، در بخش دوم رساله، تعداد ارتباط بين افراد در شبكه به صورت ماتريسي از متغيرهاي پواسون در نظر گرفته شده و روش پايش شبكه اجتماعي مبتني بر مقادير ويژه ماتريس مجاورت آن معرفي مي‌شود. در نهايت، به منظور پوشش طيف گسترده‌تري از شبكه‌هاي اجتماعي، فرض مرتبط با توزيع تعداد ارتباطات بين افراد شبكه كنار گذاشته شده و با استفاده از آزمون فرض ناپارامتري، تغيير در توزيع چندمتغيره مقادير ويژه ماتريس مجاورت شبكه اجتماعي وزن‌دار در طول زمان بررسي شده و با استفاده از آزمون فرض مشابه، نقطه آغاز تغيير در شبكه برآورد مي‌شود. تمامي روش‌هاي پيشنهادي با استفاده از داده‌هاي واقعي و شبيه‌سازي شده اعتبارسنجي و راستي آزمايي شده و عملكرد آن با ساير روش‌هاي موجود در ادبيات موضوع مقايسه شده است. نتايج نشانگر آن است كه رويكردهاي پيشنهادي عملكرد بهتري داشته و حداقل 15% زمان كشف تغيير در شبكه را، با توجه به نوع و مقياس تغيير، بهبود مي بخشند.

1400/09/20

Monitoring Structural Changes in the Social Networks Using Random Graph Theory

1/1/1900 12:00:00 AM

A network provides powerful means of representing relationships among entities in complex physical, biological, cyber, and social systems. Any phenomena in those areas may be realized as changes in the structure of the associated networks. In this thesis, the development of approaches for monitoring social networks is investigated, and the applicability of the proposed methods in detection of structural changes in social networks is assessed. In the first section, a random graph model is proposed to model behaviors of the actors in a network over time, which models the temporal dependency of the individuals’ interaction. Moreover, a change detection approach for such networks is developed, which is capable of detecting changes in the temporal dependency structure of the networks. The proposed approach ignores the weights for the edges and therefore, a part of the information associated with the social network will be lost. To rectify this, in the second section, the communications among actors are modeled as a matrix of Poisson variables, and a monitoring approach based on the eigenvalues of a modified adjacency matrix is proposed to monitor a matrix of Poisson variables. In the final section, to devise a scheme for monitoring a wide variety of social networks, the assumption related to the distribution of the communication counts in a social network is relaxed, and a nonparametric approach is proposed to detect changes in the multivariate distribution of the eigenvalues associated with its adjacency matrices in course of time in social networks. In addition, employing a similar hypothesis, the locations of the possible change-points are estimated. All proposed approaches are applied to both real and simulated networks. The performance of the proposed approaches also compared to those of the available approaches in the literature. Results indicate that the proposed approaches can improve the detection power by at least 15% based on the type of change and its magnitude

پايش شبكه هاي اجتماعي , مدل گراف تصادفي , آزمون ناپارامتري , برآورد نقطه تغيير

Social Network Monitoring , Random Graph Model , Nonparametric Hypothesis , Change-point Estimation