DOI: http://dx.doi.org/10.22059/jitm.2014.50936
د ناوری اطلاعات دانشكدة مديريت دانشگاه تهران
دورة 6، شمارة 3 پاييز 1393 ص. 486 – 475

ارائة روشي جديد براي پيشگويي پيوند بين رأس هاي موجود در
شبكه هاي اجتماعي
اعظم كي پور1، مرتضي براري2، حسين شيرازي3
چكيده: امروزه شبكه هاي اجتماعي برخط، به دليل امكان ايجاد ارتبـاط بـين افـراد مختلـف درسرتاسر دنيا محبوبيت زيادي دارند. اين شبكه هـاي اجتمـاعي كـه از امكانـاتي ماننـد پيشـنهاد دوست به كاربران برخوردارند، در اغلب موارد براي بيان پيشنهادهاي خود، از ويژگي هاي محلـي ساختار گراف شبكه استفاده ميكنند. براي بيان پيشنهاد در اين شبكه ها، روش هاي مختلفـي بـادو رويكرد محلي و سراسري پيمايش گراف شبكه پيشنهاد شده و مورد استفاده قرار مـيگ يـرد. در اين مقاله روشي با رويكرد محلي ارائه شده است كه در مقايسـه بـا روش هـاي ديگـر، داراي كارايي مناسبي است، علاوهبر اينكه به دليل محليبودن رويكرد، از سرعت قابل قبولي برخـورداراست. بر اساس ارزياب ياي كه روي مجموعه داده هاي دو شبكة اجتمـاعي بـزرگFacebook و Epinions انجام شده است، اين ويژگي جديد مي تواند پيشگويي خوبي براي يـال هـايي انجـامدهد كه قرار است در آينده شكل بگيرند و در نتيجه پيشنهادهاي قابل قبولي را ارائه دهد.

واژه هاي كليدي: پيشگويي پيوند، سيستم هاي پيشنهاددهنده، شبكه هاي اجتماعي.

دانشجوي كارشناسي ارشد هوش مصنوعي، دانشگاه صنعتي مالك اشتر، تهران، ايران
استاديار مخابرات سيستم، دانشگاه صنعتي مالك اشتر، تهران، ايران
دانشيار هوش مصنوعي، دانشگاه صنعتي مالك اشتر ، تهران، ايران

