تغییرات پیدا کردن افراد موثر در شبکه اجتماعی

#چکیده در دنیای وب و به خصوص شبکه های اجتمایی ،خبر ها نقش مهمی را بین افراد دارا هستند و می توانند گروهی را تحت تاثیر قرار دهند و در این بین دسته ای از افراد هستند که بین اعضا از اعتبار بالایی برخوردار هستند و پیروان آنها نیز او را تایید میکنند و هر خبر یا رویدادی که او به اشتراک بگذارد، آنها نیز آن را به اشتراک میگذارند و به همین ترتیب خبر در بیشتر شبکه های اجتمایی گسترش میابد. حال با این تفاسیر محققان تصمیم گرفته اند که با بررسی این نوع شبکه های اجتماعی، روابط حاکم بر آنها را دریابند تا بتوانند مدلی ارائه دهند و از روی آن به شناختن و بررسی رفتار های افراد دست یابند. در این پروژه قرار است جریان هایی که این افراد ایجاد میکنند را تشخیص و منشع آنها را نیز پیدا نمود. #مقدمه امروزه رشد سریع شبکه ای اجتماعی باعث شده افراد در زندگی شخصی خود زمان بیشتر را در این شبکه ها بگذرانند و به همین علت این شبکه معیاری برای مطالعه رفتار و انگیزهی افراد در چرایی استفاده از شبکه های اجتمایی قرار گرفته است. همچنین مطالعات بر روی این شبکه ها نشان داده است که خبر یا هر منبعی که باعث خوشی و شادی افراد میشود (که خود یکی از فاکتور های تاثیرگذار است) از اهمیت بالای برخوردار است[1]. #انگیزه برای داده کاوی در رسانه های اجتماعی اطلاعات در دسترس از طریق رسانه های اجتماعی می تواند به ما بینش شبکه های اجتماعی و جوامعی که قبلا در هر دو فیلد مقیاس و انداره امکان پذیر نبوده را بررسی کنیم. این رسانه های دیجیتال می تواند از مرزهای دنیای فیزیکی به مطالعه روابط انسانی [2] و اندازه گیره محبوبیت اجتماعی و سیاسی افراد در یک منطقه بدون برری صریح و روشن برسانند[3، 4، 5]. رسانه های اجتماعی بزرگی مانند فیس بوک و توییتر منبع ایده آل برای مطالعه مکانیزم ها و روندهای تاثیر گذاری است. با این حال، این کاری بسیار دشوار است. برای به دست آوردن اطلاعات مفید از داده های رسانه های اجتماعی بدون استفاده از فن آوری های داده کاوی کاری بسیار سخت و طاقت فرسا است. این اطلاعات به ما برای درست کردن مدلی از رفتار های مردم کمک کند. و بر اساس این مدل میتواند افراد را بر اساس ویژگی هایشان طبقه بندی کرد و ویژگی های روانشناسی افراد را از روی رفتار هایی که از خود نشان میدهند دریافت نمود و همچنین در جوامعی که در حال پیشرفت میباشند این ویژگی ها به دولت کمک میکنند تا بداند افراد جامعه چه مشکلاتی (در صورت وجود مشکل) یا چه نظراتی در مورد خود دارند و یا چه چیز هایی موجب خوش حالی افراد در مناطق مختلف جغرافیایی میشود. حال برای فهم بیشتر پروژه بهتر است با مفاهیم زیر آشنا شویم: **فرد تاثیرگذار** تعریفی که از فرد تاثیرگذار توسط یک جامعه از محققان درگیر در پروژه IARPA جمع بندی شده است شامل ویژگی های زیر است**[6]**: 1. دارای اعتبار در گروه. 2. تلاش برای متقاعد کردن دیگران حتی اگر دیگران با حرف او مخالف باشند. 3. معرفی موضوعات یا ایده هایی که دیگران آنهارا انتخاب و یا پشتیبانی میکنند. دارای اعتبار بودن به معنی این است که ایده و نظر های فرد تاثیرگذار توسط افراد شناخته شده و مشهور به رسمیت شناخته میشود. ممکن است در ابتدا به نظریات یا ایده های خود پافشاری نماید ولی سرانجام بتواند افکار خود را در طی دراز مدت به پیروانش اثبات نماید. این فرد لازم نیست در بحث و یا گروهی که در آن فعالیت می کنند فعال باشند تا بتوانند حمایت و پشتیبانی آنها را دریافت کنند، او حرف خود را از طریق فراهم آوری جواب های قابل قبول، آوردن بینش یا ایده ای جدید و یا با پیدا کردن موارد خاص که باعث رد یا تایید مسئله میشود نظریات دیگران به نظر خود نزدیک کند. #مجموعه دادگان طبق دیتاستی که در سایت کگل موجود است و از توییتر گرفته شده، باید الگوریتم خودآموزی پیاده سازی شود که بر اساس مقادیر و جواب داده شده در دیتاست train بتواند بین هر دو فردی که بعد از مرحله ی آموختن به برنامه داده میشود قضاوت کرده و فردی که تاثیر گذاری اش بیشتر است را اعلام کند. در واقع برنامه باید توانایی بدست آوردن درصد تاثیرگذاری هر فرد را داشته باشد و بین این دو عدد عمل قضاوت را انجام دهد. [لینک ](https://www.kaggle.com/c/predict-who-is-more-influential-in-a-social-network) دانلود دیتاست. این داده ها توسط Peerindex تهیه شده و با همکاری شرکت ماکروسافت مسابقه ای به نام influence in social networks با هدف قضاوت روی رفتار افراد در شبکه های اجتماعی و پیدا کردن موثر ترین فرد در این شبکه ها در تاریخ 13 آپریل 2013 به مدت یک روز برگذار شد. در این مجموعه دادگان، داده ها به صورت جفت جفت قرار دارد و در هر جفت با 11 المان از قبل محاسبه شده و مثبت،براساس فعالیت های آنها در توییتر (مثل تعداد پیروان، تعداد پست ها و ...) فراهم شده است. در هر جفت میزان تاثیرگذاری A و B با یک متغییر دودویی مشخص میشود. 1 مشخص کننده ی این است که A از B تاثیرگذارتر است و 0 نشان دهنده ی تاثیرگذاری بیشتر B نسبت به A است. همان طور که گفته شد هدف این کار پیاده سازی یک نرم افراز خودآموز ماشین است که سعی میکند این رفتار ها شناسایی و پیش بینی کند و استفاده از آن در موارد دیگر جایز نیست. پارامتر های موجود و توضیحات آن در دیتاست: 1. follower_count مشخص کننده ی تعداد افراد پیروی یک فرد را در شبکه اجتماعی است. 2. following_count مشخص کننده ی تعداد افرادی است که فرد آنها را در شبکه اجتماعی دنبال میکند است. 3. listed_count 4. mentions_received مشخص کننده ی تعداد پست هایی است که فرد در آنها ذکر شده است. 5. retweets_received مشخص کننده ی تعداد پست های به اشتراک گذاشته شده از پست های یک فرد توسط پیروان او است. 6. mentions_sent مشخص کننده ی تعداد افرادی است که فرد آنها را در مجموعه پست های خود ذکر یا به آنها اشاره کرده است. 7. retweets_sent مشخص کننده ی تعداد پست های به اشتراک گذاشته شده توسط فرد از مجموعه پست ها یا اخبار پیروان خود است. 8. posts مشخص کننده ی تعداد پست هایی است که فرد از آغاز عضویت خود در شبکه اجتماعی ارسال کرده است. 9. network_feature_1 10. network_feature_2 11. network_feature_3 لینک [گیت هاب](https://github.com/hoomanbehnejad/AI_social_network/tree/master) پروژه. #نحوه پیاده سازی 2. following_count 3. listed_count * 4. mentions_received 5. retweets_received 6. mentions_sent 7. retweets_sent 8. posts 9. network_feature_1 * 10. network_feature_2 * 11. network_feature_3 * توضیحات: مورد اول: مشخص کننده ی تعداد افراد پیروی یک فرد را در شبکه اجتماعی است. مورد دوم:مشخص کننده ی تعداد افرادی است که فرد آنها را در شبکه اجتماعی دنبال میکند است. مورد چهارم:مشخص کننده ی تعداد پست هایی است که فرد در آنها ذکر شده است. مورد پنجم:مشخص کننده ی تعداد پست های به اشتراک گذاشته شده از پست های یک فرد توسط پیروان او است. مورد ششم:مشخص کننده ی تعداد افرادی است که فرد آنها را در مجموعه پست های خود ذکر یا به آنها اشاره کرده است. مورد هفتم:مشخص کننده ی تعداد پست های به اشتراک گذاشته شده توسط فرد از مجموعه پست ها یا اخبار پیروان خود است. مورد هشتم:مشخص کننده ی تعداد پست هایی است که فرد از آغاز عضویت خود در شبکه اجتماعی ارسال کرده است. لازم به ذکر است هیچ توضیحی درمورد عناصر ستاره داد بالا در سایت کگل (منبع مجموعه دادگان) موجود نمی باشد. لینک [گیت هاب](https://github.com/hoomanbehnejad/AI_social_network/tree/master) پروژه. #روش‌های حل مسئله برای حل این نوع مسائل میتوان از روش های زیر بهره گرفت. همچنین میتوان تلفیقی از این روش ها را به عنوان روش حل درنظر گرفت زیرا در برخی روش ها ویژگی هایی موجود است که در بقیه نیست و با ترکیب آنها میتوان مسئله را دقیق تر حل نمود. برای پیاده سازی این برنامه با زبان پایتون میتوان از کتاب خانه های آماده ای نظیر numpy که برای محاسبات علمی به کارمیرود، sklearn که برای خودآموزی ماشین در زبان پایتون است استفاده نمود. **روش اول: مدل خطی** در ابتدا باید یک رفتار خطی از این پارامتر ها پیدا کنیم یعنی ساختن مدلی شبیه $ ax + by + cz + ... = 0 $ یا $ {\sum^{m}_{i=1}(a_i x_i) }= 0 $ که در اینجا میتوان بازه های $a_i$ را با حل دستگاه معدالات خطی پیدا نمود. **روش دوم: اف اف تی یا Fast Fourier transform** در این روش با فرض اینکه ما توابعی داریم کاملا مستقل خطی هستند و با ضرب آنها در هم به یک معادله شبیه $$U(x, y, t, ...) = P(x) F(y) M(t) ... = 0$$ به دست می آید. حال تنها کاری که باید انجام داد بدست آوردن توابع است که می توان آنهارا با روش اف اف تی و استفاده از سری فوریه محاسبه نمود. خوبی روش فوریه این است که میتوان این توابع را به صورت سینوسی و کسینوسی نوشت و با یک سیکما محاسبه نمود و همچنین در مواقعی که صورت صریح توابع موجود نباشد سری فوریه میتواند آنها را به صورت توابع پایه بیان کند، هر یک از این توابع به صورت زیر می باشد: $$F(x) = \frac{a_0}{2} + {\sum_{i=1}^{\infty}(a_i \cos(\frac{n\pi}{l}x) + b_i \sin(\frac{n\pi}{l}x))}$$ **روش سوم: مدل چند جمله ای** در این روش در ابتدا فرض میشود که یک چند جمله ای از درجه ی n داریم، که n به تعداد نقاط (پارامتر های) ورودی برنامه است و قرار است با این تعداد نقطه منحنی رسم شود که از تمام این نقاط بگذرد در نتیجه فرمولی که بدست می آید را میتوان به عنوان فرمول کلی درنظر گرفت و با استفاده از روش های مختلف برون یابی و درون یابی نقاط دیگر را پیش بینی نمود. روش های درون یابی : روش اول - لاگرانژ: در این روش برای پیدا کردن تابع مورد نظر طبق زیر عمل میکنیم [7]: $$ (x_0, y_0), (x_1, y_1), ... ,(x_n, y_n)$$ $$ L(x) = {\sum_{j = 0}^{k}(y_j l_j(x))}$$ $$l_j(x) = \prod_{0\leq m \leq k , m \not= k } (\frac{x - x_m}{x_j - x_m})$$ ~~روش دوم~~ **روش چهارم** - برازش منحنی: در این روش سعی میشود یک چند جنله ای مرتبه n حدس زد که $$\sum_{i = 0}^{N} (y_i - P(x_i))^{2}$$ کمترین مقدار شود. برای این منظور از روش ماتریس کمترین مربعات استفاده میشود [8]. بعد از بدست آوردن ضریب ها میتوان با استفاده از معادله و پارامتر های ورودی میزان تاثیر گذاری را پیدا نمود. #نحوه ارزیابی برنامه همان طور که گفته شد برنامه میزان تاثیرگذاری افراد را با مقادیری بین صفر و یک مشخص میکند درنتیجه بعد از اینکه هر یک از رکورد ها خوانده شد و درصد تاثیرگذاری محاسبه شد آن را با جواب مقایسه میشود و اگر درست بود یک امتیاز مثبت تلقی شده و بالعکس. این امتیاز ها به روند پیش بینی درصد تاثیرگذاری برنامه تاثیر گذاشته و باعث بهبود آن میشود. یعنی ماشین از مجموع امتیاز های خود و مقدار متغییر های فعلی و قبلی خود بعد از هر اجرا روی ضرایب و متغییر های فرمول ارزیابی تجدید نظر انجام میدهد. بعد از اتمام مرحله ی آموختن برنامه را با دیتاست از پیش تعیین شده اجرا کرده و میزان اختلاف جواب برنامه و جواب های پیش فرض مقایسه میکنیم. **راه های پیدا کردن افراد تاثیرگذار** در آینده تکمیل میشود **کار های مرتبط** در آینده تکمیل میشود #آزمایش و نتایج **نتایج آزمایش اولیه** در پیاده سازی اولیه که از روش اول (مدل خطی یا linear) بهره گرفته شده است و با استفاده از کتاب خانه numpy و sklearn سعی شده با پارامتر های مسئله مدل خطی ای را بدست آورد که با آن داده های تست مورد آزمایش قرار داد و میزان تاثیرگذاری هر فرد محاسبه نمود. وزن این مدل خطی 0.8946 است یعنی 89.46% داده های درون مجموعه دادگان با خروجی برنامه با تقریب 0.0000001 واحد، برابر است. وزن برابر تعداد جواب درست به تعداد جواب اصلی است. کار های مرتبط** مقاله ای با نام [9]Extracting Influential Nodes on a Social Network for Information Diffusion که این مسئله را از دیدگاه دیگری بررسی کرده است. سعی شده که شبکه را به صورت یک گراف در نظر گرفت و وزن های هر یال را با درجه ی تاثیر گذاری مشخص نمود. در این مقاله روش های حریصانه (Greedy)، درجه ی نفوذ (marginal degree) بررسی شده و نتایج هر کدام آمده است و طبق فرمول ها و نمودار های بدست آمده، نشان داده است که اگر دیدگاه ما به صورت گراف باشد به نتایج بهتری دست خواهیم یافت و همچنین راه برای بیرون کشیدن اطلاعات هموار است. #آزمایش و نتایج **نتایج آزمایش اولیه** در پیاده سازی اولیه که از روش اول (مدل خطی یا linear) بهره گرفته شده است و با استفاده از کتاب خانه numpy و sklearn سعی شده با پارامتر های مسئله مدل خطی ای را بدست آورد که با آن داده های تست مورد آزمایش قرار داد و میزان تاثیرگذاری هر فرد محاسبه نمود. وزن این مدل خطی 0.8946 است یعنی 89.46% داده های درون مجموعه دادگان با خروجی برنامه با تقریب 0.0000001 واحد، برابر است. وزن برابر تعداد جواب درست به تعداد جواب اصلی است. در پیاده سازی ثانویه که از روش کمترین مربعات بهره گرفته شده است و همچنان از کتاب خانه ی numpy و sklearn استفاده شده است، پارامتر های این مسئله را از نظر داشتن داشتن روابط توانی بررسی شده. این روش نسبت به روش قبل کند تر عمل میکند زیرا وقت بسیاری را صرف ضرب کردن ماتریس های بزرگ میکند ولی مزیت آن نسبت به روش قبل این است که جواب های بدست آمده به مراتب دقیق تر شده و وزن بیشتری را به خود اختصاص میدهند. این مدل با داشتن 92.301% از مدل قبلی ارزش بیشتری دارد ولی دارای نسبت زمانی 0.58 است که تقریبا نصف سرعت قبلی را دارد. #منابع [1]. Kuan-Yu Lin, Hsi-Peng Lu National Taiwan University of Science and Technology, No. 43 Keelung Road, Sec. 4, Taipei 106, Taiwan, ROC [2]. H. Lauw, J. C. Shafer, R. Agrawal, and A. Ntoulas. Homophily in the digital world: A livejournal case study. _Internet Computing, IEEE_, 14(2):15–23, march-april 2010 [3]. S. Kumar, N. Agarwal, M. Lim, and H. Liu. Mapping socio-cultural dynamics in indonesian blogosphere. In _Proceedings of the Third International_ _Conference on Computational Cultural Dynamics (ICCCD 2009)_,2009. [4]. J. Ritterman, M. Osborne, and E. Klein. Using prediction markets and twitter to predict swine 􀃀u pandemic. In F. M. Carrero, J. M. Gomez, B. Monsalve, P. Puertas, and J. C. a. Cortizo, editors, _Proceedings of the_ _1st International Workshop on Mining Social Media_, pages 9–17, 2009. [5]. B. Ulicny, M. Kokar, and C. Matheus. Metrics for monitoring a socialpolitical blogosphere: A malaysian case study. _Internet Computing,_ _IEEE_, 14(2):34 –44, march-april 2010. [6]. Proceedings of the 2012 Workshop on Language in Social Media (LSM 2012), pages 37–45, [7]. [Lagrange polynomial](http://en.wikipedia.org/wiki/Lagrange_polynomial) as visited on ~~may 16th 2015. [8]. [# Minimum mean square error](http://en.wikipedia.org/wiki/Minimum_mean_square_error) as visited on 16th may 2015~~16th may 2015. [8]. [Minimum mean square error](http://en.wikipedia.org/wiki/Minimum_mean_square_error) as visited on 16th may 2015. [9]. Extracting Influential Nodes on a Social Network for Information Diffusion, Masahiro Kimura, Kazumi Saito, Ryohei Nakano, and Hiroshi Motoda, july 2010.