دانشکده برق و کامپيوتر
پايان‌نامه كارشناسي ارشد در رشته هوش مصنوعي
شناسايي تشکل‌هاي پنهان بر اساس لينک و محتوا
به کوشش
فرحناز حاجي پور
استاد راهنما:
دکتر ستار هاشمي
31 شهريور ماه ???3
به نام خداوند جان و خرد
به نام خدا
اظهارنامه
اينجانب فرحناز حاجي پور(9133047) دانشجوي رشتهي مهندسي کامپيوتر گرايش هوش مصنوعي دانشکدهي مهندسي برق و کامپيوتر دانشگاه شيراز اظهار مي کنم که اين پايان نامه حاصل پژوهش خودم بوده و در جاهايي که از منابع ديگران استفاده کرده ام، نشاني دقيق و مشخصات کامل آن را نوشته ام. همچنين اظهار مي کنم که تحقيق و موضوع پايان‌نامه‌ام تکراري نيست و تعهد مي نمايم که بدون مجوز دانشگاه دستاوردهاي آن را منتشر ننموده و يا در اختيار غير قرار ندهم. کليه حقوق اين اثر مطابق با آيين نامه مالکيت فکري و معنوي متعلق به دانشگاه شيراز است.
نام و نام خانوادگي: فرحناز حاجي پور
تاريخ و امضاء31 /06/93
به نام خدا
شناسايي تشکل‌هاي پنهان بر اساس لينک و محتوا
به وسيلهي :
فرحناز حاجي پور
پايان نامه
ارائه شده به تحصيلات تکميلي دانشگاه به عنوان بخشي
از فعاليتهاي تحصيلي لازم براي اخذ درجه کارشناسي ارشد
در رشته‌ي:
مهندسي کامپيوتر- هوش مصنوعي
از دانشگاه شيراز
شيراز
جمهوري اسلامي ايران
ارزيابي شده توسط کميته پاياننامه با درجه : عالي
دکتر ستار هاشمي استاديار بخش کامپيوتر (رئيس کميته) ………………………….
دکتر علي حمزه استاديار بخش کامپيوتر………………………………………………………….
دکتر اقبال منصوري استاديار بخش کامپيوتر………………………………………………….
شهريور ماه 1393
تقديم به آنان که به من آموختند و تقديم به خانواده‌ام که با شکيبايي و مهرباني در کنارم بودند…
سپاسگزاري
اکنون که اين پايان‌نامه به پايان رسيده است بر خود لازم مي‌دانم تا از زحمات بي‌دريغ استاد بزرگوارم جناب آقاي دکتر هاشمي که از آغاز تا پايان کار با راهنمايي‌هاي ارزشمند خود زمينه ساز پيشرفت پايان‌نامه شدند و در اين راه زحمات فراواني را بر دوش گرفتند، نهايت سپاس و قدرداني را داشته باشم.
همچنين از استاد بزرگوار، جناب آقاي دکتر حمزه که به عنوان استاد مشاور در اين پژوهش بنده را همراهي کردند سپاسگزارم.
چکيده
شناسايي تشکل‌هاي پنهان بر اساس لينک و محتوا
به کوشش
فرحناز حاجي پور
امروزه شبکههاي اجتماعي نظير فيسبوک از محبوبيت زيادي برخوردار شده اند، چرا که به مردم سرتاسر جهان اين اجازه را ميدهد که بدون تماس فيزيکي، با دوستان خود ارتباط برقرار کرده، براي آنها پيغام گذاشته و نظرات خود را در مورد موضوعات گوناگون بيان کنند. شناسايي تشکل ها در شبکه هاي اجتماعي کاربرد بسيار زيادي در زمينه هاي مختلف دارد، بنابراين اين موضوع يک زمينهي تحقيقاتي بسيار جالب در ميان محققان بسياري از رشته ها است. مطالعات پيشين تنها از اطلاعات ساختاري و لينکهاي موجود در شبکه استفاده ميکردند و اطلاعات مفيد ديگري که در شبکه وجود داشتند مورد غفلت واقع ميشدند. در حالي که در بسياري از شبکه هاي اجتماعي، دادههاي بسيار مفيدي وجود دارد که توسط کاربران توليد ميشوند، نظير محتواي متن هاي توليد شده توسط هر کاربر. با قرار دادن اين اطلاعات در کنار ساختار لينک شبکه ميتوان تعاملات و ارتباطات بين کاربران را تفسير کرد. در اين مطالعه با استفاده از اطلاعات فوق، نشان داده ميشود کاربراني که لينک هاي نزديکي به هم دارند در يک حوزه کاري شبيه به هم قرار ميگيرند. بهطور خاصتر،در اين پژوهش مدلي براي کشف تشکل ها ارائه ميگردد که در ابتدا سعي ميکند با استفاده از يک راهکار بيزي تشکل ها را بر اساس ساختار لينک شبکه شناسايي کند. سپس با استفاده از ابزار هاي پيمايش متنف در صورتي که متن هاي منتسب به يک کاربر داراي شباهتهاي زيادي با عناوين اسناد منتسب به يک تشکل داشته باشد، آن کاربر به تشکل جديد منتقل ميشود. از اين رو، افرادي که در يک تشکل مشترک هستند در يک حوزهي کاري شبيه به هم نيز قرار دارند. نتايج حکايت از توانايي روش پيشنهادي در کشف تشکلهايي را دارد که به لحاظ معنايي کاملا معني دار هستند.
واژگان کليدي: شبکههاي اجتماعي، تشکل، شناسايي تشکل ها، پيمايش متن
فهرست مطالب
عنوان صفحه
فصل 1- مقدمه7
1-1- شبکه هاي اجتماعي7
1-2- تقسيمبندي شبکههاي اجتماعي9
1-3- اهميت شبکههاي اجتماعي10
1-4- تحليل شبکههاي اجتماعي11
1-5- شبکهها و ويژگي آنها11
1-6- تشکلها در شبکههاي اجتماعي13
1-7- اهميت شناسايي تشکلها16
1-8- انگيزه از انجام اين پايان نامه17
1-9- نگاه کلي به فصول رساله19
فصل 2- فصل دوم: مروري بر کارهاي انجام شده21
2-1- مقدمه21
2-2- روشهاي ارائه شده22
2-3- روشهاي مبتني بر لينک22
2-3-1- بهينه کردن يک هدف سراسري22
2-3-2- بدون بهينه سازي هيچ معياري27
2-3-3- روشهاي مبتني بر مدل27
2-4- روشهي مبتني بر محتوا29
2-4-1- روش CUT29
2-4-2- روش LTCA30
فصل 3- ارائه راه حل و روشهاي پيشنهادي32
3-1- مقدمه32
3-2- روش SBM34
3-3- روش LDA37
3-4- روش پيشنهادي40
3-4-1- روش CDBLC41
3-5- جمعبندي51
فصل 4- نتايج53
4-1- مقدمه53
4-2- مجموعه دادهها54
4-2-1- مجموعه دادهي Cora54
4-2-2- مجموعه دادهي Twitter55
4-3- معيارهاي ارزيابي56
4-3-1- معيار Modularity57
4-3-2- معيار Normalized Mutual Information58
4-3-3- معيار Perplexity59
4-4- نتايج و تحليلها60
4-4-1- مجموعه دادهي Cora61
فصل 5- بحث و نتيجه‌گيري67
5-1- نتيجه گيري67
5-2- پيشنهادات براي کارهاي آتي71
فهرست منابع72
فهرست شکل‌ها
عنوان صفحه
شکل 1-1- تشکلها.14
شکل2-1- افراز گراف.25
شکل 2-2- الف) خوشه‌بندي سلسله مراتبي. ب) خوشه‌بندي توده‌اي26
شکل 2-3- نمايش گرافيکي مدل GSB.30
شکل 2-4- نمايش گرافيکي روش CUT.31
شکل 3-1- نمايش گرافيکي روش مدل بلوک تصادفي (SBM).37
شکل 3-2- نمايش گرافيکي روش LDA.39
شکل3-3- روند کشف تشکلهاي پنهان در CDBLC43
شکل 3-4- گراف مبتني بر لينک براي شبکه مثال.43
شکل 3-5- اعمال روش SBM بر روي گراف شبکه.44
شکل 3-6- انتساب اسناد به تشکلها.45
شکل 3-7- اعمال روش LDA بر روي اسناد درون هر تشکل.45
شکل 3-8- محاسبه شباهت محتواي اسناد در ديگر تشکلها با عناوين يک تشکل به خصوص.46
شکل 3-9- همگرايي الگوريتم CDBLC.47
شکل 3-10- تمايش گرافيکي قدم دوم از الگوريتم CDBLC .48
شکل 3-11- فلوچارت الگوريتم CDBLC51
62
شکل 4-1- کارايي الگوريتم با توجه به معيار MI بر روي مجموعه دادهي Cora.62
شکل 4-2- Perplexity تمام تشکلها در تمام مراحل بر روي مجموعه داده Cora.63
شکل 4-3- خروجي Perplexity براي هر تشکل در مراحل مختلف بر روي مجموعه داده Cora .64
شکل 4-4- نمودار مقايسه Perplexity روش LDA و CDBLC براي T=50 و K=5.65
شکل 4-5- نمودار مقايسه Perplexity روش LDA و CDBLC براي T=30 و K=10.65
شکل 4-5- نمودار مقايسه Perplexity روش LDA و CDBLC براي T=100 و K=2066
فهرست جدول‌ها
عنوان صفحه
جدول 3-1 علائم و تعاريف بکار رفته33
فصل نخست:
مقدمه
مقدمه
شبکه هاي اجتماعي
تعامل انسان با کامپيوتر1 از زمان ايجاد اولين کامپيوترها همواره مورد توجه بوده است و شامل مطالعه، برنامهريزي و طراحي رابطه بين کاربران و رايانهها است. معمولا از HCI به عنوان نقطه تقاطع علوم کامپيوتر، علوم رفتاري2، علم طراحي و چند زمينه ديگر ياد ميشود. اين اصطلاح براي اولين بار توسط کارد و همکارانش در کتاب “روانشناسي تعامل انسان با کامپيوتر” مطرح شده است و دلالت ضمني بر اين مطلب دارد که رايانه داراي کاربردهاي بيشماري است که بدون مرز بين آن و کاربر اعمال ميشود[1].
متخصصان اين حوزه در ابتدا به دنبال راهکاري براي توليد سخت افزارهايي با ارگونومي مناسب بودند. طي دههي 1980 تمرکز اصلي به توليد نرم افزار هاي کاربر پسند معطوف شد اما طولي نکشيد که در دههي 1990 ديدگاه جديدي مطرح شد که در آن، به رايانه به عنوان ابزاري براي ايجاد تعاملات انساني نگاه ميشد. با توجه به اين رويکرد، شبکههاي اجتماعي اينترنتي عامل ايجاد تعامل ميان انسانها در فضاي مجازي گشتند و اهميت به سزايي پيدا کردند[2].
امروزه، با توجه به رشد فراگير اينترنت و فناوريهاي ارتباطي و اطلاعاتي، شاهد شکل گيري يک فضاي مجازي در کنار جهان واقعي هستيم که الگوهاي سنتي را دستخوش تغيير نموده است. اين فضا داراي ويژگيهايي چون فرازمان بودن، بيمکاني، عدم محدوديت به قوانين، روي فضا بودن، آزادي از هويت بدني و جنسي و برخورداري از فضاهاي فرهنگي، اقتصادي، سياسي است. شبکههاي اجتماعي مجازي، امروزه نقش بسيار مهمي در خلق اين فضاي مجازي دارند. اين فضاها در کنار ويژگيهاي مثبت، آسيبهاي رواني و سياسي بسيار گستردهاي را ميتوانند براي يک جامعه به همراه بياورند. همچنين عدهاي از محققان معتقند شبکههاي اجتماعي باعث افزايش معاشرت پذيري ميشود در حالي که عدهاي مقابل اين تعريف قرار دارند و معتقدند شبکه اجتماعي فعلي باعث کاهش ارتباط با خانواده ميشود[3].
بنابر تعريف ارائه شده در دانشنامه آزاد ويکي پديا، شبکه هاي اجتماعي3 ساختار هاي اجتماعي هستند که از بازيگراني تشکيل شده اند که به وسيلهي نوع خاصي از وابستگي مانند روابط دوستي،خويشاوندي، تجاري، الهامات، ايدهها، لينکهاي وب، سرايت بيماريها(اپيدمولوژي)، مسيرهي هواپيمايي يا علايق مشترک با يکديگر در ارتباط اند. به عبارت ديگر شبکه هاي اجتماعي مجموعه اي از بازيگران هستند که به نحوي با يکديگر در ارتباط هستند. در سال هاي اخير گسترش استفاده از رسانههاي ديجيتال براي برقراري ارتباط بين افراد، مفهوم شبکههاي اجتماعي به دنياي کامپيوتر راه يافته است و با توجه به زياد بودن تعداد کاربران در اين شبکهها، تحليل آنها به يکي از موضوعات مورد علاقه در اکثر حوزهها تبديل شده است.
به طور معمول شبکههاي اجتماعي را ميتوان در قالب گراف4 نمايش داد که در اين گرافها، گره5 ها معادل کاربران شبکه اجتماعي بوده و يال6هاي گراف نشان دهندهي ارتباط بين بازيگران ميباشند. با توجه به ساختار شبکه اجتماعي و يک طرفه يا دو طرفه بودن ارتباط گراف متناظر ميتواند جهت دار7 يا بدون جهت8 باشد. همچنين در صورتي که وزن ارتباط بين افراد در شبکههاي اجتماعي يکسان نباشد گراف متناظر با شبکه يک گراف وزندار9 خواهد بود که در آن وزن هر يال متناظر با وزن ارتباط ميباشد [4].
تقسيمبندي شبکههاي اجتماعي
شبکههاي اجتماعي به دو دستهي شبکههاي مجازي و شبکههاي غير مجازي تقسيم ميشوند. شبکههاي غير مجازي توسط مجموعهاي از کاربران بههم پيوسته در محيطهاي اجتماعي عمل ميکنند. شبکه هاي اجتماعي مجازي مجموعهاي از وب سايت10ها هستند که امکان ارتباط را مستقل از زمان و مکان، براي کاربران خود فراهم ميکنند. با استفاده از اين وب سايت ها کاربران با استفاده از يک موتور جستوجو گر و افزودن امکانات جانبي از قبيل انتقال صدا و تصوبر، گفتوگوي دوستانه11، پست الکترونيکي 12 و … ميتوانند علاقهمندي، افکار و فعاليتهاي خود را در يک ثانيه با صدها و حتي هزاران فرد در سراسر جهان به اشتراک بگذارند.
وبلاگ13ها، فيسبوک14، توييتر15 و يوتيوب16 از جمله شبکههاي اجتماعي مجازي هستند[5].
اهميت شبکههاي اجتماعي
امروزه شبکههاي اجتماعي به دلايل بسيار زيادي مورد توجه هستند و اهميت دارند که ما به توضيح دو دليل عمده اکتفا ميکنيم:
رشد روز افزون شبکههاي اجتماعي و تعداد کاربران آنها
اگرچه آمار قابل اعتمادي از تعداد کاربران شبکه هاي اجتماعي برخط17 وجود ندارد [6] اما تحقيقات تجاري نشان ميدهند که جمعيت اعضاي اين شبکهها در سراسر جهان در حال افزايش است. اين امر شرکتهاي بسياري را براي سرمايه گذاري در اين بخش ترغيب کرده است. البته شبکه اجتماعي برخط يوتيوب که امکان بارگذاري و تماشاي ويديوهاي با طول کوتاه را به کاربران خود ميدهد در سايت آماردهي خود18 اعلام کرده است که در حال حاظر در هر ماه بيش از 800 ميليون بازديد کننده يکتا دارد. در هر روز ميليونها عضو به اين شبکه افزوده ميشوند. در سال 2011 اين شبکه در 43 کشور دنيا بومي شده و به 60 زبان مختلف قابل دسترسي است[7].
تغيير ساختار ارتباطات اجتماعي با ورود و گسترش شبکههاي اجتماعي
برخي از آثار اين تغيير عبارتاند از: انتشار بسياري از خبرهاي مهم و پرطرفدار در شبکههاي اجتماعي به جاي استفاده از ابزارهاي سنتي مانند روزنامه، تلويزيون و …
تاثيرات گستردهي شبکههاي اجتماعي در شکلگيري ساختار جديد در روابط بين افراد، بسياري از محققان، جامعه شناسان و حتي سياستمداران را برآن داشته است تا به شبکههاي اجتماعي به عنوان يکي از مهمترين ابزارهاي تاثير بر اذهان عمومي بنگرند[3].
تحليل شبکههاي اجتماعي
با گسترش شبکههاي اجتماعي و اهميت آنها، نياز به تحليل ساختارها و رفتارهاي شبکههاي اجتماعي، به عنوان يکي از نيازمنديهاي شرکتهاي تجاري مبدل گشت. تحليل شبکههاي اجتماعي در بسياري از کاربرد19هااز جمله مديريت شبکه اجتماعي، تحليل گرايش بازار، شناسايي افراد تاثيرگذار و… قابل استفاده است. نيازمنديهاي تجاري باعث شده است در سالهاي اخير در بعد آکادميک توجه زيادي به تحليل شبکههاي اجتماعي گردد. امروزه اين ابزار قدرتمند نه تنها مورد توجه متخصصان فناوري اطلاعات ميباشد، بلکه پژوهشگران ساير رشتههايي چون علوم تربيتي، زيست شناسي، علوم ارتباطات، اقتصاد و… به عنوان يک تکنيک کليدي از تحليل شبکه اجتماعي بهره ميبرند[5].
براي تحليل شبکه از معيارها و نرمافزارهاي متفاوتي استفاده ميشود. نرم افزارهاي تجزيه و تحليل شبکه اجتماعي جهت شناسايي، تجسم و شبيه سازي راًسها و يالها استفاده ميشوند. ابزار تجزيه و تحليل شبکه به محققان اجازه ميدهد تا شبکههايي با اندازههاي مختلف را بررسي کنند. اين نرم افزارها که با فراهم آوردن ابزارهاي مختلف اجازه اعمال رويههاي رياضي و آماري را روي مدل شبکه ميدهند، با نمايشهاي بصري شبکههاي اجتماعي به درک و تحليل نتايج کمک زيادي ميکنند.
شبکهها و ويژگي آنها
شبکههاي اجتماعي20[8]، شبکههاي فني21 (مانند اينترنت[9]) و شبکههاي زيستي (مانند
شبکههاي عصبي22[10]) نمونه هايي از شبکهها هستند. راسها در اين شبکهها، موجوديتها و يالها، ارتباط بين آنها را نشان ميدهند. مثلا در شبکه اينترنت، کامپيوترها يا مسيريابها و در شبکههاي اجتماعي، مردم را با راسها، و ارتباطهاي دادهاي بين کامپيوترها و يا روابط دوستي بين مردم را با يالها نمايش ميدهيم.
شبکهها داراي ويژگيهاي آماري مشترکي هستند. يکي از اين ويژگيها، ويژگي پديده دنياي کوچک23[11] که به 6 درجه جدايي24 [12] نيز معروف است و بيان ميکند که در يک شبکه، فاصله متوسط بين راسها، کوتاه و معمولا تابعي لگاريتمي از تعداد آنهاست. شش درجه جدايي به اين اشاره دارد که اگر فاصله هر فرد را از تمام افرادي که مستقيما ميشناسد يک گام در نظر بگيريم و اين فاصله را براي تمام افرادي که با يک نفر واسط با آن آشنايي دارد دو گام در نظر بگيريم آنگاه ميانگين فاصله هر دو نفر در کره زمين 6 گام است. در سال 2009 سايتي به نام Glacir25 براي بررسي تئوري 6 درجه جدايي ساخته شد که نه تنها فاصله شما را با ديگران مشخص ميکرد بلکه نحوه ارتباط شما با اخبار جهان را هم نمايش ميداد. برنامهاي در فيس بوک به نام Six Degrees توسط بنيان26، تهيه شده است که ميتواند فاصله بين افراد را محاسبه کند. اين برنامه بيش از 5.8 ميليون کاربر دارد. ميانگين فاصله ميان تمام اعضا 5.73 است که ماکزيمم آن 12 مي باشد.
ويژگي ديگر، ويژگي توزيع درجه اريب به راست27 [13] بوده و بيان مي کند که درجه بيشتر راسهاي يک شبکه، کم و تنها تعداد محدودي از آنها درجه بالا دارند و توزيع درجات غالبا با قانون تواني28 ميباشد[14]. ويژگي بعدي، ويژگي خوشهبندي29 يا انتقالپذيري30 شبکه است و بيان ميکند دو راس مجاور با راس سوم، با احتمال زيادي با يکديگر مجاور بوده و با ضريب خوشه بندي مقداردهي ميشود[15].
اما مهمترين ويژگي شبکهها که توجه بيشتري را به خود جلب کرده است، ويژگي ساختار تشکل31 ميباشد [16][17] که طبق تعريف سنتي به معني وجود گروههاي متراکم از راسها و ارتباطات تنک بين اين گروههاست. اين ويژگي در شکل 1-1 نشان داده شده است. (به اين ويژگي، خوشهبندي نيز گفته ميشود، اما براي جلوگيري از تداخل با ويژگي قبل، از اين نام استفاده نميکنيم) اين گروهها، معمولا خوشه32، تشکل33، گروههاي به هم پيوسته 34و يا ماژول35 ناميده ميشوند.
شکل 1-1- تشکلها.
رأسها در بسياري از شبکهها به طور طبيعي در گروهها يا تشکلها قرار مي‌گيرند، مجموعههايي از رأسها (سياه يا سفيد) که يالهاي دروني بسيار دارند اما تعداد يالهاي بين آنها کم است.
تشکلها در شبکههاي اجتماعي
در اغلب شبکه‌هاي اجتماعي مجموعه‌اي از بازيگران وجود دارند که ارتباطات قوي‌تري با يکديگر داشته و موضوعات مورد علاقه آنها نيز مشابه است که در ادبيات شبکه‌هاي اجتماعي به اين مجموعه بازيگران مجمع، انجمن يا تشکل گفته مي‌شود.ساختار تشکل به معني وجود گروههاي فشرده از گرهها و تعاملات پراکنده در اين گروهها است. شناسايي تشکل به روندي گفته ميشود که در طي آن گرهها در خوشههايي گروه بندي ميشوند که تعاملات مرتبط با هم و علاقه منديهايي مشترک دارند[4][18].
امروزه توابع هدف36 مبتني بر لينک بسيار زيادي وجود دارند که سعي ميکنند مجامع و تشکلها ر در گراف شبکه پيدا کنند. اين توابع به گونهاي انتخاب ميشوند که بتوانند تشکلهايي را استخراج کنند که اتصالات دروني آنها بيشتر از اتصالات برونيشان باشد[19]. براي اينکه بتوان بر اساس تعاريف ارائه شده مجامع را استخراج کرد بايد بتوان کيفيت تشکاهاي استخراج شده را بر اساس اين تعاريف تعريف نمود. چند نمونه از معيارهاي سنجش کيفيت تشکل ها عبارت اند از:
•قطر انجمن: يکي از معيارهاي مورد استفاده براي اندازهگيري گراف قطر گراف ميباشد که از آن به عنوان معيار اندازهگيري کيفيت يک تشکل نيز استفاده ميشود. قطر يک تشکل حداکثر طول کوتاهترين مسير بين هر دو گره دلخواه در اين تشکل ميباشد و هر چه قطر يک تشکل کمتر باشد نشان از چگالي بيشتر ارتباطات و قوت آنها بين بازيگران موجود در تشکل ميباشد.
•ضريب خوشهبندي37: اين خصوصيت بيان ميکند که دو گره در شبکه اجتماعي که همسايه يک گره ديگر هستند نسبت به دو گره که به طور تصادفي از کل گره هاي موجود در شبکه اجتماعي انتخاب شوند با احتمال بيشتري با يکديگر در ارتباط هسستند. اين خصوصيت بر اساس ضريب خوشهبندي قابل اندازهگيري ميباشد. فرمول ضريب خوشهبندي که در [20] آمده است، به صورت زير ميباشد:
(1-1)
C=(3*(تعداد مثلثهاي موجود در گراف))/(تعداد گرههاي ه تايي متصل به يکديگر)
ضريب خوشهبندي به طور دقيق احتمال اينکه دو گره به يک گره خود به يکديگر متصل باشند را بيان ميکند و براي يک گراف کامل معادل يک ميباشد.
استقرار درمرکز38: تفاوت بين تعداد پيوندها براي نود تقسيم شده توسط بيشترين مجموع تفاوتها. يعني در يک شبکه هميشه گرههايي وجود دارند که نسبت به ديگر گرهها تعداد پيوندهاي بيشتري دارند. در شبکهاي که دچار عدم تمرکز است تفاوت کمي بين پيوندهاي هر گره وجود دارد.
اما اگر براي شناسايي تشکلها، تنها از ساختار لينک شبکه استفاده شود، استخراج علايق مشترک از تشکلها، امري ناممکن ميشود. بسياري از مطالعات پيشين، از پيوستگي بين روابط و علايق چشمپوشي ميکنند، بنابراين در تشخيص تشکلهاي مناسب دچار مشکل ميشوند. در اين مطالعه، ما با در نظر گرفتن اين موضوع، معتقديم که تعريف تشکل به شدت وابسته به کاربرد آن است. يک تشکل ممکن است به گروهي از افراد اطلاق شود که نسبت به ساير افراد به يکديگر نزديکتر هستند (معيار نزديکي دو فرد مي‌تواند کوتاهترين مسير بين آن دو نفر يا مجموع تمامي مسيرهاي مستقل ما بينشان و يا توابع فاصله ديگري از اين دست مي‌باشد) يا کساني که علايق مشترکي با يکديگر دارند اما ضرورتا به طور مستقيم به هم لينک ندارند، يعني ممکن است يک رأس به صورت مفهومي به يک تشکل مرتبط باشد و محتواي اسناد همراه با اين رأس به محتواي کلي يک تشکل شباهت داشته باشد اما لينک مستقيمي بين آن رأس و اعضاي تشکل وجود نداشته باشد. بنابراين، يک تشکل که از نظر معنا شناسي معنادار است بايد به هر دو تعريف توجه کند و سعي کند هر دو ويژگي را در کنار هم داشته باشد.