تاريخ دريافت مقاله: 25/08/1392 تاريخ پذيرش نها يي مقاله: 30/04/1393 نويسندة مسئول مقاله: اعظم كيپور
E-mail: a.keypour@gmail.com
مقدمه
شبكههاي اجتماعي شبكههاي پويايي اند كه همواره اعضا و ارتباطات و پيوندهاي بين آنها رو بـهافزايش است. زنجيرة اين پيوندها گاهي به دليل فرآيند ايجاد ناقص يا به دليل اينكه هنوز در ايـن شبكهها انعكاس نيافته اند (براي مثال، دوستان دنياي واقعي كه يـك ارتبـاط اجتمـاعي مجـازي ايجاد نكرده اند)، پاره شده و از دست مي روند (فاير و ديگران، 2011)، لذا يكي از مسائل مهـم در شبكههاي اجتماعي، مسئلة پيشگويي پيوند1 است.
مسئلة پيشگويي، يكي از جنبه هاي مهم داده كاوي است. داده كاوي پيشگويي كننده، مـدلي از سيستم ارائه مي كند كه اين مدل را مجموعه اي از دادههاي مشخص، پيش بيني مي كنند و هدف كلي آن ايجاد الگويي براي طبقهبندي، پيش بيني و تخمين داده ها است (رادفر، نظافتي و يوسـفياصل، 2014).
پيشگويي پيوند، به معناي وجود و عدم وجود يك پيوند يا ارتباط در آينده بـين دو رأس يـكشبكة اجتماعي است و يك ابزار مهم براي تحليل شـبكه هـاي اجتمـاعي بـه شـمار مـي رود كـه كاربردهاي زيادي نيز در حوزه هاي ديگري چون، باز يـابي اطلاعـات، با يوانفورماتيـك و تجـارتالكترونيك دارد. به علاوه در حوزة علم وب و اينترنت، ميتواند در كارهايي ماننـد ايجـاد ابرپ يونـد خودكار وب و پيشبيني ابرپيوند سايتهاي وب كاربرد داشته باشد (الحسن و زكي، 2011).
يكي از مهمترين كاربردهاي پيشگويي پيونـد در تجـارت الكترون يـك ، ايجـاد سيسـتم هـاي پيشنهاد دهنده است. اين پيشنهادها مي توانند شامل پيشنهاد كالا يـا پيشـنهاد دوسـت باشـند. از جمله فوايد پيشگويي پيوند اينكه با پيشنهادهاي مناسب در زمينة كالا، مـي تـوان ضـريب خريـداينترنتي افراد جامعه را بالا برد. عمل خريد تحـت تـأثير بسـياري از خصـايص مشـتريان، ماننـد ويژگي هاي شخصيتي، سبك زندگي، دانش و م هارتها، عوامل اجتماعي، عوامل رواني و عوامـلجمعيتي قرار دارد ( حسنقليپور، اميري، فهـيم و قـادري عابـد، 2014). خريـد اينترنتـي براسـاستجربة واقعي از خريد كالا صورت نمي گيرد، بلكه براساس ظواهري مانند تصوير، شكل، اطلاعات كيفي و تبليغات از كالا استوار است؛ به همين دليل جلب اعتماد مشتري براي انجـام مبـادلات ازطريق اينترنت، مورد توجه بسياري از سـازمان هـا و مشـتريان قـرار گرفتـه اسـت ( سـاجدي فـر، اسفيداني، وحدتزاد و محمودآذر، 2012).
يكي از راههاي جلب اعتماد مشتري، به واسطة اعتماد به افرادي حاصل ميشود كه با وي در يك شبكة اجتماعي در ارتباط بوده و از كالاي مورد نظـر اسـتفاده مـي كننـد. بـه همـين دليـل،
ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
1. Link prediction
هم پيوندي به معني تمايل اعضا براي پيوند و ارتباط با يكديگر، بـه منزلـة ويژگـي مهمـي بـراييكپارچه سازي اطلاعات ياد شده است كه موجب پايداري كسب وكارها مي شود (ايراني و حقيقـي،2014). در اين زمينه پيشگويي پيوند با تحليل ارتباطات موجود در شبكه هاي اجتماعي، مي توانـدفرآيند پيشنهاد كالا و خدمات را تسهيل كند.
از جنبة دوست يابي نيز، شبكه هاي اجتماعي برخطي مانند فيس بوك داراي حجـم انبـوهي از داده هستند كه مي توانند با جست وجو در ميان آنها و تحليل اطلاعات موجود، در اين مورد كه چه كسي ممكن است بخواهد با ديگري دوست شود، پيشگويي كنند و بر اساس اين پيشگويي ها بـهكاربران پيشنهادهاي مناسبي ارائه دهند.
ساختار شبكه هاي اجتماعي، به صورت گرافي مدل مي شود كه رأس ها ي گراف همان كاربران شبكه هستند و ارتباطات بين اين كاربران، يال هاي گراف را شكل ميدهند. براي ارائـ ة پيشـنهاد در اين شبكه ها دو رويكرد كلي وجود دارد. رويكرد اول كه مبتني بر ويژگي هـاي محلـي سـاختارگراف شبكه است، روشي است كه معمولاً در شبكه هـاي اجتمـاعي بـرخط مـورد اسـتفاده قـرار مي گيرد. اين شبكه ها معمولاً پيشگوييهاي خود را بر اساس تعداد دوستان مشتركي كه دو كاربر دارند، انجام مي دهند؛ زيرا احتمال بسيار زيادي وجود دارد كه دو كـاربري كـه دوسـتان مشـترك زيادي دارند، تمايل داشته باشند با يكديگر چه در دنياي مجازي و چه در دنيـاي واقعـي دوسـتشوند. اشكالي كه به اين روش ها وارد است، به در نظر گرفتن حداكثر فاصلة 2 بين هر دو كـاربردر گراف شبكه برمي گردد كه ممكن است از دقت كافي برخوردار نباشند.
در مقابل روش هاي با رويكرد محلـي ، ماننـد روش دوسـت ـ دوسـت يـا دوسـتان مشـترك
(الحسن و زكي، 2011)، آداميك ـ آدار (آداميك و آدار، 2005)، ضريب جاكارد (الحسـن و زكـي،
2011) و…، روش هاي سراسري نيز وجود دارند كه براي يافتن ميزان شباهت بـين دو فـرد، كـلگراف شبكه را پيمايش مي كنند. از آنجايي كـه ايـن روش هـا كـل اطلاعـات شـبكه را در نظـر ميگيرند، ممكن است از دقت زيادي برخوردار باشند، ولي بار محاسباتي بـالايي دارنـد و طبيعتـاًبراي شبكههاي اجتماعي برخط مناسب نيستند. از جمله روشهايي كه مبتنـي بـر ايـن رويكـرد هستند، معيار كاتز (ليبن ناول و كلينبرگ، 2003)، گام تصـادفي بـا شـروع مجـدد1 (بكسـتورم ولسكاوس، 2011) و simrank ( جه و ويدوم، 2002) را مي توان نام برد.
در اين نوشتار روشي ارائه خواهد شد كه با استفاده از رويكردي محلي، در تهيـ ة يـك معيـارجديد براي پيشنهاد دوست و پيشگويي پيوند، در كنار بهـره منـدي از مزيـت سـرعت روش هـا ي محلي، از كارايي مناسبي نسبت به ساير روشهاي موجود، برخوردار است.
ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
1. Random Walk with Restart (RWR)
اين مقاله به اين صورت ساماندهي شده است؛ در ادامة مطالب فعاليت ها، كارهـا ي مـرتبط وروش هاي موجود پيشگويي پيوند بيان شده است. در بخـش بعـدي روش پيشـن هادي شـرح دادهمي شود و پس از آن نتـايج تجربـي مربـوط بـه روش پيشـنهادي بيـان خواهـد شـد و بـا يـكنتيجه گيري از مطالب گفته شده به پايان مي رسد.
پيشينة پژوهش
ويژگي ها و معيارهاي مختلفي براي پيشگويي پيوند بين رأس هاي موجود در شبكه هاي اجتماعي وجود دارد. برخي از اين روش ها در استخراج اطلاعات از گراف ارتباطات شـبكه هـا ي اجتمـاعي،رويكردي محلي دارند و برخي از رويكردي سراسري پيروي ميكننـد . در ادامـه تعـدادي از ايـنمعيارها را كه معمولاً در شبكههاي اجتماعي به كار برده ميشوند، معرفي كرده و سپس به ارزيابي آنها پرداخته خواهد شد.
معيار دوستان مشترك: به منزلة يكي از معيارهاي محلي ميتوان از روش دوست ـ دوست1 يـادوستان مشترك2 (الحسن و زكي، 2011) نام برد كه در شـبكه هـايي چـون فـيس بـوك 3 مـورداستفاده قرار مي گيرند. در اين روش رأسهايي كـه بـا طـول مسـير 2 بـه هـم مـرتبط هسـتند، كانديداي پيشنهاد دوست در نظر گرفته شده و پيشنهاد مي شـوند و آن رأس هـايي كـه بـا تعـدادمسير بيشتري با يكديگر ارتباط دارند (دوستان مشترك بيشتري دارنـد)، داراي احتمـال بـالاتري براي ايجاد پيوند هستند.
معيار آداميك آدار: معيار آداميك آدار4 (آداميك و آدار، 2005) از معيار شباهتي استفاده مي كنـدكه در اصل براي يافتن ارتباطات قـوي بـين صـفحات وب بـه كـار مـي رود و مربـوط بـه تعـداد ويژگيهاي مشتركي است كه دو صفحه بهاشتراك گذاشته اند. در مسـئلة پيشـگويي پيونـد، ايـنويژگي مشترك همان همساية مشترك دو رأس است. ميزان شباهت بين دو رأس در ايـن روشاز رابطة 1 به دست مي آيد.
1
رابطة 1) |Γ( )|

