بخشی از مقاله
چکیده
شناسایی گرههای مهم در دادههای گرافی از اهمیت بالایی برخوردار است. ازجمله دادههای گرافی مهم میتوان به شبکههای اجتماعی اشاره کرد که در آن هر گره معرف یک فرد و هر یال معرف ارتباط میان دو فرد است. در این مقاله با ترکیب مفهوم بینظمی - Entropy - در گراف با ویژگیهای ساختاری موجود در شبکههای اجتماعی - نظیر زمان و نوع ارتباط - به معرفی یک روش جدید برای شناسایی گرههای مهم پرداختهایم.
در ادامه، روش خود را روی مجموعه دادهی ایمیلی انرون - Enron - اعمال کردهایم و با کارهای پیشین مقایسه نمودهایم. در مقایسه با کارهای پیشین روش پیشنهادی موفق شد -1 افراد مهمتری را شناسایی کند. -2 مدیرعامل مجموعه را به عنوان رهبر مشخص کند. -3 دو مدیرعامل از چهار مدیرعامل مجموعه را در میان پنج فرد مهم قرار دهد.
-1 مقدمه
به تازگی شناسایی گرههای مهم به زمینه تحقیقاتی مهمی در علم گرافکاوی تبدیل شده است. شناسایی گرههای مهم در زمینههای مختلفی از جمله صنعت، پزشکی، شیمی و ساختارهای دارویی کاربرد دارد. یکی از دادههای گرافی مهم، شبکههای اجتماعی هستند. با فراگیر شدن شبکههای اجتماعی در میان مردم؛ این شبکهها بازنمایی مناسبی از جامعه ارائه میکنند.
با شناسایی افراد تأثیرگذار در جامعه و نحوه تعامل آنها با دیگر افراد، میتوان رفتار عموم مردم را پیشبینی و مدیریت کرد، زیرا دیگر افراد جامعه اغلب از این اشخاص تأثیرگذار، تبعیت می کنند. در گراف شبکههای اجتماعی هر گره یک فرد و هر یال معرف یک نوع ارتباط بین افراد است. در این میان، ایمیلها یکی از بهترین منابع برای تحقیقات در این زمینه هستند. راحتی استفاده از ایمیل، ذخیره خودکار پیامها و همچنین امکان ارجاع به پیامهای گذشته، ایمیل را صورت رسمی ارتباط در اکثر شرکتها و سازمانها کرده است. از طرفی مشخص بودن جزئیاتی مانند زمان ارسال، موضوع و محتوای ایمیلها این مجموعه داده را منبع مناسبی برای تحقیقات در این زمینه کرده است.
در سالهای اخیر محققان روشهای زیادی برای شناسایی گرههای مهم یا همان افراد تأثیرگذار در شبکههای اجتماعی ارائه کردهاند، که اکثر این روشها بر پایهی معیار مرکزیت میانی2 و بینظمی در گراف تعریف میشوند. ما موفق شدیم با تعریف معیار جدیدی با استفاده از ویژگیهای گرافی مانند بینظمی و ویژگیهای مجموعه داده مانند در نظر گرفتن ساعت ارسال و دریافت ایمیلها افراد رهبر را در گراف شناسایی کنیم.
در ادامه این مقاله به صورت زیر سازماندهی شده است.
در بخش 1-2 به تعاریف اولیه گراف پرداختهایم. در بخش 2-2 مسئله شناسایی گرههای مهم را مطرح کردهایم. در بخش 3-2 مجموعه دادههای مورد استفاده در مقاله را به شکل جزئیتر بررسی میکنیم. سپس در بخش -2 4 راهحل پیشنهادی خود را که مبتنی بر بینظمی گراف است معرفی میکنیم. در ادامه، در بخش 5-2 نتایجی که از این روش حاصل شد را بررسی کرده و با کارهای مشابه مقایسه میکنیم. در بخش 3 به معرفی کارهای پیشین مرتبط میپردازیم و در بخش 4 نتیجهگیری کلی را بیان کرده و چند مورد از راههای بهبود نتایج این مقاله را به منظور کارهای آینده به اختصار معرفی میکنیم.
-2 مطالب اصلی
-1-2 تعریف مفاهیم اساسی
گراف:
گراف به صورت G = <V,E> نشان داده میشود که V = {v1,…,v n} مجموعه گرههای گراف و E = {{vi,vj} : vi,vj ∈ V} مجموعه یال-های گراف هستند. در گراف جهتدار هر یال یک دوتایی مرتب به صورت E = - vi,vj - است که به صورت یک یال از گره vi به vj نمایش داده می-شود
بینظمی گره:
اگرچه مفهوم بینظمی در علم کامپیوتر به خوبی تعریف [2] و حتی تاریخچه مفصلی در رابطه با آن نوشته شده است [3] ولی اتفاقنظری روی تعریف بی-نظمی در جهان گراف وجود ندارد .[4-7] به طور مثال تعریف " کولموگروف"3 روی ماتریس مجاورت هرچند از لحاظ تئوری کارآمد به نظر میرسد ولی غیر قابل محاسبه است
در این مقاله از فرمول - 1 - که توسط "شنون"4 تعریف شده [2] برای محاسبهی بینظمی استفاده شده است.
در این فرمول P احتمال - احتمال بر اساس مجموعهای که بینظمی را برای آن محاسبه میکنیم تعریف میشود - و n تعداد اجزای مجموعه است، که احتمال روی آن تعریف شده است. بدیهی است مجموع احتمالات Pi باید برابر یک شود.
بینظمی نرمال:
بینظمی مقداری بین صفر تا بینهایت دارد. با توجه به فرمول - 1 - ، H همیشه مقداری بین 0 و lnn دارد .[9] درنتیجه با تقسیم بینظمی بر lnn، بینظمی نرمال را بهصورت زیر تعریف میکنیم که همیشه بین 0 و 1 است.
-2-2 طرح مسئله
امروزه با گسترش شبکههای اجتماعی در میان مردم، تحلیل رفتار افراد جامعه بهصورت خودکار امکانپذیر شده است. در این میان فرآیند خودکار پیدا کردن افراد مهم در شبکه اجتماعی دارای مزایای زیاد [10] و درعینحال با چالشهای جدی روبرو است. افراد مهم، سرعت انتقال اطلاعات و تأثیرگذاری روی افراد جامعه را تا حد قابلتوجهی افزایش میدهند.
در این مقاله مجموعه دادهای به صورت گراف که بازنمایی افراد و روابط بین آنها است، دریافت میشود. این گراف باید شامل زمان ارتباطات و موضوع پیامها باشد. این مجموعه داده میتواند مربوط به یک سازمان، شرکت یا حتی یک گروه تروریستی باشد. ما با اعمال روشهای مختلف در پی شناسایی رهبران این مجموعهها هستیم. در نهایت خروجی زیرمجموعهای از گرهها است که نقش رهبری را در گراف اصلی دارند.
-3-2 مجموعه داده
مجموعه داده مورد استفاده در این مقاله مجموعه داده انرون [11] است. از مهمترین دلایل استفاده از این مجموعه داده میتوان به موارد زیر اشاره کرد:
- انرون تنها مجموعهی واقعی ایمیل مربوط به یک شرکت بزرگ است که برای عموم منتشر شده است. این مجموعه شامل ایمیلهای کاری و غیرکاری است.
- به سبب آنکه ایمیل از راههای مهم ارتباطی در شرکتها است، بررسی ایمیلها راه خوبی برای درک ارتباط بین کارمندان است.
- این مجموعه داده شبیه دادههای جمعآوریشده برای تشخیص کلاه-برداری و تروریسم است، به همین دلیل روشهای ارائهشده در این مقاله میتواند برای تشخیص این موارد استفاده شود.
- و در آخر با توجه به مشخص بودن سمت کارمندان، این مجموعه داده برای اعتبارسنجی مدل ارائهشده مناسب است.
- مقالات متعددی با استفاده از این مجموعه داده روشهای خود را ارزیابی کردهاند [12-14]، بنابراین میتوان کارایی روش ارائه شده را با روشهای مختلف مقایسه کرد.
مجموعه دادهی انرون توسط کمیته تنظیمکننده انرژی فدرال5 برای عموم منتشر شده است. نسخه مورداستفاده در این مقاله توسط "روح[15] "6 بهبود یافته است. این مجموعه شامل 517431 ایمیل از 151 کارمند است. هر کارمند به طور متوسط 2 آدرس ایمیل دارد. در این مقاله هر آدرس ایمیل بهعنوان یک گره در نظر گرفته شده است. این مجموعه داده شامل فرستنده، گیرنده، تاریخ و زمان ارسال، موضوع و متن ایمیلها است. همچنین سمت کارمندان در شرکت نیز مشخص شده است. ما بخشی از گراف را نمونهبرداری کردهایم. این بخش شامل 9661 گره و 70000 یال است.
-4-2 راه حل پیشنهادی
به منظور شناسایی گرههای مهم، ابتدا به استخراج موضوع ارتباط و تفکیک آن به کلمات7 میپردازیم. سپس گراف جهتدار و وزندار بین افراد را می-سازیم. وزن را تعداد تکرار کلمه در موضوع مکالمات بین افراد در نظر میگیریم. در مرحله بعد با اعمال فرمول - 1 - ، برای هر گره یک امتیاز اولیه در نظر میگیریم. سپس بینظمی نرمال را برای گراف بهدستآمده محاسبه می-کنیم. احتمال P در فرمول را از تقسیم وزن یال Wi به مجموع وزن یالهای گره Wt به دست میآوریم.
در فرمول - 3 - ، n درجه گره و ln لگاریتم طبیعی است.
با توجه به فرمول - 3 - ، افراد با توزیع یکنواخت وزن روی یالها و مخاطبین بالا، رتبه بالاتری دارند.
فرض میکنیم افراد مهم ایمیلهای ارسالی بیشتری نسبت به ایمیلهای دریافتی دارند. همچنین این افراد بیشتر ایمیلهای خود را در ساعات اداری ارسال میکنند.
با در نظر گرفتن دو فرضیه بالا، نسبت تعداد ایمیلهای ارسالی به کل ایمیلهای ارسالی و دریافتی را به عنوان نسبت نرمال ایمیلهای ارسالی - فرمول - - 4 - و همچنین نسبت تعداد ایمیلهای ارسالی در ساعت اداری به کل ایمیلهای ارسالی را به عنوان نسبت نرمال ایمیلهای ارسالی در ساعت اداری - فرمول - - 5 - تعریف میکنیم.
تعداد ایمیلهای ارسالی sent_CNT = تعداد ایمیلهای دریافتی received_CNT =
تعداد ایمیلهای ارسالی در ساعت اداری inTime_CNT = تعداد ایمیلهای ارسالی در خارج از ساعت اداری
-5-2 نتایج عملی
ابتدا کلمات موضوع ایمیلها را از هم جدا کردیم و به ازای هر کلمه یک یال از فرستنده به گیرنده ساختیم و تکرار کلمه را بهعنوان وزن یال در نظر گرفتیم. گراف خروجی شامل 9661 گره و 200597 یال است
بینظمی نرمال را با استفاده از فرمول - 3 - برای گراف بهدستآمده محاسبه میکنیم و به هر کارمند یک امتیاز اولیه اختصاص میدهیم. نتیجه مرتب-سازی صعودی این امتیاز اولیه را در جدول - 1 - نشان دادهایم.
جدول : - 1 - شناسایی مهمترین گرهها با استفاده از فرمول . - 3 -
حال برای بهبود نتایج، از فرمول - 4 - استفاده میکنیم. قابلذکر است به دلیل مرتب کردن نزولی افراد از - - استفاده کردیم. ساعت کاری 6 صبح تا 6 بعدازظهر فرض شده است.
جدول : - 2 - شناسایی مهمترین گرهها با استفاده از فرمول
حضور یک کارمند - "جف داسویچ - "9 در میان پنج نفر مهم شناسایی شده توسط الگوریتم پیشنهادی ممکن است در نگاه اول باعث تعجب شود ولی با اندکی بررسی بیشتر متوجه میشویم که ایشان از نقش مهمی در شرکت برخوردار بودند و به عنوان ارتباط دهنده شرکت با دولت انجام وظیفه میکردند بنابراین حضور ایشان میتواند از مزایای الگوریتم پیشنهادی باشد. پیچیدگی الگوریتم پیشنهاد شده O - m - است m - تعداد یالهای گراف - . در نتیجه برای گرافهای تنک10 نزدیک به O - n - و برای گرافهای انبوه11 نزدیک به O - n2 - است.
میتوان معیارهای ارائهشده - فرمول - 3 - و فرمول - - 4 - را با معیار طبیعی مانند درجه مقایسه کرد. نتایج مرتبسازی نزولی کارمندان بر اساس تعداد ایمیلهای ارسالی و دریافتی در جدول - 3 - آمده است.
جدول : - 3 - شناسایی مهمترین گرهها با استفاده از تعداد ایمیلهای ارسالی و دریافتی هر گره.
نتایج نشان میدهند که این معیار نیز نسبت به رویکرد استفاده شده توسط ما، دقت پایینتری دارد.
جدول : - 4 - شناسایی مهمترین گرهها با استفاده از مرکزیت میانی