اهميت شناسايي تشکلها
تشکل‌ها اطلاعات ارزشمندي در مورد نوع ارتباط بازيگران، نحوه انتقال اطلاعات بين آنها و نحوه‌ توزيع بازيگران در شبکه‌هاي اجتماعي ارائه مي‌کنند و در واقع به عنوان جزء اصلي سازنده اين شبکه‌ها محوب مي‌شوند.
شناسايي تشکل ها در شبکهها از اهميت زيادي برخوردار است، زيرا با توجه به تعداد زياد کاربران و اطلاعات بيشمار بر روي شبکههاي اينترنت، امکان آناليز دادهها و انجام درخواست39ها ميسر نخواهد شد. مثلا تشکلهاي موجود در شبکه وب، با مجموعههاي صفحات وب موجود بر روي موضوعات مرتبط متناظر بوده، تشخيص آنها منجر به يافتن صفحات مشابه و مربوط به هم ميشود. اين موضوع براي بسياري از کاربردها، مثلا موتورهاي جستجو و سيستمهاي پيشنهاددهنده40 متناسب است. همچنين، تشکلهاي موجود در شبکههاي اجتماعي با واحدهاي اجتماعي41 تناظر دارند[21]. از ديگر کاربردهاي شناسايي تشکل، در شبکههاي مبتني بر متن42 مثل 43DBLP يا 44Twitter مطرح ميشود. از يک ديدگاه، در اين شبکه، رأسها با اسناد45 تناظر داشته و دو رأس، در صورتيکه يک نويسنده سند متناظر با آنها را نوشته باشد با يک يال به هم مربوط ميشوند. نتيجه شناسايي تشکلها در اين شبکه، يافتن اسناد با محتواي مشابه است. از طرف ديگر يکي ديگر از مهمترين کاربرد شناسايي تشکل در شبکههايي از اين دست ، مسالهي رفع ابهام در نام نويسندگان46 است. بدين ترتيب که با شناسايي تشکلهاي مربوط به نويسندگاني با نامهاي مشابه، ميتوان دريافت که هر کدام از اين نويسندگان به چه تشکلي تعلق دارند و در نتيجه بين آنها تميز داد.
يکي ديگر از کاربردهاي اصلي شناسايي تشکلها در کسب و کار الکترونيکي است. از جملهي کاربردها در اين حوزه ميتوان به قسمتبندي بازار، بازاريابي ويروسي، پيدا کردن افراد تاثيرگذار و حاميان تشکلهاي اعتماد در وب اشاره کرد. يادگيري مشارکتي از جمله رويکردهاي موفق يادگيري است که طي آن، فراگيران طي تعامل با يکديگر مباحث را فرا ميگيرند. به سبب تاثير مثبت يادگيري اين روش در يادگيري، شيوههاي نوين آموزش الکترونيکي به دنبال تحقق آن در محيط مجازي و به صورت خاص، در شبکههاي اجتماعي ميباشند. از چالشهاي مهم پيش روي يادگيري مشارکتي، چگونگي ايجاد تعامل و نحوهي نظارت معلم بر فراگيران ميباشد. شناسايي تشکلهاي اجتماعي مي تواند در مواجهه با اين چالشها به معلمان ياري رساند.
کاربرد ديگر تشکلها که شناسايي آنها را با اهميت ميکند در جامعهشناسي و روانشناسي است. با استفاده از تشکل ها در اين علوم، جامعه مجازي و رفتار هر فرد در جامعه مجازي به نحو کاراتري بررسي ميشود و با الگو برداري از اين رفتارها، دنياي واقعي بهتر مدل ميشود. از مدل به دست آمده براي اتخاذ تصميمات در بسياري از زمينهها استفاده ميشود.
انگيزه از انجام اين پايان نامه
همانطور که پيشتر نيز بيان شد، تحليل شبکههاي اجتماعي به عنوان يک تکنيک کليدي در جامعهشناسي، انسان شناسي، روانشناسي اجتماعي، بازاريابي و مديريت بازار، مطالعات سازماني، سياست، اقتصاد و… همانند يک موضوع محبوبدر زمينهي تفکر و مطالعه پديدار شده است.
تشکل‌ها به سبب ارائهي اطلاعات مفيدي در مورد نوع ارتباط کاربران حاظر در شبکه، نحوهي توزيع آنها و نحوهي انتقال اطلاعات بين بازيگران در شبکه‌هاي، به عنوان جزء اصلي سازنده اين شبکه‌ها محسوب مي‌شوند. بنابراين شناسايي تشکلها امري بسيار مهم و حياتي است.
روشهاي پيشين براي شناسايي تشکلها فقط از اطلاعات ساختاري و لينکهاي موجود در شبکه استفاده ميکردند اما دادههايي که امروزه در رسانههاي اجتماعي47 يافت ميشوند علاوه بر لينکهاي بين گرهها شامل محتوايي براي توصيف خود گرهها يا ارتباطات بين آنهاست. در سايتهاي اينترنتي شبکههاي اجتماعي، کاربران داراي صفحات پروفايل شخصي48 هستند، نظرات49 خود را در شبکه به اشتراک ميگذارند و مقالات50 را بازيابي و آشکار ميکنند. در سايتهاي بحث در مورد عکسها و فيلمها، مشتريان درمورد عکسها و فيلمها توضيح ميدهند و از متنهاي کوتاه براي برچسب زدن51 به آنها استفاده ميکنند. اما با توجه به حجم بالاي محتواي متني و رشد و توسعه بسيار سريع آنها، مطالعهي همهي اين سندها و استخراج اطلاعات از آنها کار بسيار دشواري است. روشهاي مدل کردن عناوين به ما اين امکان را ميدهد که اين حجم بالا از اطلاعات را بررسي کرده و اطلاعات لازم را از آنها استخراج کنيم.
اهميت شناسايي تشکلها با توجه به تمامي مطالب ذکر شده در بالا و موارد و مشکلات موجود در اکثر روشهاي متداول براي شناسايي تشکلها، ما را بر آن داشت تا در اين پاياننامه، از اطلاعات متني نيز در کنار دادههاي معمول استفاده کنيم بهطوريکه تشکلهاي مناسب تري را کشف کنيم که هم ساختاري را داشته باشد که اعضاي نزديکتر را در يک گروه قرار دهد هم اينکه از نظر معنايي قابل فهمتر و قابل توصيفتر باشند.
نگاه کلي به فصول رساله
اين رساله مشتمل بر پنج فصل ميباشد که در ادامهي مقدمه، در فصل دوم به بررسي و تحليل روشهاي ارائه شده در اين حوزه خواهيم پرداخت. در فصل سوم، روشهاي پيشنهادي با تمامي جزئيات ارائه خواهند شد و در فصل چهارم، نتايج حاصل از اجراي آنها بر روي مجموه داده52هاي معرفي شده به همراه تحليل نتايج آورده شده است. در انتها در فصل پنجم به شرح نتيجهگيري و کارهاي آينده پرداختهايم.
فصل دوم
مروري بر کارهاي پيشين
فصل دوم:
مروري بر کارهاي انجام شده
مقدمه
مطالعه ساختار تشکل در شبکهها تاريخچه‌اي بسيار طولاني داشته و الگوريتمهايي که به اين منظور مطرح‌شده‌اند در دو دسته کلي قرار مي‌گيرند:
دسته اول: الگوريتمهايي که فقط بر اساس ساختار ارتباط 53 بين رأسها عمل مي‌کنند.
دسته دوم: الگوريتمهايي که علاوه بر ساختار ارتباط بين رأسها، از اطلاعات مفهومي گراف شبکه نيز استفاده مي‌کنند.
همانطور که در فصل قبل اشاره شد، تشکل به گروهي از اعضا اطلاق ميشود که از لحاظ لينک، ارتباطات بسيار نزديکي با يکديگر دارند و از نظر محتوا، در يک حوزه مشترک فعاليت ميکنند.
در اين فصل با توجه به تعريف فوق و تعاريف قبلي، به مطالعهي روشهاي ارائه شده در اين حوزه از نقطه نظرات گوناگون خواهيم پرداخت.
روشهاي ارائه شده
همانطور که در بخش 2-1 اشار شد، الگوريتمهاي شناسايي تشکل در دو دسته کلي قرار ميگيرند که دسته اول بر اساس ساختار لينک ميباشد. خود روشهاي تعريف شده در اين حوزه در سه دستهي کلي زير قرار ميگيرند:
روشهايي که به دنبال بهينه کردن54 يک هدف سراسري55 مي‌باشند.
روشهايي که بر اساس بهينه‌سازي هيچ معياري عمل نمي‌کنند.
روشهاي مبتني بر مدل 56.
روشهاي ارائه شده در دسته دوم بهطور پراکنده، سعي در يافتن تشکلها بر اساس محتوا ميکنند.
در ادامه نمونههايي از هر دسته را شرح خواهيم داد.
روشهاي مبتني بر لينک
بهينه کردن يک هدف سراسري
روشهايي که به دنبال بهينه کردن يک هدف سراسري مي‌باشند، مانند بهينه کردن معيارهاي اندازه برش گراف [21] پيمانهاي بودن57 [22] و نوع فازي آن [23]، مابين بودن[24] و هدايت58 [25] و يا بهينه کردن پارامترهاي احتمالات موجود در GMM59 [26]در گروه اول جاي دارند. الگوريتمهاي افراز گراف60 و خوشه‌بندي سلسله مراتبي61 از اين دسته‌اند.
2-3-1-1- افراز گراف در نظريه گراف و علوم کامپيوتر
مسئله افراز گراف[21] شامل تقسيم رأسهاي يک گراف در g گروه با اندازههاي از پيش معلوم است به طوري که تعداد يالهاي بين گروهها که اندازه برش ناميده مي‌شود کمينه شود(شکل 2). اين مسئله در راستاي حل مسائلي همچون محاسبه موازي62مطرح ميشود. در اينجا هدف تخصيص پروسهها به پردازندههاست، به طوري که بار63 بر روي هر پردازنده به طور متعادل توزيع شود و از طرفي ارتباط بين پردازندهها که باعث کاهش سرعت اجرا مي‌شود، کمينه شود. اين مسئله NP-دشوار است و با الگوريتمهاي مکاشفه‌اي64 که بهترين آنها الگوريتم Kernighan-Lin [27] با زمان اجراي O(n3) است، قابل اجرا است.
به طور کلي پيدا کردن راه حل براي مسئله افراز گراف، چندان هم در تحليل شبکهها سودمند نيست، زيرا در شبکهها، بر خلاف مسئله افراز گراف تعداد تشکلها مشخص نيست و لزومي هم بر هم اندازه بودن اين تشکل‌ها وجود ندارد. از طرفي، نيازي به کمينه کردن ارتباط بين تشکل‌ها نيست، چرا که طبق انتظار، ارتباط بين تشکلهاي بزرگ نسبت به ارتباط بين تشکلهاي کوچک، بسيار بيشتر است. بنابراين، مسئله شناسايي تشکلها در شبکهها تفاوت اساسي با مسئله افراز گراف دارد.
امروزه، تا حدي مشکلات اين روش با استفاده از الگوريتمهاي طيفي65 که از بردارهاي ويژه66 ماتريس شبکه استفاده مي کنند حل شده است[28].
شکل2-1- افراز گراف.
خط قرمز نشان‌دهنده حل مسئله است که در آن رأسها به دو گروه با اندازههاي يکسان
تقسيم شده و يالهاي بين دو گروه، کمينه است.
راه حل بهتري که در اين راستا ارائه مي شود، روش هاي خوشه بندي سلسله مراتبي است.
2-3-1-2- خوشه‌بندي سلسله مراتبي
هدف اين روشها شناسايي تقسيم‌بندي طبيعي شبکهها بر اساس معيار شباهت67 بين رأسها يا قدرت68 ارتباطات بين آنهاست. اين روشها در دو دسته کلي توده‌اي69 و تقسيم شونده70 جاي ميگيرند.
روشهاي خوشه‌بندي سلسله مراتبي توده‌اي: در اين روشها، در ابتدا شباهت بين هر زوج رأس بر اساس يک معيار محاسبه‌شده و يالهاي بين آنها به ترتيب از بيش‌ترين ميزان شباهت به کمترين، به شبکه تهي اضافه ميشوند. اين روال مي‌تواند در هر لحظه متوقف شود و اجزاي حاصل، تشکلهاي تشکيل‌شده تا آن لحظه هستند (شکل 3.ب). روشهاي توده‌اي اغلب نمي‌توانند تشکلهاي شبکه را به طور صحيح شناسايي کنند، در نتيجه قابل‌اعتماد نيستند. به علاوه با توجه به اينکه رأسهاي موجود در تشکلها شباهت قوي تري نسبت به ديگر رأسها دارند، در مراحل اوليه به هم متصل شده و رأسهاي مرزي کنار گذاشته ميشوند. بنابراين اين روش، نسبت به روشهاي تقسيم شونده در شناسايي تشکل‌ها ضعيفتر عمل مي‌کنند.
روشهاي خوشه‌بندي سلسله مراتبي تقسيم شونده: اين روشها با يک شبکه غير تهي شروع کرده، يالهاي مربوط به زوج رأسهايي که شباهت کمتري دارند به ترتيب حذف مي‌شوند(شکل 3.الف). در روش ارائه‌شده توسط Grivan و Newmanيالهايي براي حذف انتخاب مي‌شوند که معيار مابين71 بودن بيشتري داشته باشند. از مشکلات اين روش ميتوان به زمان اجراي بالاي اين روش اشاره کرد که O(n3) است[29].
الف) ب)
شکل 2-2- الف) خوشه‌بندي سلسله مراتبي. ب) خوشه‌بندي توده‌اي
دايرههاي پايين تصوير نماينده رأسهاي گراف هستند.
خط نقطه چين در هر سطح، تشکل هاي آن سطح را نشان مي دهد
2-3-1-3- الگوريتم Chen
در [24] معيار جديدي به نام L براي انتخاب راس مناسب جهت اضافه نمودن به گروه، معرفي شده است. اين الگوريتم سعي دارد تا اين معيار را ماکزيمم کند. معيارهايي که تاکنون معرفي شده بودند در راستاي افزايش يالهاي داخلي و کاهش يالهاي خارجي گروه هستند. مهمترين جنبهاي که در اين معيارها فراموش شده است تراکم گروه است. به عبارت ديگر، توجهي به رئوس دورافتاده72 ندارند. رئوس دورافتاده رئوسي هستند که با اضافه شدن به گروه تعداد يالهاي خارجي را افزايش نميدهند، در حالي که عضو گروه نيز نميباشند. به طور مثال، گروهي را با يک ميليون يال داخلي و بدون يال خارجي تصور کنيد که در آن هر راس به يک الي دو را متصل است. با وجود اسن نميتوان ادعا کرد که اين مجموعه يک گروه خوب است. به همين دليل معيار جديدي به نام Lin معرفي شده است که نسان دهندهي ميانگين درجات گروه است.
L_in=((?_(i?C_core)??IK_i)?)/(|S|)
که در آن IKi تعداد يالهاي بين راس i و رئوس گروه S وجود دارد را نشان مي دهد. به طور مشابه، معيار Lext نيز به همين شيوه تعريف ميشود.
L_ext=((?_(j?B)??EK_j)?)/|B|
در اين فرمول EKj تعداد يالهاي بين راس j و رئوس داخل مجموعه N را نشان ميدهد. اين الگوريتم به دنبال افزايش مقدار Lin و کاهش Lext به صورت همزمان است. در همين راستا، معيار L بر اساس دو معيار Lin و Lext به صورت زير تعريف ميشود.
L=L_in/L_ext
حالتهايي که هنگام اضافه شدن راس به گروه رخ ميدهند، در زير دستهبندي شدهاند.
?L’?_in> L_in و ?L’?_ext<L_ext
?L’?_in<L_in و ?L’?_ext<L_ext
?L’?_in> L_in و ?L’?_ext>L_ext
واضح است که در حالت اول راس به گروه افزوده خواهد شد. رئوسي که در حالت دوم صدق ميکنند، در واقع گرههاي دور افتاده هستند. در حالت سوم تصميم گيري کمي مشکل است. زيرا که اين رئوس داراي ارتباطات سنگين با رئوس درون و بيرون از گروه به صورت همرمان هستند. رئوسي با درجه بالا که با رئوس درون يا بيرون گروه ارتباط دارند را در اصطلاح هاب مينامند. در اينجا علاقه به حضور اين رئوس در گروه نداريم. در ابتدا قضاوت براي اينکه راسي، هاب است زود است. به همين دليل در ابتدا اين رئوس را به گروه اضافه ميشوند و در انتها هر يک از رئوس دوباره براي هاب بودن بررسي ميشود.
اين الگوريتم داراي دو فاز اصلي است. در فاز اول که کشف73 نام دارد به دنبال رئوسي با L’ ماکزيمم ميگردد و آنها را به گروه اضافه ميکند. در فاز دوم که فاز تست74 نام دارد هر يک از رئوس اضافه شده را مورد بررسي قرار ميدهد و تنها رئوسي که در شرط اول صدق ميکنند نگه ميدارد و ما بقي را دور ميريزد.
پيچيدگي اين الگوريتم برابر با O(kd|S|) ميباشد. که در آن d ميانگين درجات رئوس و k اندازه مجموعهي D است. اين الگوريتم قابليت اجرا بر روي گرافهاي درختي بسياري هستند را ندارد. زيرا در اين گرافها رئوس با درجه اندک بسيار مشاهده ميشود. همچنين امکان گير کردن در مينيمم (ماکزيمم) محلي وجود دارد.
بدون بهينه سازي هيچ معياري
اين روشها بر اساس بهينه‌سازي هيچ معياري عمل نمي‌کنند و به دنبال وجود زير اجزا 75 با ساختارهاي از پيش تعيين‌شده76 مي‌گردند[29]. نمونهي بارز اين دسته روش Clique [29] ميياشد که در گراف شبکه، براي پيدا کردن ساختارهايي نظير k-clique جستجو ميکنند و بيان ميکنند که تشکلهاي موجود، با اين ساختارها تناظر دارند. در علم کامپيوتر مسئله کليک اشاره به يافتن زيرگرافهاي کامل دارد، يعني مجموعهاي از عناصر که دو به دو بههم متصل هستند.
روشهاي مبتني بر مدل
گروهي از روشهاي مبتني بر مدل 77 نيز در دسته اول جاي دارند. بسياري از اين روشها براي تخمين پارامترهاي مدل از مقادير بسيار نزديک78 به پارامترها استفاده مي‌کنند که اين روشها به دليل وجود نويز79 در دنياي واقعي پايدار و قابل‌اطمينان نيستند، اما در روش DSBM80 [16]براي تخمين پارامترها از رفتار بيزي81 استفاده‌شده که علاوه بر نشان دادن عدم قطعيت82 در مقادير پارامترها نسبت به عوامل خطا ساز نيز پايدارتر است.
نمونهي ديگري از اين روش، مدل GSB (بلوک تصادفي عمومي83) است. اين مدل که نوعي از مدل بلوک تصادفي است، مي تواند احتمال (likelihood) توليد لينک در شبکههاي جهتدار و يا بدون جهت را بر اساس ايدهي استفاده از لينک براي شناسايي جوامع را مدل کند. در اينجا |E| نشان دهندهي تعداد يال جهتدار در شبکه ميباشد. همچنين فرض ميکنيم که يک جفت تشکل نهان84 <g,h> توسط هر لينک <i,j> با احتمال w_gh تشکيل ميشود. گره i با احتمال ?_gi توسط تشکل g و گره j با احتمال ?_hj توسط تشکل h نمونهبرداري ميشوند. در مدل GSB فرض ميشود که احتمال ايجاد يک پيوند بين دو گره مرتبط است با وجود ارتباط بين خود جوامع. با اين فرض، مدلGSB قادر به کشف جوامع به طور عمومي تر ميباشد. همچنين پارامتر اين مدل توسط الگوريتم EM85 بدست ميآيد[30] . نمايش گرافيکي اين مدل در شکل 2-3 آورده شده است.
شکل 2-3- نمايش گرافيکي مدل GSB.
دايرههاي توپر نشان دهندهي مقادير ديده شده و دايرههاي توخالي نشان دهنده مقادير پنهان هستند. خط پر به همراه فلش بين گرههاي i و j نشان دهندهي وجود يک يال جهتدار بين آنها است. خطچينهايي که دو دايره را به هم مرتبط ميکنند، بيان ميکنندکه رابطه بين اين عناصر ديده نشده هستند و بايد توسط مقادير ديده شده ياد گرفته شوند. فلشها نشاندهندهي جهت رابطه هستند.
روشهي مبتني بر محتوا
در اين قسمت به ارائهي دو روش اکتفا ميکنيم.
روش 86CUT
اين روش که از محتواي پستهاي الکترونيکي براي شناسايي تشکلها استفاده مي‌کند، نمونهاي از الگوريتمهاي موجود براي دسته دوم است. در اين روش تشکلها بر اساس ترکيبهاي تصادفي از مدل کاربران که از علايق آنها بهدست ميآيد، مدل ميشوند. اما اين روش از اطلاعات ارتباطات در گراف شبکه استفاده نمي‌کند، بنابراين مدلهايي شبيه CUT براي زماني که اعضاي تشکل فعالانه باهم در ارتباط باشند مناسب هستند و در غير اين صورت جواب قابل قبولي ارائه نمي‌دهند[5]. نمايش گرافيکي اين روش در شکل 2-4 نشان داده شده است.
شکل 2-4- نمايش گرافيکي روش CUT.
روش LTCA87
اين روش نيز مثال ديگري از الگوريتمهاي دسته دوم است. در اين روش فرض مي‌شود افرادي که باهم در يک تشکل قرار مي‌گيرند، به طور نزديکي88 با يکديگر در ارتباط هستند و موضوعهاي پنهان89 مشترکي را به اشتراک ميگذارند[31] بنابراين سعي ميکند تشکلهايي را استخراج کند که افراد در آن موضوعات شبيه به همي را به اشتراک ميگذارند.
فصل سوم
ارائه راه حل و روش هاي پيشنهادي
ارائه راه حل و روشهاي پيشنهادي
مقدمه
روشي که در اينجا ارائه خواهيم داد بر خلاف اغلب روشها که براي تشخيص تشکل ها در شبکه هاي اجتماعي، تنها با استفاده از ساختار90 شبکه، تلاش در بهينه کردن سراسري 91 يک معيار از پيش تعيين شده دارند، اساسا بر مبناي استفاده از اطلاعات مفهومي موجود در شبکههاي اجتماعي در کنار اطلاعات ساختاري است. به طور کلي، در اين روش، در ابتدا بر اساس يک روش مبتني بر مدل و با استفاده از اطلاعات ساختاري يک تخمين اوليه مناسب از تشکل ها به دست ميآيد، سپس بر اساس روش هاي پيمايش متن92 و با استفاده از اطلاعات مفهومي سعي ميشود کاربران به تشکل هايي منتقل شوند که به لحاظ مفهومي با محتواي متن هاي منتسب به آن کاربر، شباهت داشته باشند.
انگيزه اصلي براي ارائه روشي مبتني بر محتوا و لينک



قیمت: تومان


پاسخ دهید