= (,)
∈()∩ ( )
در اين رابطه، z: همساية مشترك دو رأس u و v و |Γ( )|: درجة رأس z است.
ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
FOAF
Common friends
www.facebook.com
Adamic-Adar
معيار كاتز: معيار كاتز1 (ليبن ناول و كلينبـرگ، 2003) از دسـته معيار هـاي سراسـري بـه شـمار ميرود و مبتني بر معيار كوتاهترين مسير است. براي به دست آوردن ميزان شباهت بـين دو رأس، تمام مسيرهاي موجود بين آن دو را بررسي ميكند و بهكمك رابطة 2 محاسبه مي شود.
رابطة 2) ,ℎ= (,)
كه در آن ,ℎ به تعداد مسيرهايي اشاره مي كند كه با طول 1 بين u و v وجود دارد و مقداري بين صفر و 1 دارد. ايرادي كه به اين معيار وارد است، مرتبة زماني چندجملهاي درجـهسه آن است، به همين دليل نمي توان براي شبكه هاي بزرگ از آن استفاده كرد.
ضريب جاكارد: ضريب جاكارد2 (الحسـن و زكـي، 2011) شـباهت بـين مجموعـه نمونـههـا را اندازهگيري ميكند و درواقع، اندازة ارتباطات تقسيم بر اندازة اجتماع مجموعه هاي نمونـه تعريـف ميشود. بنابراين ضريب جاكارد كه نسبت بين دوستان مشترك u و v به كـل دوسـتان ايـن دواست، به صورت زير محاسبه مي شود (رابطة 3).
|( )Γ( ) ∩ Γ|رابطة 3) |(

در اين رابطه Γ( ) مجموعه همسايه هاي رأس u است.
امتياز الحاق ترجيحي: امتياز الحاق ترجيحي3 (كوكيرسكي، هامنر و يانگ، 2011) بر اين ايـدهاستوار است كه كاربران با دوستان زياد، به ايجاد ارتباطات بيشتر در آينده تمايل دارند. اين معيـاركه در موارد بسياري پاسخ هاي مثبتي داشته است، از رابطة 4 محاسبه مي شود.
−ℎ−(,)
رابطة 4) |( )Γ( )|. |Γ|=
انديس ترفيع هاب: انديس ترفيع هاب (HPI)4 (زيو، لو، زنگ و زو، 2012) براي تعيين كيفيت هم پوشاني توپولوژيك جفت لايه ها در يك شبكة دگرگون شونده به كار ميرود و به صورت رابطـة5 تعريف مي شود.
ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
Katz
Jaccard Coefficient
Preferential attachment
Hub Promoted Index
|Γ( ) ∩ Γ( )|
(,) =

