● مقدمه
موتور جست و جوی وب از سه بخش تشکیل می شود :
۱) یک دنبالگرد crawler که صفحات وب را پیدا می کند تا داخل مجموعه صفحات وب آن موتور قرار گیرد،
۲) یک شاخص گذار indexer که شاخص معکوس inverted index ( نیز موسوم به شاخصindex ) را که ساختمان اصلی داده های مورد استفاده ی آن موتور جست وجو است و صفحات وب دنبال گشته crawled را ارائه می کند ،
۳) یک پاسخ دهنده که پرس و جو های کاربر را با استفاده از شاخصها پاسخ می دهد .
در حد مقصود ما بگوییم، دنبالگرد، وب را به مثابه ی یک گراف می نگرد : هر صفحه وب یک گره است و هر ابرپیوند یک کمان است .پرسش اساسی ای که دنبالگرد با آن رودررو است این است که کدام صفحه ها را پیدا کند تا ‹‹ مناسب ترین›› صفحات را در مجموعه ی خود داشت باشد .
برخی مسائلِ باز که ذیلاً عنوان شده است، می تواند دنبالگردها بهبود بخشد.
- درک بهتر از ساختار گراف (بخش ۳ ) ممکن است به راه کارآمدتری برای دنبالگردی در وب منجر شود .
- درک بهتر خصوصیت های مختلف وب (بخش ۲) می تواند مشخص کند کدام جمعیت از صفحه ها در دنبالگردی تا بدینجا کمترارائه شده هستند.
- راه مؤثری برای یافتن میزبانهای دوگان duplicate hosts می تواند به دنبالگرد کمک کند تا از دنبالگردی در دوگانِ میزبانی که قبلاً دنبالگردی کرده است ، پرهیز نماید.
به فرض این که مجموعه ای از پرس وجوها به موتور جست و جو عرضه شده باشد ، مساله ی اصلی این است که کدام پرس وجوها بیشتر بوده است .البته برای کشف تأثیرات موقت ، جستن « تارک داران» top gainers و « تارک بازان» top losers نیز جالب است. این مسأله در بخش ۵ مطرح شده است.
در پایان ، دو مسأله را که در ارتباط با خوشه ای شدنِ موضوع-وابسته ی وب یا یک زیرگراف آن است مطرح می کنیم: بخش ۶ از مسأله ی یافتن زیر گرافهای دوبخشی جهت دار چگال بحث می کند. بخش ۷ پرسش چگونگی اشتقاق بردارهای ویژه ی ماتریسهای مختلف را از گراف وب عرضه می دارد. ما هر یک از این مسائلِ باز را ترسیم کرده ، ارجاعاتی نیز به کارهای پیشین در این زمینه می دهیم .
● نمونه گیری صفحات وب
درک وب و خصوصیت های آن ، از آغاز وب ، یک موضوع مهم تحقیقاتی است .چند صفحه در وب وجود دارد؟چند تا از آنها توسط موتور جست و جویی شاخص گذاری شده است؟ چند صفحه به یک زبان خاص یا در یک حوزه ی معین وجود دارد ؟ متوسط اندازه ی یک صفحه ی وب چقدر است ؟ چه درصدی از صحات وب صفحه ی اصلی هستند ؟ و این خصوصیت ها در زمان چگونه تغییر می کند ؟ موتور های جست وجو می کوشند تا آنجا که ممکن باشد، اطلاعات وب را ثبت کنند .به علاوه نسبت انواع مختلف صفحه ها ،نظیر صفحه های به زبانهای مختلف باید تقریباً متناسب با انواع موجود در وب باشد .
رد گیری این خصوصیات در دنبالگردی بدیهی است . بنابر این اگر این آمار برای وب معلوم باشد ، دنبالگرد می تواند تعیین کند که چه انواعی از صفحات وب تا بدینجا خیلی کمتر ارائه شده هستندو بکوشد بیشتر از آنها دنبالگردی کند.
برا ی نمونه گیری یکنواخت صفحات وب می شد از یک فن استفاده کرد ، تا همه ی چنین سؤالاتی را به جز سؤال نخست پاسخ داد . متأسفانه چنین فنی شناخته نشده است اگرچه تحقیقات دامنه داری در این خصوص صورت گرفته است .لارنس و جایلز[Lawrence and Giles ۹۹ ] از رهیافتهای مبتنی بر آزمون تصادفی نشانی های IP بهره گرفتند : آنها یک نشانی تصادفی IP را انتخاب کردند و بررسی کردند که آیا آن میزبان host یک وبگاه است یا نه . در صورت بودن ،آنها می کوشند صفحه های وب دسترس پذیر این وبگاه را نمونه گیری کنند . البته اگر از صفحات وب یک وبگاه فهرست جامعی نداشته باشیم این که چگونه از این صفحه های وب نمونه گیری کنیم ، همچنان یک مسأله ی باز باقی خواهد ماند. هنتسینگر و همکارانش [Henzinger et al. ۰۰] تشکیل یک راه تصادفی خاص را بر گراف (جهت دار ) وب و آنگاه نمونه گیری ازصفحات عبور شده را به طور معکوس متناسب با توزیع ثابت راه تصادفی مطرح نمودند.این رهیافت مشکلاتی چند دارد. یک مسأله این که، واضح نیست که چند مرحله باید انجام داد تا توزیع متوازن راتقریب زد. مسأله ی دیگر این که ، راه تصادفی خاصی را که ایشان مطرح می کننند، نمی توان مستقیماً پیاده سازی کرد ، بلکه این مسأله را می توان با استفاده از یک راه تصادفی دیگر غیر از آنچه ایشان در مقاله ی خود عرضه کرده اند حل کرد [Henzinger et al. ۰۰] .
بریوسف و همکارانش [Bar-yossef st al.۰۰]گراف وب را به یک گراف غیر جهت دار همبند و منظم تبدیل کردند. توازن یک راه تصادفی بر این گراف ، توزیع یکنواخت است . باز اینجا نیز واضح نیست که چند مرحله برای این راه لازم است .البته مسأله ی مهمتر این است که روش قابل اعتمادی برای تبدیل گراف وب به یک گراف غیر جهت دار در دست نیست . بریوسف و همکارانش درخواست یالهای داخلی یک صفحه معین را از موتورهای جست وجوی مختلف به منظور نمونه گیری همه ی یالهای مجاور یک صفحه ی معین مطرح نمودند. البته اغلب فقط یک زیر مجموعه از همه ی یالهای داخلی را بدین طریق می توان پیدا کرد .
عاقبت ، راسمه ویچین تونگ و همکاران [Rusmevichientong et al.] رهیافت هنتسینگر [Henzinger et al.] را اصلاح کردند تا روشی به دست آید که درآن تا حدی نمونه گیری یکنواخت حاصل شود.در عمل برآن باوریم که رهیافت ایشان خوب کار نمی کند،چرا که کثرتی از میزبانها در وب هستند که از درون این میزبان پیوند خورده اند ، اما اندکی از پیوندها این میزبان را رها می کنند.اگر راه تصادفی در [Rusmevichientong et al. ۰۱] به چنین میزبانی برخوردکند، شانس زیادی دارد که بخش عظیمی از گره ها از همین میزبان باشند، یعنی این که این نمونه نایکنواخت خواهد بود .
● مدل سازی گراف وب
به محض این که پژوهشگران وب مشاهده ی خصوصیت های گراف وب را آغاز کردند ، کوشیدند تا مدلی از گراف وب بسازند ( [Kleinberg et al. ۹۹] را بنگرید).به نظر می رسد راههای تصادفی بر گراف وب سریعاً همگرا شوند.به علاوه وقتی به پیوند های بین وبگاهها می نگریم ، این پیوندهاکاملاً تصادفی به نظر می رسد .بنا براین کوشش برای مدل سازی وب به عنوان گراف تصادفی مرحله ای بدیهی بوده است. این امر به مدلِ گراف روگرفتِ copy graph کلاین برگ و همکاران [Kleinberg et al. ۹] و همه ی اصلاحیات آن منجر شد[Kumar et al. ۰۰, Pandurangan et al. ۰۲]
آن دسته از خصوصیات گراف وب که این مدلها می کوشند ثبت نمایند،توزیع درجه ی ورودی توانی است ، این واقعیت که عداد بزرگی از گروهک های کوچک و توزیع توانی صفحه-رتبه ای داریم .البته خاصیت خیلی مهمی از گراف وب هست که با هیچ یک از این گرافهای پیشین مدل نمی شود، یعنی این واقعیت که وب بیشتر یک ساختار دو سطحی است : هر صفحه ی وب متعلق به یک میزبان است و حدود ۷۵% این ابر پیوندها صفحه های همان یک میزبان را به هم پیوند می زنند[bharat et al. ۰۱] . یالهای بین گره های موجود در یک میزبان ساختار معتنابهی دارند : مثلاً هر صفحه روی یک میزبان می تواند به همان صورت انحصاری copyright form یا صفحه ی اصلی میزبان اشاره کند. حسب آخرین معلومات ، تا کنون مدلی ارائه نشده است که این ساختار دوسطحی را به اضافه ی سایر خصوصیات فهرست شده ی فوق ، مدل سازی کند. از این گذشته گراف میزبانی را که از طریق ادغام همه ی گره های آن میزبان به یک گره ایجاد شده است در نظر بگیرید . گراف حاصل نیز یک توزیع توانی ، با درجه ی ورودی و درجه ی خروجی دارد [Bhrat et al. ۰۱] . ضمناً هیچ مدل گراف تصادفی نیست که توزیع های توانی صفحات را و سطح میزبان را مدل سازی کند.
خلاصه اینکه ،مسأله ی باز ،ایجاد یک مدل گراف تصادفی است که رفتار گراف وب را بر صفحه ها و هم بر سطح میزبان مدل سازی کند.
● میزبانهای دوگان
موتورهای جست و جوی وب می کوشند تا از داشتن صفحه های دوگان و تقریباً دوگان در مجموعه خود پرهز نمایند، چراکه این صفحه ها زمانی را که می باید صرف افزودن محتوای مفید به آن مجموعه شود، می افزایند . به اضافه صفحه های دوگان و تقریباً دوگان در مجموعه ای ازصفحات دنبال گشته به خوبی مطالعه شده است [Brin et al. ۹۵ Broder ۹۷] . ضمناً تحقیقاتی نیز در زمینه ی تعیین فهرست های درختی دوگان موسوم به آینه ها mirrors صورت گرفته است [Bharat and Broder ۹,Cho et al. ۰۰] . در حالی که یافتنِ آینه mirror detection و یافتن تک صفحه individual-page detection می کوشند حل کاملی از مسأله ی صفحه های دوگان ارائه کنند ، یک گونه ی ساده تر می تواند در حین اینکه به منابع محاسباتی کمتری نیاز داشته باشد ، سود بیشتری حاصل کند. این مسأله ی ساده تر یافتن میزبان دوگان duplicate host detection نام دارد : یافتن دو میزبان که صفحه به صحه یکسان باشند . میزبانهای دوگان ( دومیزبانها duphosts ) بزرگترین منبع منفرد صفحه های دوگان بر روی وب هستند، پس حل مسأله ی میزبانهای دوگان به بهبود مهمی می رسد .
مسأله ی یافتن میزبانهای دوگان آسانتر از یافتن آینه است ، زیرا URL های بین دومیزبانها تنها در اجزاء نام میزبان تفاوت دارند.مضافاً ، صفحه های روی میزبانها دقیقاً یکسان هستند بدین معنی که این الگوریم نیاز به صورت بندی مجدد reformatting ندارد.بالاخره اینکه، مجموعه ی صفحه های روی میزبان نخست ، با مجموعه ی صفحه های روی میزبان دوم یکسان است . نخستین مجموعه ی رهیافتهای مسأله ی دومیزبانها توسط بهارا و همکارانش [Bharat et al. ۰۰] مورد مطالعه قرار گرفت ، اما میزان خطای الگوریتم آنها را احتمالاً می توان ( هم برا ی خطای اضافی و هم برای خطای نقصانی) کاهش داد .البته رهیافت کلی ایشان ارزشمند به نظر می رسد: هر میزبان را توسط یک ترسیم sketch ارائه کنید . مثلاً ترسیم می تواند درواقع زیر مجموعه ای از URL های روی میزبان یا ابر پیوندهای اشاره کننده به صفحه های روی میزبان باشد . آنگاه برای مقایسه ی میزبانها از این ترسیم بهره بگیرید . البته پرسشهای سخت چنین اند : چه ترسیمی را برگزینیم و چگونه از مقایسه ی همه ی جفت های میزبان دوری گزینیم؟ چون میلیونه میزبان متفاوت وجود دارند ، واضح است که مقایسه ی همه ی این جفت ها امکان پذیر نیست . ترسیمهای بهارات و همکارانش [Bharat et al.۰۰] صرفاً بر رشته ها ی URL ها و ساختمان ابر پیوند مبتنی است .
● جریانهای داده ها
ثبت پرس و جو های یک موتور جست وجو همه ی پرس وجوهای ارائه شده به آن موتور جست و جو را شامل است . جست و جوهای بسیاری به کندی در طی زمان تغییر می کنند . البته بیشترین افزایش یا کاهش جست و جوها از یک بازه ی زمانی تا بازه ی زمانی دیگر ، گرایش ها و سو گیری علایق کاربران را می نمایاند. ما اینها را تارک دار ها top gainers و تارک بازها top losers می نامیم . به دلیل اینکه تعداد پرس و جو ها بسیار زیاد است ، تارک دارها و تارک باز ها را باید با ایجاد یک گذر pass از ثبت های پرس و جو ها query logs محاسبه نمود .این امر به مسأله ی زیر در خصوص جریان داده ها منجر می شود : اگر دودنباله از اشیاء داده شده باشند ،آن اقلامی را بیابید که قدرمطلق آن وقتی که یک دنباله را با دیگری فقط در یک بار خواندن مقایسه می کنید، از بقیه بیشتر کاهش یا افزایش دارد . چاریکار و همکارانش [Charicar et al. ۰۲] یک الگوریتمِ ۲-گذر ۲-pass برای این مسأله ارائه داده ا ند. مسأله ی جالب دیگر این است که برای همه ی اقلام فوق یک بسامد frequency خاصی بیابیم که افزایش نسبی آن( یعنی :افزایش آنها بخش بر بسامد آنها در دنباله ی نخست ) بیشترین مقدار باشد.
● زیرگرافهای دوبخشی چگال
وب چنانکه کومار [Kumar et al.۹۹]نشان داده است ، بسیاری از زیرگرافهای دوبخشی جهت دار همبند چگال را شامل است ، چراکه اجتماعات سایبر cyber-communities اغلب چنین ساختار همبندی دارند.گره های مبدأ soure nodes در چنین زیرگرافی ،« هاب »ها hubs یا گره های هادی ِ directory nodes موضوع هستند .همچنین کومار و همکارانش الگوریتمی برای یافتن زیرگرافهای دوبخشی کامل کوچک که آن را هسته core نامید اند ، ارائه و پیاده سازی کرده اند . ایشان از یک رهیافت پایین به بالا (بالارو) استفاده کرده اند که از این واقعیت که هر هسته ی (i,i) ترکیبی از هسته های (i-۱,i-۱) است بهره می گیرد .البته هسته های ایشان نظر به دهها گره نسبتاً کوچک بودند.
به منظور ثب کامل این اجتماعات سایبر یافتن زیرگرافهای دوبخشی خیلی بزرگتر در میان صدها یا هزارها گره جالب خواهد بود. نیازی به تکمیل اینها نیست ،لکن باید چگال dence باشند، بدین معنی که باید دست کم بخش ثابتی از زیرگرافهای دوبخشی ِ کاملِ مرتبط را شامل شوند. آیا الگوریتمهای کارآمدی برای یافتن آنها وجود دارد ؟ و آیا این الگوریتمها را می توان به نحو کارآمدی پیاده سازی کرد اگر که فقط بخش کوچکی از این گراف در حافظه ی اصلی بگنجد؟
● افراز بردار ویژه ای ِ گرافهای جهت دار
داناث و هافمن [ Donath and Hoffman ۷۳] بهره گیری از بردارهای ویژه را به منظور افراز گراف غیر جهت دار به روشی متوازن balanced ارائه نمودند.از آن زمان کار زیادی در زمینه ی رهیافتهای طیفی spectral برای افراز گراف صورت گرفته است. برای ملاحظه ای عالی در این زمینه چونگ را بنگرید [chung] .شای و ملک [Shi and Malik ۰۰] نشان دادند که بردارهای ویژه ی ماتریسهای مختلفِ بنا شده بر ماتریس مجاورت ِ یک گراف ، به انواع مختلفی از برشهای متوازن در گراف مربوط است . فرض کنید W ماتریس مجاورت ِگرافِ غیر جهت دار ِ (V,E) با گره های ۱,۲,.. , n باشد و فرض کنید D یک ماتریس قطری باشد که برای آن di = deg(i) . فرض نمائید A و B مجموعه هایی از گره ها و E(A,B) مجموعه ی یالهای (a,b) باشد که .
▪ وابستگیِ متوسطِ average association یک مجموعه ی ِ A ، است.
▪ برش متوسط average cut یک مجموعه ی ِ A ، است.
▪ برش نرمال average cut یک مجموعه ی ِ A ، است.
شای و ملک نشان دادند که : دومین بردار ویژه ی بزرگ ِ W به مجموعه ای مربوط است که وابستگی متوسط average association را بیشینه می کند.دومین بردار ویژه ی کوچک W – D به مجموعه ای مربوط است که برش متوسط average cut را کمینه می کند، و دومین بردار ویژه ی کوچک مسأله ی تعمیم یافته ی بردار ویژه ، یعنی : تقریبی از کوچکترین برش نرمال به دست می دهد . این نتیجه ها برای گراف غیر جهت دار برقرارند ، اما گراف وب گرافی جهت دار است . بنابر این ، درک چگونگی ارتباط نتایج فوق برای گراف گرافهای جهت دار جالب خواهد بود . اینکه آیا بردارهای ویژه ی ماتریسهای نظیر از گرافهای جهت دار نیز با تجزیه های متوازن گراف جهت دار مرتبطند، ممکن است که این امر به یک زیرگراف خاص-موضوعِ topic-specific آن آن منجر شود. یکی از نخستین گامها را در این جهت گیبسُن و همکارانش [Gibson et al ۹۸] برداشتند.آنها از بردار ویژه ی ماتریس و ماتریس که A ماتریس مجاورت یک زیرگراف خاص-موضوع ِ آن است ،و برای تجزیه ی زیرگرافهای خاص-موضوع بهره گرفتند. ایشان حکایت گونه نشان دادند که بردار ویژه ی اصلی principal و چند بردار ویژه ی غیر اصلی فوقانی top ، گرافهای موضوعی را به چند اجتماعِ ابرپیوندشده hyperlinked communities یعنی خوشه های clusters صفحه های همان زیرموضوع subtopic تجزیه می کنند.
موتور جست و جوی وب از سه بخش تشکیل می شود :
۱) یک دنبالگرد crawler که صفحات وب را پیدا می کند تا داخل مجموعه صفحات وب آن موتور قرار گیرد،
۲) یک شاخص گذار indexer که شاخص معکوس inverted index ( نیز موسوم به شاخصindex ) را که ساختمان اصلی داده های مورد استفاده ی آن موتور جست وجو است و صفحات وب دنبال گشته crawled را ارائه می کند ،
۳) یک پاسخ دهنده که پرس و جو های کاربر را با استفاده از شاخصها پاسخ می دهد .
در حد مقصود ما بگوییم، دنبالگرد، وب را به مثابه ی یک گراف می نگرد : هر صفحه وب یک گره است و هر ابرپیوند یک کمان است .پرسش اساسی ای که دنبالگرد با آن رودررو است این است که کدام صفحه ها را پیدا کند تا ‹‹ مناسب ترین›› صفحات را در مجموعه ی خود داشت باشد .
برخی مسائلِ باز که ذیلاً عنوان شده است، می تواند دنبالگردها بهبود بخشد.
- درک بهتر از ساختار گراف (بخش ۳ ) ممکن است به راه کارآمدتری برای دنبالگردی در وب منجر شود .
- درک بهتر خصوصیت های مختلف وب (بخش ۲) می تواند مشخص کند کدام جمعیت از صفحه ها در دنبالگردی تا بدینجا کمترارائه شده هستند.
- راه مؤثری برای یافتن میزبانهای دوگان duplicate hosts می تواند به دنبالگرد کمک کند تا از دنبالگردی در دوگانِ میزبانی که قبلاً دنبالگردی کرده است ، پرهیز نماید.
به فرض این که مجموعه ای از پرس وجوها به موتور جست و جو عرضه شده باشد ، مساله ی اصلی این است که کدام پرس وجوها بیشتر بوده است .البته برای کشف تأثیرات موقت ، جستن « تارک داران» top gainers و « تارک بازان» top losers نیز جالب است. این مسأله در بخش ۵ مطرح شده است.
در پایان ، دو مسأله را که در ارتباط با خوشه ای شدنِ موضوع-وابسته ی وب یا یک زیرگراف آن است مطرح می کنیم: بخش ۶ از مسأله ی یافتن زیر گرافهای دوبخشی جهت دار چگال بحث می کند. بخش ۷ پرسش چگونگی اشتقاق بردارهای ویژه ی ماتریسهای مختلف را از گراف وب عرضه می دارد. ما هر یک از این مسائلِ باز را ترسیم کرده ، ارجاعاتی نیز به کارهای پیشین در این زمینه می دهیم .
● نمونه گیری صفحات وب
درک وب و خصوصیت های آن ، از آغاز وب ، یک موضوع مهم تحقیقاتی است .چند صفحه در وب وجود دارد؟چند تا از آنها توسط موتور جست و جویی شاخص گذاری شده است؟ چند صفحه به یک زبان خاص یا در یک حوزه ی معین وجود دارد ؟ متوسط اندازه ی یک صفحه ی وب چقدر است ؟ چه درصدی از صحات وب صفحه ی اصلی هستند ؟ و این خصوصیت ها در زمان چگونه تغییر می کند ؟ موتور های جست وجو می کوشند تا آنجا که ممکن باشد، اطلاعات وب را ثبت کنند .به علاوه نسبت انواع مختلف صفحه ها ،نظیر صفحه های به زبانهای مختلف باید تقریباً متناسب با انواع موجود در وب باشد .
رد گیری این خصوصیات در دنبالگردی بدیهی است . بنابر این اگر این آمار برای وب معلوم باشد ، دنبالگرد می تواند تعیین کند که چه انواعی از صفحات وب تا بدینجا خیلی کمتر ارائه شده هستندو بکوشد بیشتر از آنها دنبالگردی کند.
برا ی نمونه گیری یکنواخت صفحات وب می شد از یک فن استفاده کرد ، تا همه ی چنین سؤالاتی را به جز سؤال نخست پاسخ داد . متأسفانه چنین فنی شناخته نشده است اگرچه تحقیقات دامنه داری در این خصوص صورت گرفته است .لارنس و جایلز[Lawrence and Giles ۹۹ ] از رهیافتهای مبتنی بر آزمون تصادفی نشانی های IP بهره گرفتند : آنها یک نشانی تصادفی IP را انتخاب کردند و بررسی کردند که آیا آن میزبان host یک وبگاه است یا نه . در صورت بودن ،آنها می کوشند صفحه های وب دسترس پذیر این وبگاه را نمونه گیری کنند . البته اگر از صفحات وب یک وبگاه فهرست جامعی نداشته باشیم این که چگونه از این صفحه های وب نمونه گیری کنیم ، همچنان یک مسأله ی باز باقی خواهد ماند. هنتسینگر و همکارانش [Henzinger et al. ۰۰] تشکیل یک راه تصادفی خاص را بر گراف (جهت دار ) وب و آنگاه نمونه گیری ازصفحات عبور شده را به طور معکوس متناسب با توزیع ثابت راه تصادفی مطرح نمودند.این رهیافت مشکلاتی چند دارد. یک مسأله این که، واضح نیست که چند مرحله باید انجام داد تا توزیع متوازن راتقریب زد. مسأله ی دیگر این که ، راه تصادفی خاصی را که ایشان مطرح می کننند، نمی توان مستقیماً پیاده سازی کرد ، بلکه این مسأله را می توان با استفاده از یک راه تصادفی دیگر غیر از آنچه ایشان در مقاله ی خود عرضه کرده اند حل کرد [Henzinger et al. ۰۰] .
بریوسف و همکارانش [Bar-yossef st al.۰۰]گراف وب را به یک گراف غیر جهت دار همبند و منظم تبدیل کردند. توازن یک راه تصادفی بر این گراف ، توزیع یکنواخت است . باز اینجا نیز واضح نیست که چند مرحله برای این راه لازم است .البته مسأله ی مهمتر این است که روش قابل اعتمادی برای تبدیل گراف وب به یک گراف غیر جهت دار در دست نیست . بریوسف و همکارانش درخواست یالهای داخلی یک صفحه معین را از موتورهای جست وجوی مختلف به منظور نمونه گیری همه ی یالهای مجاور یک صفحه ی معین مطرح نمودند. البته اغلب فقط یک زیر مجموعه از همه ی یالهای داخلی را بدین طریق می توان پیدا کرد .
عاقبت ، راسمه ویچین تونگ و همکاران [Rusmevichientong et al.] رهیافت هنتسینگر [Henzinger et al.] را اصلاح کردند تا روشی به دست آید که درآن تا حدی نمونه گیری یکنواخت حاصل شود.در عمل برآن باوریم که رهیافت ایشان خوب کار نمی کند،چرا که کثرتی از میزبانها در وب هستند که از درون این میزبان پیوند خورده اند ، اما اندکی از پیوندها این میزبان را رها می کنند.اگر راه تصادفی در [Rusmevichientong et al. ۰۱] به چنین میزبانی برخوردکند، شانس زیادی دارد که بخش عظیمی از گره ها از همین میزبان باشند، یعنی این که این نمونه نایکنواخت خواهد بود .
● مدل سازی گراف وب
به محض این که پژوهشگران وب مشاهده ی خصوصیت های گراف وب را آغاز کردند ، کوشیدند تا مدلی از گراف وب بسازند ( [Kleinberg et al. ۹۹] را بنگرید).به نظر می رسد راههای تصادفی بر گراف وب سریعاً همگرا شوند.به علاوه وقتی به پیوند های بین وبگاهها می نگریم ، این پیوندهاکاملاً تصادفی به نظر می رسد .بنا براین کوشش برای مدل سازی وب به عنوان گراف تصادفی مرحله ای بدیهی بوده است. این امر به مدلِ گراف روگرفتِ copy graph کلاین برگ و همکاران [Kleinberg et al. ۹] و همه ی اصلاحیات آن منجر شد[Kumar et al. ۰۰, Pandurangan et al. ۰۲]
آن دسته از خصوصیات گراف وب که این مدلها می کوشند ثبت نمایند،توزیع درجه ی ورودی توانی است ، این واقعیت که عداد بزرگی از گروهک های کوچک و توزیع توانی صفحه-رتبه ای داریم .البته خاصیت خیلی مهمی از گراف وب هست که با هیچ یک از این گرافهای پیشین مدل نمی شود، یعنی این واقعیت که وب بیشتر یک ساختار دو سطحی است : هر صفحه ی وب متعلق به یک میزبان است و حدود ۷۵% این ابر پیوندها صفحه های همان یک میزبان را به هم پیوند می زنند[bharat et al. ۰۱] . یالهای بین گره های موجود در یک میزبان ساختار معتنابهی دارند : مثلاً هر صفحه روی یک میزبان می تواند به همان صورت انحصاری copyright form یا صفحه ی اصلی میزبان اشاره کند. حسب آخرین معلومات ، تا کنون مدلی ارائه نشده است که این ساختار دوسطحی را به اضافه ی سایر خصوصیات فهرست شده ی فوق ، مدل سازی کند. از این گذشته گراف میزبانی را که از طریق ادغام همه ی گره های آن میزبان به یک گره ایجاد شده است در نظر بگیرید . گراف حاصل نیز یک توزیع توانی ، با درجه ی ورودی و درجه ی خروجی دارد [Bhrat et al. ۰۱] . ضمناً هیچ مدل گراف تصادفی نیست که توزیع های توانی صفحات را و سطح میزبان را مدل سازی کند.
خلاصه اینکه ،مسأله ی باز ،ایجاد یک مدل گراف تصادفی است که رفتار گراف وب را بر صفحه ها و هم بر سطح میزبان مدل سازی کند.
● میزبانهای دوگان
موتورهای جست و جوی وب می کوشند تا از داشتن صفحه های دوگان و تقریباً دوگان در مجموعه خود پرهز نمایند، چراکه این صفحه ها زمانی را که می باید صرف افزودن محتوای مفید به آن مجموعه شود، می افزایند . به اضافه صفحه های دوگان و تقریباً دوگان در مجموعه ای ازصفحات دنبال گشته به خوبی مطالعه شده است [Brin et al. ۹۵ Broder ۹۷] . ضمناً تحقیقاتی نیز در زمینه ی تعیین فهرست های درختی دوگان موسوم به آینه ها mirrors صورت گرفته است [Bharat and Broder ۹,Cho et al. ۰۰] . در حالی که یافتنِ آینه mirror detection و یافتن تک صفحه individual-page detection می کوشند حل کاملی از مسأله ی صفحه های دوگان ارائه کنند ، یک گونه ی ساده تر می تواند در حین اینکه به منابع محاسباتی کمتری نیاز داشته باشد ، سود بیشتری حاصل کند. این مسأله ی ساده تر یافتن میزبان دوگان duplicate host detection نام دارد : یافتن دو میزبان که صفحه به صحه یکسان باشند . میزبانهای دوگان ( دومیزبانها duphosts ) بزرگترین منبع منفرد صفحه های دوگان بر روی وب هستند، پس حل مسأله ی میزبانهای دوگان به بهبود مهمی می رسد .
مسأله ی یافتن میزبانهای دوگان آسانتر از یافتن آینه است ، زیرا URL های بین دومیزبانها تنها در اجزاء نام میزبان تفاوت دارند.مضافاً ، صفحه های روی میزبانها دقیقاً یکسان هستند بدین معنی که این الگوریم نیاز به صورت بندی مجدد reformatting ندارد.بالاخره اینکه، مجموعه ی صفحه های روی میزبان نخست ، با مجموعه ی صفحه های روی میزبان دوم یکسان است . نخستین مجموعه ی رهیافتهای مسأله ی دومیزبانها توسط بهارا و همکارانش [Bharat et al. ۰۰] مورد مطالعه قرار گرفت ، اما میزان خطای الگوریتم آنها را احتمالاً می توان ( هم برا ی خطای اضافی و هم برای خطای نقصانی) کاهش داد .البته رهیافت کلی ایشان ارزشمند به نظر می رسد: هر میزبان را توسط یک ترسیم sketch ارائه کنید . مثلاً ترسیم می تواند درواقع زیر مجموعه ای از URL های روی میزبان یا ابر پیوندهای اشاره کننده به صفحه های روی میزبان باشد . آنگاه برای مقایسه ی میزبانها از این ترسیم بهره بگیرید . البته پرسشهای سخت چنین اند : چه ترسیمی را برگزینیم و چگونه از مقایسه ی همه ی جفت های میزبان دوری گزینیم؟ چون میلیونه میزبان متفاوت وجود دارند ، واضح است که مقایسه ی همه ی این جفت ها امکان پذیر نیست . ترسیمهای بهارات و همکارانش [Bharat et al.۰۰] صرفاً بر رشته ها ی URL ها و ساختمان ابر پیوند مبتنی است .
● جریانهای داده ها
ثبت پرس و جو های یک موتور جست وجو همه ی پرس وجوهای ارائه شده به آن موتور جست و جو را شامل است . جست و جوهای بسیاری به کندی در طی زمان تغییر می کنند . البته بیشترین افزایش یا کاهش جست و جوها از یک بازه ی زمانی تا بازه ی زمانی دیگر ، گرایش ها و سو گیری علایق کاربران را می نمایاند. ما اینها را تارک دار ها top gainers و تارک بازها top losers می نامیم . به دلیل اینکه تعداد پرس و جو ها بسیار زیاد است ، تارک دارها و تارک باز ها را باید با ایجاد یک گذر pass از ثبت های پرس و جو ها query logs محاسبه نمود .این امر به مسأله ی زیر در خصوص جریان داده ها منجر می شود : اگر دودنباله از اشیاء داده شده باشند ،آن اقلامی را بیابید که قدرمطلق آن وقتی که یک دنباله را با دیگری فقط در یک بار خواندن مقایسه می کنید، از بقیه بیشتر کاهش یا افزایش دارد . چاریکار و همکارانش [Charicar et al. ۰۲] یک الگوریتمِ ۲-گذر ۲-pass برای این مسأله ارائه داده ا ند. مسأله ی جالب دیگر این است که برای همه ی اقلام فوق یک بسامد frequency خاصی بیابیم که افزایش نسبی آن( یعنی :افزایش آنها بخش بر بسامد آنها در دنباله ی نخست ) بیشترین مقدار باشد.
● زیرگرافهای دوبخشی چگال
وب چنانکه کومار [Kumar et al.۹۹]نشان داده است ، بسیاری از زیرگرافهای دوبخشی جهت دار همبند چگال را شامل است ، چراکه اجتماعات سایبر cyber-communities اغلب چنین ساختار همبندی دارند.گره های مبدأ soure nodes در چنین زیرگرافی ،« هاب »ها hubs یا گره های هادی ِ directory nodes موضوع هستند .همچنین کومار و همکارانش الگوریتمی برای یافتن زیرگرافهای دوبخشی کامل کوچک که آن را هسته core نامید اند ، ارائه و پیاده سازی کرده اند . ایشان از یک رهیافت پایین به بالا (بالارو) استفاده کرده اند که از این واقعیت که هر هسته ی (i,i) ترکیبی از هسته های (i-۱,i-۱) است بهره می گیرد .البته هسته های ایشان نظر به دهها گره نسبتاً کوچک بودند.
به منظور ثب کامل این اجتماعات سایبر یافتن زیرگرافهای دوبخشی خیلی بزرگتر در میان صدها یا هزارها گره جالب خواهد بود. نیازی به تکمیل اینها نیست ،لکن باید چگال dence باشند، بدین معنی که باید دست کم بخش ثابتی از زیرگرافهای دوبخشی ِ کاملِ مرتبط را شامل شوند. آیا الگوریتمهای کارآمدی برای یافتن آنها وجود دارد ؟ و آیا این الگوریتمها را می توان به نحو کارآمدی پیاده سازی کرد اگر که فقط بخش کوچکی از این گراف در حافظه ی اصلی بگنجد؟
● افراز بردار ویژه ای ِ گرافهای جهت دار
داناث و هافمن [ Donath and Hoffman ۷۳] بهره گیری از بردارهای ویژه را به منظور افراز گراف غیر جهت دار به روشی متوازن balanced ارائه نمودند.از آن زمان کار زیادی در زمینه ی رهیافتهای طیفی spectral برای افراز گراف صورت گرفته است. برای ملاحظه ای عالی در این زمینه چونگ را بنگرید [chung] .شای و ملک [Shi and Malik ۰۰] نشان دادند که بردارهای ویژه ی ماتریسهای مختلفِ بنا شده بر ماتریس مجاورت ِ یک گراف ، به انواع مختلفی از برشهای متوازن در گراف مربوط است . فرض کنید W ماتریس مجاورت ِگرافِ غیر جهت دار ِ (V,E) با گره های ۱,۲,.. , n باشد و فرض کنید D یک ماتریس قطری باشد که برای آن di = deg(i) . فرض نمائید A و B مجموعه هایی از گره ها و E(A,B) مجموعه ی یالهای (a,b) باشد که .
▪ وابستگیِ متوسطِ average association یک مجموعه ی ِ A ، است.
▪ برش متوسط average cut یک مجموعه ی ِ A ، است.
▪ برش نرمال average cut یک مجموعه ی ِ A ، است.
شای و ملک نشان دادند که : دومین بردار ویژه ی بزرگ ِ W به مجموعه ای مربوط است که وابستگی متوسط average association را بیشینه می کند.دومین بردار ویژه ی کوچک W – D به مجموعه ای مربوط است که برش متوسط average cut را کمینه می کند، و دومین بردار ویژه ی کوچک مسأله ی تعمیم یافته ی بردار ویژه ، یعنی : تقریبی از کوچکترین برش نرمال به دست می دهد . این نتیجه ها برای گراف غیر جهت دار برقرارند ، اما گراف وب گرافی جهت دار است . بنابر این ، درک چگونگی ارتباط نتایج فوق برای گراف گرافهای جهت دار جالب خواهد بود . اینکه آیا بردارهای ویژه ی ماتریسهای نظیر از گرافهای جهت دار نیز با تجزیه های متوازن گراف جهت دار مرتبطند، ممکن است که این امر به یک زیرگراف خاص-موضوعِ topic-specific آن آن منجر شود. یکی از نخستین گامها را در این جهت گیبسُن و همکارانش [Gibson et al ۹۸] برداشتند.آنها از بردار ویژه ی ماتریس و ماتریس که A ماتریس مجاورت یک زیرگراف خاص-موضوع ِ آن است ،و برای تجزیه ی زیرگرافهای خاص-موضوع بهره گرفتند. ایشان حکایت گونه نشان دادند که بردار ویژه ی اصلی principal و چند بردار ویژه ی غیر اصلی فوقانی top ، گرافهای موضوعی را به چند اجتماعِ ابرپیوندشده hyperlinked communities یعنی خوشه های clusters صفحه های همان زیرموضوع subtopic تجزیه می کنند.
هیچ نظری موجود نیست:
ارسال یک نظر