بخشی از مقاله
چکیده
شبکههای اجتماعی در سالهای اخیر پیشرفتهای قابلتوجهی داشتهاند و به سرعت از راههای گوناگون در حال انتشار هستند. همزمان با این پیشرفتها باید حریم خصوصی موجودیتهای شبکه اجتماعی حفظ شود. حریم خصوصی در شبکههای اجتماعی به وسیله گمنامی به دست میآید. برای روش ارائهشده در این پژوهش، از ترکیب روشهای خوشهبندی رئوس و ساخت بهینه گراف استفاده شده است. در این پژوهش شبکههای اجتماعی با چندین نوع ارتباط و همچنین یالهای حساس بین افراد در نظر گرفته شده است و هدف حفظ حریم خصوصی دادههای منتشرشده به وسیله اصلاح گراف با افزودن کمترین تعداد یال است. پس از اعمال گمنامی برای هر k رأس گمنام شده، علاوه بر یکسان بودن درجه رئوس، ارتباطات رئوس مذکور نیز باهم یکسان میشوند.
همچنین شبکه اجتماعی پس از گمنامی در برابر حملات همسایگی مقاوم میشود. برای این منظور مدلی جهت حفظ حریم خصوصی دادههای منتشرشده شبکههای اجتماعی ارائه میشود که از یک الگوریتم حریصانه بهره میبرد. این الگوریتم با استفاده از اصلاح گراف به صورت بهینه عمل میکند و از لحاظ پیچیدگی زمانی و حافظه مصرفی کارا است. هدف اصلی در این پژوهش این است که بین حریم خصوصی موجودیتها، سودمندی دادهها و همچنین هزینه گمنامی توازن بهینه ای به وجود آید.
-1 مقدمه
شبکههای اجتماعی به دلیل ارتباطات با معنی بین موجودیتهایشان، اطلاعاتی فراتر از آنچه که در ظاهر امر نشان میدهند در خود نهفته دارند. نقض حریم خصوصی میتواند زمینهساز ایجاد مشکلاتی برای افراد گردد که این خود به صورت معضلی در بحث تهیه دادههای آماری برای تحلیلگران تبدیل شده است. هر مدلی که در مورد حفظ حریم خصوصی دادههای منتشرشده ارائه میشود، دو هدف اساسی را در نظر میگیرد.
این دو هدف، حفظ حریم خصوصی و میزان سودمندی دادههای منتشر شده است. مسئلهای که در اینجا باعث دشوار شدن کار میشود، متضاد بودن این دو هدف است؛ به عبارت دیگر در صورتی که مدلی ارائه شود که حریم خصوصی را به طور صد در صد تضمین نماید، میزان سودمندی دادهها مقدار صفر درصد خواهد بود؛ چرا که تنها در صورتی حریم خصوصی به طور کامل و بینقص حفظ خواهد شد که هیچ دادهای منتشر نشود. حفظ حریم خصوصی مطلق نیز امکانپذیر نیست. دلیل عمده آن وجود حملات با دانش قبلی دشمن است . حریم خصوصی در شبکههای اجتماعی به وسیله گمنامی به دست میآید.
در سالهای اخیر تعاریف گوناگونی از گمنامی گراف ارائه و مورد مطالعه قرار گرفته است. ژو و پیآی [1,2] مدلی برای حفظ حریم خصوصی شبکههای اجتماعی در برابر حملات همسایگی مرتبه اول ارائه کردند. آنها فرض کردند مهاجم ساختار زیرگراف را توسط همسایگان بلا واسطه - مستقیم - گره هدف میشناسد. مدل آنها شبکههای اجتماعی ساده ای را در نظر گرفته بود، به طوری که ارتباطات چندگانه در آنها وجود نداشت. علاوه بر این، وجود ارتباطات حساس و همچنین اطلاعات مربوط به ارتباطات را در نظر نگرفتند.
زو و همکاران در [3] چارچوبی را تحت عنوان -kخود ریختی 1 برای گمنام سازی شبکههای اجتماعی ارائه دادند. الگوریتمی که آنها ارائه دادند، شبکه اجتماعی را به یک شبکه خود ریخت تبدیل میکند. آنها برای رئوس هیچگونه اطلاعات و برچسبی در نظر نگرفتند. همچنین یک فرض عمومیتر را در مطالعات خود پذیرفتند؛ به این ترتیب که مهاجم میتواند همه زیرگرافهای اطراف فرد را شناسایی کند . آنها راهحلی برای ساخت گراف G' به طوری که برای هر زیرگراف x G و گراف G' شامل حداقل k زیرگراف هم ریخت با x باشد، ارائه دادند.
در [4] اثبات شده است که گمنامی بر مبنای یافتن دنباله برچسبها برای زیرمجموعهای از رئوس با افزودن کمترین تعداد یال هنگامی که k>2 باشد، دارای پیچیدگی NP-hard است. با توجه به این که در برخی از کاربردها در شبکههای اجتماعی نیاز است تا تنها زیرمجموعهای از رئوس گمنام شوند؛ به عبارتی در بعضی از کاربردها، برخی از موجودیتها الزامی به گمنامی ندارند، حال آنکه گمنامی زیرمجموعهای از رئوس دارای اهمیت است.
ما در این پژوهش الگوریتمی حریصانه برای گمنامی گرافهای با دنباله برچسبها ارائه میدهیم که به صورت بهینه عمل میکند، به عبارتی هدف این است که بین حریم خصوصی موجودیتها و سودمندی دادهها و همچنین هزینه گمنامی توازن بهینهای به وجود آید. در ادامه در بخش 2 تعاریف اولیه مورد نیاز در مورد روش پیشنهادی برای ورود به بحث آمده است. تعریف مسئله در بخش 3 مطرح شدهاست. روش پیشنهادی، تحلیل پیچیدگی و معیار هزینه گمنامی به ترتیب در بخشهای 4، 5 و 6 آمده است. بخش 7 بررسی موردی روش پیشنهادی و در نهایت بخش 8 شامل نتیجهگیری و آینده پژوهش است.
-2 تعاریف اولیه روش پیشنهادی
در این قسمت تعاریف اولیه استفادهشده در این پژوهش آورده شده است.
-1-2 شبکههای اجتماعی
یک شبکه اجتماعی به صورت گراف - G= - V, E, L, میتواند مدل شود. در این گراف، V مجموعه رئوس گراف است که موجودیتهای شبکه اجتماعی را نشان میدهد. E نشاندهنده یالها است که ارتباط بین موجودیتها را نشان میدهد که خود مجموعهای از مجموعه انواع یالها است. به عبارت دیگر E= {E1, E2' …' - n} به طوری که Ei مجموعه یالهای نوع i است. L مجموعه برچسبها است و تابعی است که برچسبها را به رئوس و یالها الصاق میکند - رابطه . - 1
-2-2 شبکههای اجتماعی چند رابطهای
در برخی از شبکههای اجتماعی تنها یک نوع ارتباط میان موجودیتها وجود دارد، درحالیکه در بعضی دیگر، چندین نوع ارتباط بین موجودیتها در نظر گرفته میشود. به عنوان مثال در یک شبکه اجتماعی ممکن است موجودیتها ارتباط دوستی، همکاری و همکلاسی را به طور همزمان داشته باشند. به اینگونه از شبکههای اجتماعی، شبکههای اجتماعی چند رابطهای2 گفته میشود. شکل - 1 - نمونهای از یک شبکه اجتماعی چند رابطهای است. در واقع اینگونه از شبکههای اجتماعی، جامعتر و به دنیای واقعی نزدیکتر هستند.
-3-2 گراف همسایگی
در یک شبکه اجتماعی G، گراف همسایگی رأس v، زیرگرافی است متشکل از رئوس متصل به v که با NeighborG - v - = G - Nv - نمایش داده میشود. G - Nv - به صورت G - Nv - = {u| - v,u - E - G - } در نظر گرفته میشود. در شکل - 2 - گراف -1همسایگی رأس Bill که بخشی از شبکه اجتماعی شکل - 2 - هست آورده شده است.
-4-2 حملات همسایگی
اگر مهاجم نسبت به موجودیتهای یک شبکه اجتماعی، دانش قبلی داشته باشد و در آن شبکه صرفاً هویتهای منحصربهفرد موجودیتها حذف شده باشد، وی خواهد توانست حریم خصوصی موجودیتها را نقض کند و اطلاعات بیشتری نسبت به قبل به دست آورد. با اینکه برای حفظ حریم خصوصی در شبکههای اجتماعی، قبل از انتشار دادهها، هویتها و شناسههای منحصربهفرد افراد را حذف میکنیم، با این حال این عمل کافی نخواهد بود.
اگر دشمن گراف همسایگی مرتبه اول 1 - -همسایگی - رأس هدف را بداند، خواهد توانست اطلاعاتی در رابطه با موقعیت هدف در گراف نهایی، ارتباطات وی و اطلاعات مفید دیگری به دست آورد .[5] به عنوان مثال در شکل - 1 - رئوس نشاندهنده دانشجویان و ارتباطات بین آنها به دو دسته تقسیم شده است. نوع اول ارتباط همکلاسی بودن است که با a نمایش داده شده است. نوع دوم ارتباط دوستی است که با b نشان داده شده است.
اکنون فرض کنید که این شبکه اجتماعی را میخواهیم منتشر کنیم درحالیکه حریم خصوصی افراد حفظ شوند. در ابتدا برای دستیابی به این هدف، هویتها و شناسههای منحصربهفرد افراد را از شبکه اجتماعی حذف میکنیم؛ اما این عمل کافی نخواهد بود. در شکل - 1 - فرض کنید مهاجم میداند Bill دو دوست و یک همکار دارد. به عبارت دیگر، دشمن گراف -1همسایگی Bill که در شکل - 2 - نشان داده شده است را می داند. بنابراین، دشمن با قطعیت میتواند Bill را در گراف منتشرشده بیابد، چرا که گراف -1همسایگی Bill منحصربهفرد است.
شناسایی افراد در گراف منتشرشده شبکه اجتماعی، حریم خصوصی آنها را نقض میکند. برای حفظ حریم خصوصی، خواستهای که مورد نظر است این است که تضمین شود هیچ موجودیتی در یک شبکه اجتماعی چند رابطهای گمنام شده با احتمال بیشتر از شناسایی نخواهد شد. k پارامتر گمنامی است که توسط صاحبان دادهها تعیین میشود. این مدل منطبق با رویکرد مدل -kگمنامی سوئینی [6] است.
-5-2 دنباله برچسبها - Label Sequence -
برای هر گره vi V، دنباله مرتبی از برچسب یالهای وارده به v، دنباله برچسبهای یال های وارده به vi نامیده میشود که در ادامه به اختصار آن را LS مینامیم. برای مثال در شکل - 1 - دنباله برچسبهای رأس مربوط به Bill به صورت aab است.
-6-2 دنباله برچسب گروه - Label Sequence Group -
دنباله برچسب گروه دنبالهای است که:
1. طول آن مینیم باشد.
2. توسط آن، دنباله برچسب همه رئوس موجود در گروه تولید شود. در ادامه دنباله برچسب گروه را LSG مینامیم.
-7-2 دنباله برچسبهای باقیمانده جهت گمنامی برای هر رأس در گروه - Remain Label Sequence - Anonymity
این دنباله از تفاضل دنباله بر چسبهای گروه و دنباله برچسبهای مربوط به یک رأس به دست میآید. به عبارتی این دنباله تعداد یالهایی که باید به یک رأس جهت گمنامی افزوده شود را نشان میدهد که در ادامه به اختصار آن را RLSA مینامیم. RLSA = LSG - LS
-k -8-2گمنامی برای یک رأس
در صورتی که برای گره v از مجموعه رئوس V در گراف G، حداقلk-1 رأس با دنباله برچسبهای مشابه وجود داشته باشد، در این صورت -kگمنامی برای آن رأس اعمال شده است.
-3 مسئله
همان طور که ذکر شد در برخی از کاربردها در شبکههای اجتماعی نیاز است تا تنها زیرمجموعهای از رئوس گمنام شوند؛ به عبارتی در بعضی از کاربردها، برخی از موجودیتها الزامی به گمنامی ندارند، حال آنکه گمنامی زیرمجموعهای از رئوس دارای اهمیت است. در [4] اثبات شده است که گمنامی بر مبنای یافتن دنباله برچسبها برای زیرمجموعهای از رئوس با افزودن کمترین تعداد یال هنگامی که k>2 باشد، دارای پیچیدگی NP-hard است. در این قسمت، به ارائه روشی برای حفظ حریم خصوصی دادههای منتشرشده شبکههای اجتماعی چندرابطهای میپردازیم. هدف از ارائه این روش، مقابله با حملات همسایگی مرتبه اول هست.
به عبارتی در صورتی که دشمن، دانشی نسبت به گراف همسایگی یک رأس داشته باشد، فراتر از احتمال مشخصی نخواهد توانست موقعیت وی را در گراف گمنام شده تشخیص دهد و حریم خصوصی وی نقض شود. در این روش، شبکههای چندرابطهای، همچنین ارتباطات حساس و غیر حساس در نظر گرفتهشدهاند و رئوس دارای برچسبهای اطلاعاتی هستند که در حفظ حریم خصوصی باید در نظر گرفته شوند. همان طور که گفته شد در این پژوهش از روشهای خوشهبندی رئوس و ساخت بهینه گراف استفاده شده است. خوشهبندی طوری انجام میشود که کمترین تعداد یال جهت رسیدن به -kگمنامی به گراف افزوده شود.
-4 روش پیشنهادی
در شبکههای اجتماعی واقعی، دو ویژگی مهم حاکم هست. این دو ویژگی در طراحی مدل گمنامی میتوانند مؤثر باشند. ویژگی : - 1 - درجه رئوس در شبکهای اجتماعی بزرگ، عموماً از قانون توزیع توان3 پیروی میکنند.[7] این ویژگی در شبکههای اجتماعی مختلفی مانند اینترنت، شبکههای زیستشناسی و شبکههای همکاری به وضوح مشاهده شده است. ویژگی : - 2 - پدیده جهان کوچک، بیان می کند که شبکههای اجتماعی بزرگ واقعی، عموماً قطر کوچکی دارند.[8]
از آن جا که مدل مبنای این مسئله، مدل -kگمنامی هست، در نتیجه هر رأس، حداقل با k-1رأس دیگر باید در یک گروه قرار گیرد. طبیعتاً در هر گروه، رئوس نیز درجههای یکسانی خواهند داشت، علاوه بر آن با توجه به ماهیت مسئله، برچسب یالهای وارده به رئوس نیز باید باهم برابر باشند. از آن جا که درجههای رئوس در شبکههای اجتماعی از ویژگی - 1 - پیروی میکنند، در نتیجه تعداد کمی از رئوس، درجه بالایی خواهند داشت.
شروع گمنامسازی از رئوس با درجه بالاتر میتواند میزان از دست رفتن اطلاعات را کاهش دهد. معمولاً تعداد زیادی از رئوس، درجه کمی دارند. گمنامسازی رئوس با درجه کم به طوری که کیفیت بالایی در گمنامسازی وجود داشته باشد،نسبتاً سادهتر از رئوس با درجه بالاتر است. علاوه بر اینها، رئوس با درجه کمتر میتوانند در گمنامسازی شبکههای بزرگتر مؤثر باشند؛ به طوری که کمترین تأثیر بر روی قطر گراف حاصل شود و با هزینه کمتری گمنامسازی صورت پذیرد .[9] در ادامه، روش پیشنهادی که شامل دو مرحلهی، خوشهبندی رئوس و افزودن یال هست، ارائه خواهد شد. دلیل استفاده از هر دو روش خوشهبندی رئوس و اصلاح بهینه گراف این است که بتوانیم از مزایای هر دو روش برای گمنامی شبکههای اجتماعی استفاده کنیم و درعینحال معایب این روشها را در گمنامی شبکههای اجتماعی برطرف کنیم.
-1-4 خوشهبندی رئوس
خوشهبندی رئوس شامل گامهای زیر است.
گام اول: در ابتدا، مقادیر منحصربهفرد رئوس و همچنین ارتباطات حساسی که عموماً توسط صاحبان دادهها مشخصشدهاند را حذف میکنیم.