|Γ( )|, |Γ( )| (5 رابطة
انديس فشردة هاب: انديس فشردة هاب (HDI)1 (زيو، لو، زنگ و زو، 2012) مشـابه انـديسبالاست، با اين تفاوت كه مقدار حداكثر درجه ها را در نظر ميگيرد (رابطة 6).
|Γ( ) ∩ Γ( )|
(,) =

|Γ( )|, |Γ( )| (6 رابطة
معيار دوستان: معيار دوستان (فاير و ديگران، 2011) با در نظر گـرفتن همـة همسـايه هـا ي دو كاربر، به معناي تعداد اتصالات بين همسايه هاي u و v است كه براي دستيابي بـه ايـن تعـداد ازرابطة 7 استفاده مي شود.
−(,) =(,)
رابطة 7) ( )()

δ(,) = 1=(,)( ,)

معيار وزن يال: معيار وزن يال2 (كوكيرسكي و همكـاران ، 2011)، ابتـدا بـهصـورت دو ويژگـيجداگانه براي هر يك از دو سر لبه محاسبه مي شود (رابطة 8).
1
( ) =
رابطة 8)
1373505-329672( ) =
+ |Γ( )|
حال وزن يال بين دو رأس v و u مي تواند از طرق مختلف محاسبهشده و مورد بهره بـرداريقرار گيرد و دو معيار زير را شكل دهد.
جمع وزن ها: جمع وزن ها (كوكيرسكي و همكاران، 2011) برابر است بـا جمـع دو وزن تعريـفشده در رابطة 8:
ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
Hub Depressed Index
Edge weight
رابطة 9) ( )+ ( )= (,)
ضرب وزن ها: ضرب وزن ها (كوكيرسكي و همكاران، 2011) برابر است با ضرب دو وزن تعريف شده در رابطة 8:
رابطة 10) ( )× ( )= (,)
ضريب خوشه بندي: ضريب خوشه بندي1 (فيزا، بيكداش و لبـي، 2011) برابـر اسـت بـا نسـبتتعداد همسايگان مشترك بين دو رأس بر مقدار حداقل درجة اين دو رأس و مقـدار آن بـه كمـكرابطة 11 محاسبه مي شود.
رابطة 11)
در رابطة 11 دراية uzام ماتريس مجاورت گراف شبكه است.
همبستگي درجه: همبستگي درجه2 (فيزا و همكـاران ، 2011) متناسـب بـا ضـريب همبسـتگيپيرسون است، به شكل زير تعريف مي شود:
−(,)
رابطة 12) |( )Γ( )|. |Γ( )| − |Γ( )| − |Γ| 4.=

.2 |Γ( )|+ 2. |Γ( )|− |Γ( )| − |Γ( )|
روش Friend Link: روش Friend Link (پاپاديميتريو، سيمونيديس و مانولوپوس، 2011) بـادر نظر گرفتن يك كران، مسيرهاي كوتاه تـر از ايـن كـران را بـين دو رأس بررسـ ي مـي كنـد واين گونه از مزيت سرعت روش هاي محلي و دقت روش هاي سراسري بهـره مـي بـرد . رابطـة 13 روش محاسبة تعيين ميزان شباهت دو رأس در اين روش را نشان مي دهد.
رابطة 13) ,

كه در آن ,ℎ تعداد مسيرهاي با طول i بين دو رأس است.
ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
Clustering co-efficient
Degree correlation
علاوه بر معيارهاي مذكور، معيارهاي ديگري نيز وجود دارند كه به علت تشابه و نزديكي نتايج آنها با معيارهاي بيان شده، از معرفي آنها خودداري شده است.
روششناسي پژوهش
معيار آداميك ـ آدار ايدة مناسبي براي تعيين ميزان شباهت كاربران شـبكه هـاي اجتمـاعي ارائـهمي دهد و توانسته است پيشگوييهاي خوبي را بهانجام رساند. ايدة موجود در اين معيار اين اسـتكه اگر همساية مشترك دو كاربر دوستان كمتري داشته باشد (درجة كمتر) معلوم است گزيده تـرانتخاب مي كند و احتمال ايجاد ارتباط قوي تري بين دو رأس مورد نظر وجود دارد. لـذا بـه درجـة هر يك از همسايگان مشترك، وزن معكوسي داده است تا چنانچه همساية مشترك داراي درجـ ة بالاتري بود، وجود اين همساية واسطه اثر كمتري بر نتيجة پيشنهادها داشته باشد.
نكتة گفتني در اين روش، اينكه ممكن اسـت رأس مشـتركي كـه دوسـتان زيـادي دارد، دربسياري از اين دوستان با دو سر ارتباط (دو كـاربري كـه در حـال بررسـي ميـزان شـباهت آنهـا هستيم) اشتراك داشته باشد. به بيان ديگر، داشتن دوستان زياد براي يك رأس واسطه يك امتياز منفي محسوب مي شود، اما در صورتي كه اين دوستان، خود دوستان مشترك يكي از دو كـاربريباشند كه قصد پيشنهاد دوست به آنها را داريم، اين تعداد دوستان بايد امتياز مثبت تلقي شود.
در اين بخش، ما يك معيار تعيين شباهت بين جفت رأس هاي گراف شبكه پيشنهاد داده ايـمكه با در نظر گرفتن درجة رأس هاي مياني و نيز دوستان مشترك رأس مياني با دو رأس اصـلي،اين ميزان شباهت را با توجه به معادلة زير بيان مي كند.
(,) +(,)
رابطة 14) |( )Γ|

= (,)−
∈()∩ ( )
كه در آن Cn(u,z) تعداد همسايه هاي مشترك دو رأس u و z است.
رابطة 14 براي تعداد بالاي دوستان مشترك رأس مياني با دو رأس اصلي، امتياز مثبت قائـلمي شود و به همين دليل، مجموع اين تعداد در صورت معادلـه قـرار داده شـده اسـت تـا ميـزانشباهت را افزايش دهد. از سوي ديگر، براي درجة رأس مياني امتياز منفي در نظر گرفتـه شـده ودر مخرج معادله جاي مي گيرد.
در مقايسه هايي كه بين اين روش و روشهاي معرفي شـده صـورت گرفتـه اسـت، مشـاهده ميشود كه اين معيار كارايي قابل قبولي نسبت به روشهاي ديگر دارد كه در ادامه ايـن كـارايياثبات مي شود.
يافته هاي پژوهش
در اين بخش الگوريتم پيشنهادي اين پژوهش با سيزده ويژگي شرح داده شده، مقايسه مي شود و كارايي آن به صـورت تجربـي اثبـات خواهـد شـد. بـراي ايـن كـار، از دو مجموعـه داد ة واقعـي
.استفاده شده است 2Facebook و 1Epinions
مجموعه داده هاي شبكة اجتماعي Epinions كه يك شبكة اجتماعي »چه كسـ ي بـه چـهكسي اعتماد م يكند« بهشمار ميرود، در نظر گرفته شده است و از k 49 كاربر و k 487 يال بين جفت رأس ها تشكيل شده اسـت. مجموعـه دادههـاي Facebook ن يـز كـه در 30 اكتبـر 2009 جمعآوري شده (پاپاديميتريو و همكاران، 2011) شامل k 7/3 كاربر و k 7/13 يال است.
براي ارزيابي و مقايسة روشها و الگوريتم هاي مختلف پيشگويي پيوند با روش پيشنهادي، از معيار MAP3 استفاده شده است، تا در بررسي كارايي الگوريتم مورد نظـر، روي ترتيـب دوسـتانپيشنهاد داده شده با اين روشها، تأكيد بيشتري شود. معادلية MAP (پاپـاديميتريو و همكـاران، 2011) بهصورت رابطة 15 تعريف مي شود.
||
13663933506811رابطة 15) @ | |=
در اين رابطه؛ N: تعداد كاربران در مجموعه دادة آزمايشي؛ : تعداد كاربران مرتبط با كـاربر
u در مجموعة آزمايشي و @ : مقـدارprecision در kامـين موقعيـت فهرسـت پيشنهادها براي u است. توجه كنيد كه MAP در واقع هـر دو مقـدارprecision و recall را در خود دارد و از نظر هندسي، در زير منحني precision-recall جاي دارد.
به منظور ارزيابي روشها، از هر مجموعه آموزشـي بـه صـورتي كـاملاً تصـادفي، 1000 رأس
انتخاب شد و با در نظر گرفتن همة ارتباطات ميان آنها، پس از محاسبه و مقايسة مقادير معيارها، آزمايشهاي لازم روي آنها انجام گرفت. از آنجـايي كـه بـا ايـن انتخـاب همـة رأسهـا ، حتـي رأسهايي كه هنوز دوستي ندارند و به اصطلاح افراد تازه وارد اين شبكة اجتماعي بهشمار ميروند نيز انتخاب مي شوند، اين امكان وجود دارد كه در نتايج همة انواع روش هاي معرفي شده، با دقـتپاييني مواجه شويم؛ چراكه اين نوع رأس ها، با مشكلي به نام آغاز سرد4 برخورد مي كنند كه يـك
ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
http://www.trustlet.org/wiki/
http://delab.csd.auth.gr/~symeon
Mean Average Precision
Cold Start
مشكل رايج در ارائة پيشنهادهاي شبكههاي اجتماعي محسوب مي شود. در اين حالت، اطلاعـاتياز فرد تازه وارد در دست نيست تا بتوان از اين طريق، علايق وي را شناسايي كرد و پيشـنهادهايمناسب را به او ارائه داد. در شبكههاي اجتماعي مشهوري چون Facebook كه از روش »دوست ـ دوست« براي ارائة پيشنهادها استفاده مي كنند، اين مشكل از راه بررسي اسامي موجود در پست الكترونيكي فرد و تطابق آن با اعضاي شبكة اجتماعي و ارائة اسامي تطابق يافته، از بين مـي رود.
در گوگل پلاس نيز براي حل اين مشكل، فرد را وادار ميكنند كه در آغاز ورود به شبكه، ده نفـردوست را انتخاب كرده و معرفي كند.
بـراي تفكيـك داده هـاي آموزشـي و آزمايشـي در هـر دو مـورد از اعتبارسـنجي ضـربدري ده لايه اي1 استفاده شد و الگوريتم ها به كمك زبان نرم افزاري جاوا، بهاجرا گذاشته شـدند . مقايسـهبين الگوريتم هاي مختلف در رابطه با مجموعه داده هاي انتخابي و نتايج آن، در جـدول 1 نشـانداده شده است.
جدول 1. مقادير MAP الگوريتم ها براي مجموعه داده هاي واقعي
Facebook Epinions الگوريتم
0/314 0/527 روش جديد
0/136 0/233 امتياز الحاق تدريجي
0/169 0/484 ضريب جاكارد
0/156 0/484 HDI
0/202 0/463 كاتز
0/251 0/435 دوستان مشترك
0/248 0/475 آداميك ـ آدار
0/122 0/498 HPI
0/260 0/481 FriendLink
0/293 0/199 معيار دوستان
0/190 0/587 ضريب خوشه بندي
0/138 0/098 ضريب درجه
0/034 0/119 مجموع وزن ها
0/034 0/119 ضرب وزن ها

همان طور كه در جدول 1 مشاهده مي شود، روش جديد در رابطه با مجموعه دادة Epinions پس از معيار ضريب خوشه بندي، بهترين جواب را داده است و در مقايسه بـا سـاير معيارهـا بهتـر
ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
1. 10-Fold Cross Validation
عمل كرده است. در مورد Facebook نيز به كمك روش پيشنهادي، در مجموع بهترين پاسخ در رابطه با مجموعه دادة انتخابي به دست آمـده اسـت؛ در حاليكـه در ايـن مجموعـه داده، ضـريبخوشه بندي داراي كارايي بسيار پاييني بوده است. بنابراين همانگونـه كـه در جـدول 1 مشـاهدهمي شود، روش جديد در مورد هر دو مجموعه داده در مقايسه با ساير روشها، پاسخهاي مناسـبو قابل قبولي خواهد داشت و پيش بينيهاي خوبي را ارائه مي دهد. نتيجهگيري يكي از عوامل مهم در تعيين ميزان شباهت بين دو رأس، ميزان درجة رأسهاي رابط بين اين دو رأس است. هر چه ميزان درجة رأس پيونددهنده بين دو رأس كمتر باشد، بدين معناست كه فـردرابط گزيده تر انتخاب مي كند و دوستانش شباهت بيشتري به يكديگر خواهند داشت و در نتيجـه مي تواند رابط خوبي براي ايجاد پيوند بين دو فرد باشد، اما در صـورت ي كـه رأس رابـط بـا وجـوددرجه بالاي ارتباطات، داراي دوستان مشترك زيادي با دو رأس باشـد، ا يـن خاصـيت مـي توانـدبه منزلة يك امتياز مثبت تلقي شده و نقش مهمي در قوي كردن رابطه بين دو رأس ايفا كند.
References
Adamic L. & Adar E. (2005). How to search a social network. Social Networks, 27(3):187–203.
Al Hasan, M., & Zaki, M. J. (2011). A survey of link prediction in social networks. In Social network data analytics (pp. 243-275). Springer US.
Backstrom, L., & Leskovec, J. (2011, February). Supervised random walks: predicting and recommending links in social networks. In Proceedings of the fourth ACM international conference on Web search and data mining (pp. 635-644). ACM.
Cukierski, W., Hamner, B., & Yang, B. (2011, July). Graph-based features for supervised link prediction. In Neural Networks (IJCNN), The 2011 International Joint Conference on (pp. 1237-1244). IEEE.
Feyessa, T., Bikdash, M., & Lebby, G. (2011, October). Node-pair feature extraction for link prediction. In Privacy, security, risk and trust (passat), 2011 IEEE third international conference on and 2011 IEEE third international conference on social computing (socialcom) (pp. 1421-1424). IEEE.
Fire, M., Tenenboim, L., Lesser, O., Puzis, R., Rokach, L., & Elovici, Y. (2011). Link prediction in social networks using computationally efficient topological features. In Privacy, security, risk and trust (passat), 2011 IEEE
third international conference on and 2011 IEEE third international conference on social computing (socialcom) (pp. 73-80). IEEE.
Hasangholipour, T., Amiri, M., Fahim, F. & Ghaderi Abed, A. (2014). Effects of Consumer Characteristics on their Acceptance of Online Shopping: A Survey in Faculty of Management, University of Tehran. Journal of Information Technology Management, 5(4): 67-84. (in Persian)
Irani, M. & Haghighi, M. (2014). The Impact of Social Networks on the Internet Business Sustainability (With Emphasis on the Intermediary Role of Entrepreneurial Purpose of Online Branches of Mellat Bank’s Portal). Journal of Information Technology Management, 5(4): 23-46. (in Persian)
Jeh, G., & Widom, J. (2002, July). SimRank: a measure of structural-context similarity. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 538-543). ACM.
Liben‐Nowell, D., & Kleinberg, J. (2007). The link‐prediction problem for social networks. Journal of the American society for information science and technology, 58(7): 1019-1031.
Papadimitriou, A., Symeonidis, P., & Manolopoulos, Y. (2011). Predicting links in social networks of trust via bounded local path traversal. In Proceedings 3rd Conference on Computational Aspects of Social Networks (CASON’2011), Salamanca, Spain.
Papadimitriou, A., Symeonidis, P., & Manolopoulos, Y. (2011). Friendlink: link prediction in social networks via bounded local path traversal. In Computational Aspects of Social Networks (CASoN), 2011 International Conference on (pp. 66-71). IEEE.
Radfar, R., Nezafati, N. & Yousefi Aasl, S. (2014). Classification of Internet banking customers using data mining algorithms. Journal of Information Technology Management, 6(1): 71-90. (in Persian)
Sajedifar, A., Asfidani, M., Vahdatzad, M. & Mahmoudi Azar, M. (2012). The Effect of Electronic Services Quality on Trust-Building in Online Customers of Tehran’s Brokerage Firms. Journal of Information Technology Management, 4(11): 47-68. (in Persian)
Zhu, Y. X., Lü, L., Zhang, Q. M., & Zhou, T. (2012). Uncovering missing links with cold ends. Physical A: Statistical Mechanics and its Applications, 391(22): .8775-9675



قیمت: تومان


پاسخ دهید