¸½¼Â¤ËŬÍѤ¹¤ëºÝ¤ÎÌäÂê
PageRank ¤Î´ðËÜŪ¤Ê¹Í¤¨Êý¼«ÂÎ¤ÏÆñ¤·¤¤¤â¤Î¤Ç¤Ï¤Ê¤¤¡£¼ÂÍÑŪ¤Ê¸ú²Ì¤¬ÀäÂç¤Ê³ä¤Ë¤ÏÊ£»¨²ø´ñ¤Ê¥¢¥ë¥´¥ê¥º¥à¤Ç¤â¤Ê¤ó¤Ç¤â¤Ê¤¯¡¢´Êñ¤ÊÀþ·ÁÊÑ´¹¤ò¹Ô¤¦¤À¤±¤Ç¤¢¤ê¡¢¤à¤·¤í´ÊÌÀ¤Çľ´¶Åª¤ËÍý²ò¤·¤ä¤¹¤¤ÉôÎà¤Ë°¤¹¤ë¤À¤í¤¦¡£ ¤À¤¬¡¢¼ÂºÝ¤Î Web ¥Ï¥¤¥Ñ¡¼¥ê¥ó¥¯¹½Â¤¤ò»È¤Ã¤Æ PageRank ¤ò·×»»¤¹¤ë¤È¤Ê¤ë¤È¡¢¤µ¤¹¤¬¤Ë¸ý¤Ç¸À¤¦¤Û¤É¤Ë¤Ï°×¤·¤¤¤â¤Î¤Ç¤Ï¤Ê¤¤¡£¤½¤Îº¤Æñ¤Ï¼ç¤ËÆó¤Ä¤¢¤ë¡£°ì¤Ä¤Ë¤Ï¡¢½ã¿è¤Ë²¾ÁÛŪ¤Ê¿ôÃÍ¥â¥Ç¥ë¤È¸½¼ÂÀ¤³¦¤È¤ÎÁê°ã¤ËͳÍ褹¤ë¤â¤Î¤Ç¤¢¤ê¡¢¤â¤¦°ì¤Ä¤Ï¡¢¼ÂºÝ¤Ë¿ôÃÍ·×»»¤¹¤ë¾å¤Ç¤Î(¤â¤Ã¤Ñ¤éµ»½ÑŪ¤Ê)º¤Æñ¤Ç¤¢¤ë¡£
½àÈ÷¡§¿ô³ØÍѸì(¼ç¤Ë³ÎΨ²áÄø)¤Î²òÀâ
¿ä°Ü³ÎΨ¹ÔÎó¤Ï¡¢³ÎΨ²áÄø¤Ë¸½¤ì¤ë¥Þ¥ë¥³¥Õ²áÄø¤È¿¼¤¤´Ø¤ï¤ê¤¬¤¢¤ë¡£¤½¤³¤Ç¤³¤ÎÀá¤Ç¤Ï PageRank ¼«ÂΤÎÀâÌÀ¤È¤Ï¾¯¤·Î¥¤ì¤Æ¡¢³ÎΨ²áÄø¤Ë¸½¤ì¤ë¿ô³ØÍѸì¤ò¤¤¤¯¤Ä¤«ÀâÌÀ¤·¤Æ¤ª¤¯¡£¤«¤Ê¤êÆñ¤·¤¤ÉôÎà¤ËÆþ¤ë¤È¤ª¤â¤¦¤Î¤Ç¡¢Îɤ¯Ê¬¤«¤é¤Ê¤±¤ì¤ÐÆÉ¤ßÈô¤Ð¤·¤Æ¤â¤é¤Ã¤Æ¤â¹½¤ï¤Ê¤¤ (Îɤ¯¤ï¤«¤é¤Ê¤±¤ì¤ÐÀâÌÀ¤Î»ÅÊý¤¬°¤¤¤È¹Í¤¨¤Æ¤¤¤¿¤À¤¤¤Æ¹½¤ï¤Ê¤¤)¡£¤Þ¤¿¡¢¤Û¤È¤ó¤É¾ÚÌÀ̵¤·¤ËÍѤ¤¤Æ¤¤¤ë¤Î¤ÇÃí°Õ¤·¤Æ¤Û¤·¤¤¡£¾Ü¤·¤¤²òÀâ¤Ï¶µ²Ê½ñ¤òÆÉ¤ó¤Ç¤â¤é¤¤¤¿¤¤¡£
͸þ¥°¥é¥Õ S ¤Î¤¢¤ë¾õÂÖ i ¤ò½Ðȯ¤·¤Æ¡¢Í¸Â»þ´Ö¤Î¸å¤Ç¾õÂÖ i ¤ËºÆ¤ÓÌá¤Ã¤Æ¤¯¤ë³ÎΨ¤¬ 1 ¤Ç¤¢¤ë¤È¤¡¢¤¹¤Ê¤ï¤Á¥°¥é¥Õ¤ÎÏ©¤ò½çÊý¸þ¤Ë¤¿¤É¤ë¤À¤±¤Ç¸µ¤Î°ÌÃÖ¤ËÌá¤Ã¤Æ¤³¤ì¤ë·ÐÏ©¤¬Â¸ºß¤¹¤ë¤È¤¡¢i ¤Ï¡ÖºÆµ¢¡×¤Ç¤¢¤ë¤È¤¤¤¦¡£ºÆµ¢¤Ç¤Ê¤¤¾õÂ֤ϡÖÈóºÆµ¢¡×¤Ç¤¢¤ë¤È¤¤¤¦¡£¾õÂÖ i ¤«¤é½Ðȯ¤·¤ÆÍ¸Â²ó¤Î¿ä°Ü¤Ç¾õÂÖ j ¤Ë㤹¤ë³ÎΨ¤¬ 0 ¤Ç¤Ï¤Ê¤¯Àµ¤Ç¤¢¤ë¤È¤¡¢¡Ö¾õÂÖ j ¤¬¾õÂÖ i ¤«¤éÅþã²Äǽ¡×¤È¤¤¤¦¡£µÕÊý¸þ¤Ë¤âÅþã²Äǽ¤Ç¤¢¤ë¤È¤¡¢¡Öi ¤È j ¤ÏÁê¸ßÅþã²Äǽ¡×¤È¸À¤¦¡£¾õÂÖ i ¤«¤é¾¤Î¤É¤ó¤Ê¾õÂ֤ؤâÅþã¤Ç¤¤Ê¤¤¤È¤¡¢i ¤ò¡ÖµÛ¼ý¾õÂ֡פȸƤ֡£
ÎÙÀܹÔÎó A ¤ÎÄê¤á¤ë¥°¥é¥Õ¤ÎǤ°Õ¤ÎĺÅÀ¤«¤é½Ðȯ¤·¤Æ¡¢Â¾¤ÎǤ°Õ¤ÎĺÅÀ¤Ø¥°¥é¥Õ¤ÎÏ©¤òÌð°õÄ̤ê¤Ë¿Ê¤ó¤ÇÅþã¤Ç¤¤ë¤³¤È¤ò¡Ö¶¯Ï¢·ë¡×¤È¸À¤¦ (¡Öʬ²òÉÔǽ¡×¤È¸Æ¤Ö¤³¤È¤â¤¢¤ë)¡£¶¯Ï¢·ë¤Ï¡¢Ç¤°Õ¤Î¾õÂÖ¤«¤éǤ°Õ¤Î¾õÂÖ¤ØÁê¸ßÅþã²Äǽ¤Ç¤¢¤ë¤³¤È¤ÈƱÃͤǤ¢¤ë¡£ ¶¯Ï¢·ëÀ¤¬ÌäÂê¤Ë¤Ê¤ë¤Î¤Ï¡¢ÎÙÀܹÔÎó A ¤ÎÀ®Ê¬¤Ë 0 ¤¬Â¿¤¤¤È¤¤Ç¤¢¤ë¡£¤¹¤Ù¤Æ¤ÎÀ®Ê¬ aij ¡â 0 ¤Ê¤é¾ï¤Ë¶¯Ï¢·ë¤Ç¤¢¤ë¤³¤È¤ËÃí°Õ¤·¤è¤¦¡£¤Ê¤¼¤Ê¤é¡¢Âбþ¤¹¤ë¥Þ¥ë¥³¥ÕÏ¢º¿¤ÎɸËÜÏ©¤¬S ¤ÎǤ°Õ¤ÎÆóÅÀ´Ö¤òÀµ¤Î³ÎΨ¤Ç±ýÍè¤Ç¤¤ë¤³¤È¤ò¼¨¤·¤Æ¤¤¤ë¤«¤é¤Ç¤¢¤ë¡£
¾õÂÖÁ´ÂΤòƱÃÍÎà(¤¢¤ë¤¤¤ÏºÆµ¢Îà)¤Ëʬ¤±¤ë¤³¤È¤¬¤Ç¤¤ë¡£¤³¤³¤Ç¡¢ºÆµ¢Îà¤È¤Ï¥ê¥ó¥¯¤ò¤¿¤É¤Ã¤Æ¤¤¤±¤ëÈϰϤΤ³¤È¤Ç¤¢¤ë¡£ °ì¤Ä¤ÎƱÃÍÎà¤ËÆþ¤Ã¤Æ¤¤¤ë¾õÂ֤ϸߤ¤¤ËÁê¸ßÅþã²Äǽ¤Ç¤¢¤ë¡£°ì¤Ä¤ÎÎफ¤é½Ðȯ¤·¤Æ¤É¤ì¤«Â¾¤ÎÎà¤ØÀµ¤Î³ÎΨ¤ÇÆþ¤ë¤³¤È¤â¤¢¤ê¤¨¤ë¡£¤·¤«¤·¤³¤Î¾ì¹ç¤ÏÌÀ¤é¤«¤Ë¸µ¤ÎÎà¤ËÌá¤ë¤³¤È¤ÏÉÔ²Äǽ¤Ç¤¢¤ë¡£¤µ¤â¤Ê¤±¤ì¤Ð¡¢¤³¤ÎÆó¤Ä¤ÎÎà¤Ï°ì¤Ä¤ÎƱÃÍÎà¤Ë¤Þ¤È¤Þ¤Ã¤Æ¤·¤Þ¤¦¡£ °Ê²¼¤Î¿Þ¤Ï¡¢R ¤òºÆµ¢Åª¤ÊƱÃÍÎà¡¢T ¤òÈóºÆµ¢Åª¤ÊƱÃÍÎà¤È¤¹¤ë¤È¡¢¥Þ¥ë¥³¥ÕÏ¢º¿¤ÏºÆµ¢Îफ¤é½Ð¤Ê¤¤¤·¡¢ÈóºÆµ¢Îफ¤é½Ð¤Ê¤¤¤³¤È¤â¤¢¤ë¤¬¡¢°ìÅٽФë¤ÈºÆ¤Ó¤½¤ÎÈóºÆµ¢Îà¤ËÌá¤Ã¤Æ¤¯¤ë¤³¤È¤Ï¤Ê¤¤¤³¤È¤ò¼¨¤·¤Æ¤¤¤ë¡£
ºÆµ¢¡¦ÈóºÆµ¢¤Î´Ø·¸¤òɽ¤ï¤·¤¿¿Þ (¾®Ã«(1997) ¿Þ11.1 ¤ò²þÊÑ)
¤³¤ÎƱÃÍ´Ø·¸¤Ç¤¿¤À°ì¤Ä¤ÎºÆµ¢Îष¤«¤Ç¤¤Ê¤¤¤È¤¡¢¤½¤Î¥Þ¥ë¥³¥ÕÏ¢º¿¤Ï¡Ö´ûÌó¡×¤Ç¤¢¤ë¤È¤¤¤¦¡£¸À¤¤´¹¤¨¤ì¤Ð¡¢Á´¤Æ¤Î¾õÂÖ¤¬Áê¸ßÅþã²Äǽ¤Ç¤¢¤ë¤È¤´ûÌó¤Ç¤¢¤ë¤È¤¤¤¦¡£´ûÌó¤Ç¤¢¤ì¤Ð¶¯Ï¢·ë¤Ç¤¢¤ë¡£
Áê¸ß¤Ë¤Þ¤Ã¤¿¤¯´ØÏ¢¤Î¤Ê¤¤ÎÙÀܹÔÎó(¤¢¤ë¤¤¤Ï¿ä°Ü³ÎΨ¹ÔÎó)¤Ï¡¢Å¬Åö¤ÊÃÖ´¹¹ÔÎó(¹Ô¤äÎó¤òÆþ¤ìÂØ¤¨¤ë¹ÔÎó)¤ò³Ý¤±¤ë¤È¡¢
P = | P1 0 |
| 0 P2 |
¤Î¤è¤¦¤Ê´Ø·¸¤Ë¤Ç¤¤ë¡£¤³¤ì¤ÏºÆµ¢Îà P1 ¤È P2 ¤È¤Î´Ö¤ËľÀܤΥê¥ó¥¯´Ø·¸¤¬¤Þ¤Ã¤¿¤¯Â¸ºß¤·¤Ê¤¤¤³¤È¤ò¼¨¤·¤Æ¤¤¤ë¡£
ºÆµ¢ÎࡦÈóºÆµ¢Îब¤Þ¤¶¤Ã¤Æ¤¤¤ëÎÙÀܹÔÎó(¤¢¤ë¤¤¤Ï¿ä°Ü³ÎΨ¹ÔÎó)¤Ï¡¢Å¬Åö¤ÊÃÖ´¹¹ÔÎó¤ò³Ý¤±¤ë¤È¡¢
P = | P1 0 |
| Q P2 |
¤Î¤è¤¦¤Ê´Ø·¸¤Ë¤Ç¤¤ë(¤¿¤À¤· Q ¡â 0)¡£¤³¤Î¤È¤¡¢P1 ¤¬ÈóºÆµ¢Îà¡¢P2 ¤¬ºÆµ¢Îà¤Ç¤¢¤ë¡£
¿ä°Ü³ÎΨ¹ÔÎó¤Ï¥Þ¥ë¥³¥Õ¹ÔÎó¤È¸Æ¤Ð¤ì¤ë¤³¤È¤â¤¢¤ë¡£¥Þ¥ë¥³¥Õ²áÄø¤Î»î¹ÔÎó¤Î´Ñ¬·ë²Ì¤ò¥Þ¥ë¥³¥ÕÏ¢º¿¤È¸Æ¤Ö¡£ ¥Þ¥ë¥³¥ÕÏ¢º¿¤Ï¡¢»þ´Ö¤¬½½Ê¬¤Ë·Ð²á¤¹¤ë¤È¤¢¤ë¼ï¤ÎÊ¿¹Õ¾õÂ֤˶á¤Å¤¯¡£Ç¤°Õ¤Î¾õÂÖ i ¤ËÂФ·¤Æ j ¤¬ÈóºÆµ¢¾õÂ֤ʤé Pij(n) ¢ª 0 ¤Ç¤¢¤ë¡£µÕ¤Ë i ¤¬ÈóºÆµ¢¤Ç j ¤¬ºÆµ¢¤Ç¤¢¤ë¾ì¹ç¡¢¾õÂÖ i ¤Ë¤È¤É¤Þ¤Ã¤Æ¤¤¤é¤ì¤ë³ÎΨ¤Ï 0 ¤Ç¤¢¤ë¡£ i,j ¤¬Æ±¤¸Èó¼þ´üŪºÆµ¢Îà¤Ë°¤·¤Æ¤¤¤ì¤Ð¡¢ Pij(n) ¢ª¦Ðj ¡æ 0 ¤Ç¤¢¤ë¡£
ÄêÍý¡§P ¤ò͸¥ޥ륳¥Õ¹ÔÎó¤È¤¹¤ë¤È¡¢ P ¤Î¸ÇÍÃÍ 1 ¤Î½ÅÊ£ÅÙ¤Ï P ¤«¤é·è¤Þ¤ëºÆµ¢Îà¤Î¿ô¤ËÅù¤·¤¤¡£ (¾ÚÌÀ¤ÏŤ¯¤Ê¤ë¤Î¤Çά¤¹¤ë)¡£
¿ä°Ü³ÎΨ¹ÔÎó¤ËÉտ魯¤ë͸þ¥°¥é¥Õ¤Î¶ËÂ綯Ϣ·ëÀ®Ê¬ (¤ËÂбþ¤¹¤ë¾õÂ֤ν¸¹ç)¤ò¥¨¥ë¥´¡¼¥ÈÉôʬ¡¢¤½¤ì°Ê³°¤Î¶¯Ï¢·ëÀ®Ê¬¤ò¾Ã»¶Éôʬ¤È¸Æ¤Ö¡£¤É¤Î¤è¤¦¤Ê½é´ü¾õÂÖ³ÎΨ x(0) ¤«¤é»Ï¤á¤Æ¤â¡¢»þ´Ö n ¤¬·Ð¤Ä¤Ë¤·¤¿¤¬¤Ã¤Æ x(n) = P(n) x(0) ¤Ç¤¢¤ë¤«¤é¡¢¾Ã»¶Éôʬ¤Ë°¤¹¤ë¾õÂ֤θºß³ÎΨ¤Ï 0 ¤Ë¶á¤Å¤¯¡£¥¨¥ë¥´¡¼¥ÈÉôʬ¤Ë¤Ä¤¤¤Æ¤Ï¡¢³ÆÏ¢·ëÀ®Ê¬¤ËÂбþ¤¹¤ë¾õÂÖ¤ÎÎऴ¤È¤Ë°ì¤Ä¤ÎÆÈΩ¤Ê´ûÌó¥Þ¥ë¥³¥ÕÏ¢º¿¤Î¤´¤È¤¯¤Ë¿¶¤ëÉñ¤¤¡¢³ÆÎà¤ÎÃæ¤Ç¤Î¾õÂÖ³ÎΨ (¤¢¤ë¤¤¤Ï¤½¤Î²áµî¤«¤é¤ÎÊ¿¶Ñ)¤Ï½é´ü¾õÂÖ³ÎΨ¤Ë¤è¤é¤Ê¤¤ÃÍ¡¢¤¹¤Ê¤ï¤ÁÂбþ¤¹¤ë P ¤Î´ûÌóÀ®Ê¬¤Î¸ÇÍ¥Ù¥¯¥È¥ë¤ËÈæÎ㤹¤ë¤â¤Î¤Ë¶á¤Å¤¯¡£Îà¤Î´Ö¤Ç¤Î³ÎΨ¤ÎʬÇۤϽé´ü¾õÂÖ³ÎΨ¤Ë°Í¸¤¹¤ë¡£
Î¥»¶»þ´Ö·¿¥Þ¥ë¥³¥ÕÏ¢º¿¤ÎÉÔÊÑʬÉۤ϶˸ÂʬÉۤǤ¢¤ê¡¢¤½¤ÎʬÉÛ¤«¤é¤Ï¤â¤Ï¤äʬÉۤΰÕÌ£¤Ç¤Î»þ´ÖŪȯŸ¤Ï¤Ê¤¤¡£¾õÂ֤γÎΨʬÉÛ¤¬»þ´Ö¤òÊѲ½¤µ¤»¤Æ¤âÊѤï¤é¤Ê¤¤¤È¤¡¢Äê¾ïʬÉۤȸƤ֡£ PageRank ¤ò¥Þ¥ë¥³¥Õ²áÄø¤ÎÍѸì¤Ç¸À¤¤Ä¾¤¹¤Ê¤é¤Ð¡¢ PageRank ¤Ï¡¢¥é¥ó¥À¥à¤Ë¥ê¥ó¥¯¤ò¤¿¤É¤Ã¤ÆÆ°¤¯¥æ¡¼¥¶¤¬°ìÄê¤Î»þ´Ö¤Î¤¦¤Á¤Ë¤½¤ì¤¾¤ì¤Î¥Ú¡¼¥¸¤òˬÌ䤹¤ëÄê¾ïʬÉۤǤ¢¤ë¤È¤â¸À¤¨¤ë¡£
²¾ÁÛ¥â¥Ç¥ë¤È¸½¼ÂÀ¤³¦¤È¤ÎÁê°ã
¤Ç¤Ï¡¢³ÎΨ²áÄø(¤¢¤ë¤¤¤Ï¥°¥é¥ÕÍýÏÀ)¤Î¹Í¤¨Êý¤È¸½¼Â¤ÎWeb¥Ú¡¼¥¸¤Î¥ê¥ó¥¯¹½Â¤¤È¤ò¤¹¤ê¹ç¤ï¤»¤Æ¤ß¤è¤¦¡£
¤³¤ì¤Þ¤Ç¤ËÎã¤È¤·¤Æµó¤²¤Æ¤¤¿²¾ÁÛŪ¤Ê Web ¥Ú¡¼¥¸·²¤Ï¥ê¥ó¥¯¤ò¤¿¤É¤Ã¤Æ¤µ¤¨¤¤¤ì¤Ðɬ¤º¸ß¤¤¤Î¥Ú¡¼¥¸¤Ë¤¿¤É¤ê¤Ä¤±¤ë´Ø·¸¤Ç¤¢¤Ã¤¿¡£¤¹¤Ê¤ï¤Á¡¢Í¸þ¥°¥é¥Õ¤Ï¶¯Ï¢·ë¤Ç¤¢¤ê¹ÔÎó¤ÏºÆµ¢¤«¤Ä´ûÌó¤Ç¤¢¤Ã¤¿¡£¾å¤Ëµó¤²¤¿¤è¤¦¤Ë¿¤¯¤Î³ÎΨ²áÄø¤Î¶µ²Ê½ñ¤Ç¤ÏºÆµ¢¤Ê¤¤¤·´ûÌó¤Ç¤¢¤ë¤³¤È¤òÁ°Äó¤Ë¤·¤¿¾ÚÌÀ¤¬¿ô¿¤¯¤Ê¤µ¤ì¤Æ¤ª¤ê¡¢´ûÌó¤Ç¤¢¤ì¤Ð¤¤¤í¤¤¤í¤ÎÀ¼Á¤ò¸À¤¦¤³¤È¤¬¤Ç¤¤ë¤è¤¦¤Ë¤Ê¤Ã¤Æ¤¤¤ë¡£
¤À¤¬¸½¼Â¤ÎWeb¥Ú¡¼¥¸¤Ï¡¢¶¯Ï¢·ë¤Ç¤Ï¤Ê¤¤¡£¤¹¤Ê¤ï¤ÁÎÙÀܹÔÎó¤Ï´ûÌó¤Ç¤Ê¤¤¡£ ¶ñÂÎŪ¤Ë¤Ï¡¢¥ê¥ó¥¯¤ò¤¿¤É¤Ã¤Æ¤¤¤¯¤È³°¸þ¤¤Î¥ê¥ó¥¯¤¬¤Þ¤Ã¤¿¤¯¤Ê¤¤¥Ú¡¼¥¸¤Ë¹Ô¤Åö¤¿¤ë¤³¤È¤¬¤¢¤ë¡£¤³¤¦¤¤¤¦¾ì¹ç¤ÏÄ̾ï¤Ï web ¥Ö¥é¥¦¥¶¤Î¡ÖÌá¤ë¡×µ¡Ç½¤òÍѤ¤¤ë¤·¤«¤Ê¤¤¡£¿Í´Ö¤¬¥Ö¥é¥¦¥¸¥ó¥°¤¹¤ë¤À¤±¤Ê¤é¤Ð¤½¤ì¤ÇºÑ¤à¤¬¡¢ PageRank ·×»»¤Î¾å¤Ç¤Ï¤½¤ì¤Ç¤ÏºÑ¤Þ¤Ê¤¤¡£ PageRank ¤¬µÛ¤¤¹þ¤Þ¤ì¤Æ¤·¤Þ¤Ã¤ÆÌá¤Ã¤Æ¤³¤Ê¤¤¤«¤é¤Ç¤¢¤ë¡£¤³¤Î¤è¤¦¤Ê¥Ú¡¼¥¸¤Î¤³¤È¤ò¡¢Page ¤é¤Ï¡Ödangling page¡×¤È¸Æ¤ó¤Ç¤¤¤ë¡£ Ʊ¤¸Íý¶þ¤Ç¡¢³°¸þ¤¤Î¥ê¥ó¥¯¤Ï¤¢¤ë¤±¤ì¤É¤â¡¢Ä¥¤é¤ì¤Æ¤¤¤ë¥ê¥ó¥¯¤¬¤Þ¤Ã¤¿¤¯Ìµ¤¤¥Ú¡¼¥¸¤â¸ºß¤¹¤ë¡£ Page ¤é¤Ï¤³¤Î¤è¤¦¤Ê¥Ú¡¼¥¸¤Ë¤Ä¤¤¤Æ¤Ï¹Íθ¤·¤Æ¤¤¤Ê¤¤¤¬¡¢Î®Æþ¤¹¤ë PageRank ¤¬¤Ê¤¤¤Î¤Ëή½Ð¤¹¤ë PageRank ¤À¤±¹Íθ¤Ç¤¤ë¤Î¤ÏÂоÎÀ¤«¤é¸À¤Ã¤Æ¤â¤ª¤«¤·¤Ê¤Ï¤º¤Ç¤¢¤ë¡£
¤Þ¤¿¡¢¥ê¥ó¥¯¤¬Éôʬ½¸¹ç¤À¤±¤Ç¥ë¡¼¥×¤Ë¤Ê¤Ã¤Æ³°¤Ë½Ð¤é¤ì¤Ê¤¤¸½¾Ý¤â¤¢¤ë¡£¤³¤ì¤ÏÈó¼þ´üŪºÆµ¢Îबʣ¿ô¸ºß¤¹¤ë¤Èµ¯¤³¤ê¤¦¤ëÌäÂê¤Ç¤¢¤ë (¾åµ¤Î¿Þ¤Ç R ¤Î°ì¤Ä¤Ë¤Ï¤Þ¤ê¤³¤ó¤Ç¤·¤Þ¤Ã¤¿¤é¡¢Â¾¤ÎR ¤ä T ¤Ë¤Ï¤â¤¦°Ü¤ì¤Ê¤¤¤³¤È¤ò¹Í¤¨¤ÆÄº¤¤¿¤¤)¡£ Page ¤é¤Ï¡Örank sink¡×¤È¸Æ¤ó¤Ç¤¤¤ë¡£ ¤½¤ì¤Ë¸½¼Â¤Î¥Ú¡¼¥¸¤Ç¤Ï¡¢¥ê¥ó¥¯¤ò¤É¤¦¤¿¤É¤Ã¤Æ¤¤¤Ã¤Æ¤â¡¢¥ê¥ó¥¯¤ò¤¿¤É¤ë¤À¤±¤Ç¤ÏÀäÂФˤ¿¤É¤ê¤Ä¤±¤Ê¤¤¥Ú¡¼¥¸·²¤¬Â¸ºß¤¹¤ë¡¢¤Ä¤Þ¤ê¥Ú¡¼¥¸·²¤¬Áê¸ß¤ËÏ¢´Ø¤Î¤Ê¤¤Ê£¿ô¤ÎƱÃÍÎà(ºÆµ¢Îà)¤«¤é¤Ê¤Ã¤Æ¤¤¤ë¤ï¤±¤Ç¤¢¤ë¡£
¤Ä¤Þ¤ê¡¢¸½¼Â¤Î Web ¥Ú¡¼¥¸¤«¤é¤Ê¤ë¿ä°Ü³ÎΨ¹ÔÎó¤Î¤Û¤È¤ó¤É¤Ï´ûÌó¤Ç¤Ê¤¤¡£´ûÌó¤Ç¤Ê¤¤¾ì¹ç¤ÏºÇÂç¸ÇÍÃÍ(¤¹¤Ê¤ï¤Á1)¤¬½ÅÊ£¤·¤Æ¤ª¤ê¡¢Í¥¸ÇÍ¥Ù¥¯¥È¥ë¤¬Ê£¿ô¸ºß¤¹¤ëÌäÂê¤òÈò¤±¤é¤ì¤Ê¤¤¡£¸À¤¤´¹¤¨¤ì¤Ð¡¢PageRank ¤¬°ì°Õ¤Ë·è¤Þ¤é¤Ê¤¤¤³¤È¤ò°ÕÌ£¤¹¤ë¡£
¤½¤³¤Ç¡¢Page ¤é¤Ï¤³¤Î¤è¤¦¤ÊÌäÂê¤ò²ò·è¤¹¤ë¤¿¤á¤Ë¡¢ ¡Ö¥æ¡¼¥¶¤Ï¡¢Â¿¤¯¤Î¾ì¹ç¤Ï¸½ºß¤Î¥Ú¡¼¥¸¤Ë¸ºß¤¹¤ë¥ê¥ó¥¯¤ò¤¿¤É¤Ã¤Æ°Üư¤¹¤ë¤¬¡¢»þ¡¹¤ÏÁ´¤¯Ìµ´Ø·¸¤Ê¥Ú¡¼¥¸¤Ë¥¸¥ã¥ó¥×¤¹¤ë¡× ¤È¤¤¤¦¥Ö¥é¥¦¥¸¥ó¥°¥â¥Ç¥ë¤ò¹Í¤¨¤¿¡£ ¤Ê¤ª¡¢¡Ö»þ¡¹¡×¤È¤¤¤¦¤Î¤Ï¶ñÂÎŪ¤Ë¤Ï 15% ¤È¤¤¤¦¿ô»ú¤Ë¸ÇÄꤷ¤Æ·×»»¤·¤Æ¤¤¤ë¡£¥æ¡¼¥¶¤Ï 85% ¤Ï¥ê¥ó¥¯¤ò¤¿¤É¤ë¤¬¡¢15% ¤ÏÆÍÁ³Ìµ´Ø·¸¤Ê¥Ú¡¼¥¸¤ËÈô¤ó¤Ç¤¤¤¯¤È¤¤¤¦¤³¤È¤Ç¤¢¤ë¡£ (Ãí¡§Page ¤é¤Î¥ª¥ê¥¸¥Ê¥ë¤Î¼êË¡¤Ç¤Ï¤½¤ì¤¾¤ì 87% (= 1/1.15) ¤È 13% (= 0.15/1.15) ¤Ç¤¢¤Ã¤¿¡£)
¤³¤ì¤ò¿ô¼°¤Çɽ¤ï¤¹¤È°Ê²¼¤Î¤è¤¦¤Ë¤Ê¤ë¡£
M' ¡á c¡¦M + (1-c)¡¦[1/N]
¤¿¤À¤·¡¢[1/N] ¤Ï¤¹¤Ù¤Æ¤ÎÍ×ÁǤ¬ 1/N ¤Ç¤¢¤ë N¼¡ÀµÊý¹ÔÎó¤Ç¤¢¤ê¡¢ c = 0.85 (= 1-0.15) ¤Ç¤¢¤ë¡£ M' ¤âƱ¤¸¤¯¿ä°Ü³ÎΨ¹ÔÎó¤Ë¤Ê¤ë¤³¤È¤Ï¼«ÌÀ¤À¤í¤¦¡£¤¹¤Ê¤ï¤Á¡¢Page ¤¿¤Á¤Ë¤è¤ëÊÑ·Á¤Ï¤â¤È¤â¤È¤Î¹ÔÎó M ¤Î¸ÇÍÃÍÌäÂ꤫¤é¡¢¹ÔÎó M' ¤ÎÍ¥¸ÇÍ¥Ù¥¯¥È¥ë¤òµá¤á¤ë¸ÇÍÃÍÌäÂê¤ËÊÑ·Á¤·¤¿¤³¤È¤ò°ÕÌ£¤¹¤ë¡£ M ¤¬Äê¾ï̵µ²±¾ðÊó¸»(i.i.d.)¤Ç¤¢¤ë¾ì¹ç¡¢M' ¤Ï¡Öº®¹ç¾ðÊ󸻡פȸƤФ졢Äê¾ï¤Ç¤Ï¤¢¤ë¤¬¥¨¥ë¥´¡¼¥ÈŪ¤Ç¤Ê¤¤¾ðÊ󸻤Îŵ·¿Îã¤Ç¤¢¤ë¡£
¤³¤Î¤³¤È¤ò¿ô³ØÅª¤Ë¸«¤ì¤Ð¡ÖÈó´ûÌó¤Ê¿ä°Ü¹ÔÎó¤ò´ûÌó¤Ë¤¹¤ë¡×¤³¤È¡¢Ê̤θÀÍդǤϡֶ¯Ï¢·ë¤Ç¤Ï¤Ê¤¤¥°¥é¥Õ¤ò¶¯Ï¢·ë¤Ë¤¹¤ë¡×ÊÑ´¹Áàºî¤ò»Ü¤·¤¿¤³¤È¤ò°ÕÌ£¤¹¤ë¡£ Á´¤Æ¤ÎÍ×ÁǤ˰Üž³ÎΨ 0.15 ¤ò¹Íθ¤¹¤ë¤È¸À¤¦¤³¤È¤Ï¡¢¤â¤È¤â¤È¤Î´ûÌó¤Ç¤Ê¤¤¿ä°Ü³ÎΨ¹ÔÎó¤ò¡¢´ûÌ󤫤ĺƵ¢(ÅöÁ³¤Î¤³¤È¤Ê¤¬¤éÈóÉé¤Ç¤â¤¢¤ë) ¤Î¿ä°Ü³ÎΨ¹ÔÎó¤ËÊÑ´¹¤¹¤ë¤³¤È¤ò°ÕÌ£¤¹¤ë¡£ ¤â¤È¤â¤È¤Î¿ä°Ü³ÎΨ¹ÔÎó¤ËÂФ·¤Æ¤³¤Î¤è¤¦¤ÊÊÑ´¹Áàºî¤ò¹Ô¤¦¤³¤È¤Ë¤è¤Ã¤Æ¡¢ PageRank ¤¬°ì°Õ¤Ë·è¤Þ¤ë¤³¤È¡¢¤¹¤Ê¤ï¤Á¡¢ºÇÂç¸ÇÍÃͤνÅÊ£ÅÙ¤ò 1 ¤Ë¤¹¤ë¤³¤È¤¬Êݾڤµ¤ì¤ë¡£¤³¤Î¤è¤¦¤ÊÊÑ´¹Áàºî¤ò¹Íθ¤¹¤ë¤³¤È¤Ë¤è¤Ã¤Æ¿ä°Ü³ÎΨ¹ÔÎó¤ÎºÆµ¢Îà¤Î¿ô¤Ï 1 ¤Ë¤Ê¤êƱ»þ¤Ë´ûÌó¤Ë¤Ê¤ë¤«¤é¡¢Àè¤ÎÄêÍý¤Ë¤è¤ê¡¢Í¥¸ÇÍ¥Ù¥¯¥È¥ë(¤¹¤Ê¤ï¤Á PageRank)¤¬°ì°Õ¤Ë·è¤Þ¤ë¤È¸À¤¦¤³¤È¤Ë¤Ê¤ë¤Î¤Ç¤¢¤ë¡£
¿ôÃÍ·×»»¾å¤ÎÌäÂêÅÀ(¤½¤Î1)
¤³¤³¤Ç¤Ï PageRank ¤Î¤À¤¤¤¿¤¤¤Î³µÇ°¤¬¤ï¤«¤ì¤ÐÎɤ¤¤Î¤Ç¡¢¿ôÃÍ·×»»¾å¤Îµ»½ÑŪÌäÂê¤Ë¿¼¤¯Î©¤ÁÆþ¤ëɬÍפϤʤ¤¤È¤ª¤â¤ï¤ì¤ë (¤½¤â¤½¤â¡¢É®¼Ô¼«¿È¤â¼«¿®¤ò»ý¤Ã¤ÆÀâÌÀ¤Ç¤¤Ê¤¤)¡£ ¤À¤¬¡¢¸ÇÍÃͲòÀϤÏϢΩ°ì¼¡ÊýÄø¼°²òÀÏ¤ÈÆ±Íͤ˳Ƽï¤ÎÅý·×ʬÀϤÎÃæ¤ÇÍøÍѤµ¤ì¤ë½ÅÍפʿôÃÍ·×»»¼êË¡¤Î°ì¤Ä¤Ê¤Î¤Ç¡¢²òÀÏË¡¤Ë¤Ä¤¤¤Æ´Êñ¤Ë¿¨¤ì¤Æ¤ª¤¯¡£
¿ôÃÍ·×»»¤¹¤ë¾å¤Ç¤ÎÌäÂê¤Î°ì¤Ä¤Ï¡¢¼çµ²±Îΰè¤ÎÌäÂê¤Ç¤¢¤ë¡£
²¾¤Ë N ¤¬ 104 ¤Î¥ª¡¼¥À¤À¤Ã¤¿¤È¤·¤è¤¦¡£Ä̾ï¤Ï¿ôÃÍ·×»»¥×¥í¥°¥é¥à¤ÎÆâÉô¤Ç¤Ï¹ÔÎó¤ä¥Ù¥¯¥È¥ë¤ÏÇÜÀºÅ٤dzÊǼ¤µ¤ì¤ë¤«¤é¡¢N¼¡ÀµÊý¹ÔÎó A ¤Îµ²±Îΰè¤Ï sizeof(double) * N * N = 8 * 104 * 104 = 800MB ¤È¤Ê¤ë¡£¤µ¤¹¤¬¤Ë¡¢800MB ¤Î¼çµ²±Îΰè¤Ï¤Ê¤«¤Ê¤«»ý¤Æ¤ë¤â¤Î¤Ç¤Ï¤Ê¤¤¤À¤í¤¦¤¬¡¢¤È¤Ï¤¤¤¨ÉÔ²Äǽ¤Ê¿ô»ú¤È¸À¤¦¤ï¤±¤Ç¤â¤Ê¤¤¡£¤À¤¬¡¢N ¤¬ 105 ¤ä 106 ¤Ë¤Ê¤ë¤È¡¢¤½¤ì¤¾¤ì 80GB, 8TB ¤È¤Ê¤ë¡£¤³¤¦¤Ê¤ë¤È¥á¥â¥ê¤É¤³¤í¤«¥Ï¡¼¥É¥Ç¥£¥¹¥¯¤Ç¤â¤â¤¦¥à¥ê¤Ç¤¢¤ë¡£ Google ¤Ç¤Ï 10²¯°Ê¾å¤Î¥Ú¡¼¥¸¤ò°·¤Ã¤Æ¤¤¤ë¤«¤é(2001ǯ»þÅÀ)¡¢¤Þ¤È¤â¤Ê¤ä¤êÊý¤Ç¤Ï¤Þ¤Ã¤¿¤¯¥À¥á¤Ç¤¢¤ë¤³¤È¤¬¤ï¤«¤ë¡£
¤â¤Ã¤È¤â¡¢A ¤ÏÁÂ(sparse)¤Ê¹ÔÎó¤Ç¤¢¤ë¡£¥ê¥ó¥¯¤òÄ¥¤ê¤Þ¤¯¤Ã¤Æ¤¤¤ë¥Ú¡¼¥¸¤¬°ìÉô¤Ë¤¢¤Ã¤¿¤È¤·¤Æ¤â¡¢ WebÁ´ÂΤËÄ¥¤Ã¤Æ¤¤¤ë¤â¤Î¤Ï¤Ê¤¤¤·¡¢¤¢¤Ã¤¿¤È¤·¤Æ¤â¤½¤ì¤Ï¶Ë¤á¤Æ¤Þ¤ì¤Ê¸ºß¤Ç¤¢¤ë¤«¤é¤À¡£Ê¿¶ÑŪ¤Ë¤Ï¡¢1¥Ú¡¼¥¸¤¢¤¿¤ê10-20¥ê¥ó¥¯ÄøÅ٤ǤϤʤ¤¤À¤í¤¦¤« (IBM Almaden ¸¦µæ½ê¤Ë¤è¤ë 'Graph structure in the web'¤Ë¤è¤ì¤Ð¡¢Ê¿¶Ñ¤¹¤ë¤È 16.1 ÄøÅÙ¤À¤½¤¦¤Ç¤¢¤ë)¡£¤À¤«¤é¡¢A ¤ÏŬÀڤʰµ½ÌÊýË¡¤òÍѤ¤¤Æ°µ½Ì¤Ç¤¤ë¡£ N ¤¬ 106 ¤Ç¤¢¤Ã¤Æ¤âÊ¿¶Ñ¥ê¥ó¥¯¿ô¤ò10¤È¤¹¤ì¤Ð 80MB ¤ÇºÑ¤ß¡¢µ¬ÌϤ«¤é¤¤¤Ã¤ÆÌµÍý¤Î¤Ê¤¤¿ô»ú¤ËǼ¤á¤ë¤³¤È¤¬¤Ç¤¤ë¡£
Á¹ÔÎó¤Î³ÊǼÊý¼°¤Ï¤¹¤Ç¤Ë½½Ê¬¸¦µæ¤µ¤ì¤Æ¤¤¤ë¤«¤é(͸ÂÍ×ÁÇË¡¤Î²òË¡¤Ê¤É)¡¢Å¬ÀڤʿôÃÍ·×»»¤ÎÀìÌç½ñ¤Ë¤¢¤¿¤Ã¤Æ¤½¤ì¤é¤ò³Ø¤Ù¤ÐÎɤ¤¡£¤È¤Ï¤¤¤¨¡¢ÁêÅö¤ËÆñ²ò¤ÇÌÌÅݤʼêË¡¤¬É¬ÍפǤ¢¤ë¡£¤¿¤À¤·¤¦¤Þ¤¯¤¹¤ì¤ÐÊÂÎ󲽤ˤè¤ë¹â®·×»»¤Î²ÄǽÀ¤¬¤Ç¤Æ¤¯¤ë(¤é¤·¤¤)¤³¤È¤Ï»ØÅ¦¤·¤Æ¤ª¤¤¿¤¤¡£Á¹ÔÎó¤Î²òË¡¤Ç¤ÏÈóÎíÍ×ÁǤò¤É¤Î¤è¤¦¤ËÇÛÎó¾å¤Ë³ÊǼ¤¹¤ë¤«¤Ë¤è¤ê¡¢·×»»Àǽ¤ÈÊÂÎóÀǽ¤¬¶¯¤¯±Æ¶Á¤ò¼õ¤±¤ë¤«¤é¤Ç¤¢¤ë¡£
¿ôÃÍ·×»»¾å¤ÎÌäÂêÅÀ(¤½¤Î2)
¤â¤¦°ì¤Ä¤Ï¡¢¼ý«¤ÎÌäÂê¤Ç¤¢¤ë¡£
Äê¾ïÊýÄø¼°
xi = ¦²Aijxi
¤Ï N ¸µ¤ÎϢΩ°ì¼¡ÊýÄø¼°¤Ç¤¢¤ê¡¢°ìÈÌŪ¤Ë¤Ï²òÀϲò¤¬ÆÀ¤é¤ì¤Ê¤¤¤«¤é¡¢¿ôÃÍŪ¤Ë²ò¤¯¤·¤«¤Ê¤¤¡£ Àè¤Ëµó¤²¤¿Îã¤Ç¤Ï¸ÇÍÃͤȸÇÍ¥Ù¥¯¥È¥ë¤òµá¤á¤ë¤Î¤Ë Octave ¤Î eig() ´Ø¿ô¤òÍѤ¤¤¿¤¬¡¢¤³¤ì¤ÏÌäÂ꤬¾®¤µ¤¤¾ì¹ç¤Ë¤·¤«Å¬ÍѤǤ¤Ê¤¤¡£¤½¤â¤½¤â¡¢Á´Éô¤Î¸ÇÍÃÍ¡¿¸ÇÍ¥Ù¥¯¥È¥ë¤ò·×»»¤¹¤ëɬÍפϤʤ¤¡£
ºÇÂç¸ÇÍÃͤȤ½¤ì¤Ë°¤¹¤ë¸ÇÍ¥Ù¥¯¥È¥ë(Í¥¸ÇÍ¥Ù¥¯¥È¥ë)¤òµá¤á¤ë¿ôÃÍ·×»»¼êË¡¤Ë¤Ï¡¢¡Ö¤Ù¤¾èË¡¡×(È¿ÉüË¡¤È¤â¸Æ¤Ð¤ì¤ë)¤òÍѤ¤¤ë¤Î¤¬ÉáÄ̤Ǥ¢¤ë¡£¤³¤ì¤Ï¡¢½é´ü¥Ù¥¯¥È¥ë x0 ¤òŬÅö¤Ë¤È¤ê¡¢ x(n+1) = A y(n) (¤¿¤À¤·¡¢y(n) = x(n) / c(n)) ¤È¤·¤Æ n ¢ª¡ç ¤È¤·¤¿¾ì¹ç¡¢x ¤ÏºÇÂç¸ÇÍÃͤò»ý¤Ä¸ÇÍ¥Ù¥¯¥È¥ë¤Ë¼ý«¤·Æ±»þ¤Ë c ¤Ï¤½¤ÎºÇÂç¸ÇÍÃͤ˼ý«¤¹¤ë¤È¤¤¤¦¡¢Àþ·ÁÂå¿ôŪ¤ÊÀ¼Á¤òÍøÍѤ·¤¿·×»»ÊýË¡¤Ç¤¢¤ë (¾ÚÌÀ¤ÏÀþ·ÁÂå¿ô¤Î¶µ²Ê½ñ¤ËºÜ¤Ã¤Æ¤¤¤ë¤Î¤Ç»²¾È¤µ¤ì¤¿¤¤)¡£ ¤Ù¤¾èË¡(È¿ÉüË¡)¤ÎÆÃŤÏÃ༡·«¤êÊÖ¤·¤Î¶á»÷Ë¡¤Ë¤è¤ê²ò¥Ù¥¯¥È¥ë¤¬²þÁ±¤Ç¤¤ë¤³¤È¤Ç¤¢¤ë¡£¤½¤ÎÍøÅÀ¤Ï¡¢¹ÔÎó¤È¥Ù¥¯¥È¥ë¤Î³Ý¤±»»¤òŬÅö¤Ê²ó¿ô·«¤êÊÖ¤¹¤À¤±¤ÇÎɤ¤¤Î¤Ç¥×¥í¥°¥é¥à¤¬´Êñ¤ÇºÑ¤à¤³¤È¤È¡¢Ä¾ÀÜË¡¤Ç¤Ï¥á¥â¥ê¤ä¥Ç¥£¥¹¥¯¤ÎÀ©¸Â¤Ë¤è¤Ã¤Æ¼è¤ê°·¤¨¤Ê¤¤¤è¤¦¤ÊÂ絬ÌϤʲòÀϤò¹Ô¤¨¤ë¤³¤È¤Ç¤¢¤ê¡¢Â¿¤¯¤Î¼ÂÍÑŪ»»Ë¡¤Î¸¶ÅÀ¤Ç¤¢¤ë¡£
¤³¤³¤Ç¡¢Àþ·ÁÂå¿ô¤Î´Êñ¤ÊÄêÍý(¥Ú¥í¥ó¡¦¥Õ¥í¥Ù¥Ë¥¦¥¹¤ÎÄêÍý)¤«¤é¡¢¿ä°Ü³ÎΨ¹ÔÎó¤ÎÀäÂÐÃͺÇÂç¤Î¸ÇÍÃÍ¤Ï 1 ¤Ç¤¢¤ë¤³¤È¤ËÃí°Õ¤·¤Æ¤ª¤³¤¦¡£¤³¤Î¤³¤È¤òÍѤ¤¤ì¤Ð¡¢È¿ÉüË¡¤Ç¤Î PageRank ¤Î·×»»¤¬¤è¤ê¤ä¤ê¤ä¤¹¤¯¤Ê¤ë¡£¤¹¤Ê¤ï¤Á¡¢ºÇÂç¸ÇÍÃͤ¬´ûÃΤǤ¢¤ë¤«¤é¡¢ Ax = x ¤òËþ¤¿¤¹¥Ù¥¯¥È¥ë x ¤òµá¤á¤è¤È¤¤¤¦¡¢¤è¤ê´Êñ¤ÊÌäÂê¤Ëµ¢Ã夵¤ì¤ë¤«¤é¤Ç¤¢¤ë¡£ ¤³¤ì¤ÏºÙ¤«¤¤¤³¤È¤Ç¤Ï¤¢¤ë¤¬½ÅÍפǤ¢¤ë¤È¤ª¤â¤¦¡£¤Þ¤º¡¢·×»»¤ËÈæ³ÓŪ¥³¥¹¥È¤Î¤«¤«¤ë³ä¤ê»» (y(n) = x(n) / c(n)) ¤òÉÔÍפˤǤ¤ë¡£¤µ¤é¤Ë¡¢È¿ÉüË¡¤Ë¤ª¤¤¤Æ¤Ï½½Ê¬¤ÊÀºÅÙ¤ò¼è¤é¤º¤«¤Ä²Ã®ÊýË¡¤ò´Ö°ã¤¨¤ë¤È¡¢ºÇÂç¸ÇÍÃͤǤʤ¯ÆóÈÖÌܤËÂ礤¤¸ÇÍÃͤȤ½¤ì¤Ë°¤¹¤ë¸ÇÍ¥Ù¥¯¥È¥ë¤ò·×»»¤·¤Æ¤·¤Þ¤¦¾ì¹ç¤¬¤¢¤ë¤«¤é¤Ç¤¢¤ë (¤â¤Ã¤È¤â¤³¤ì¤Ïµ©¤Ç¤¢¤ë¤·¡¢º¬ËÜŪ¤Ë¸í¤Ã¤Æ¤¤¤ë¤«¤é¤«¤â¤·¤ì¤Ê¤¤)¡£¤À¤¬ºÇÂç¸ÇÍÃͤ¬¤ï¤«¤Ã¤Æ¤¤¤ë¤«¤é¡¢¥Á¥§¥Ã¥¯¤¹¤ë¤³¤È¤¬²Äǽ¤Ë¤Ê¤ë¡£ Page ¤é¤ÎÂè°ìÏÀʸ¤Ç¤Ï¤³¤Î¤³¤È¤Ë¤Ïµ¤¤¬ÉÕ¤¤¤Æ¤¤¤Ê¤«¤Ã¤¿¤è¤¦¤À¤¬¡¢ Haveliwala ¤ÎÂèÆóÏÀʸ¤Ç¤³¤ÎÅÀ¤Ë´Ø¤¹¤ë½¤Àµ¤¬²Ã¤¨¤é¤ì¤Æ¤¤¤ë¡£
È¿Éü²ó¿ô¤Ï¡¢¤É¤ÎÄøÅÙ¤ÎÀºÅÙ¤òµá¤á¤ë¤«¤Ë¤è¤Ã¤Æ·è¤Þ¤ë¡£¤Ä¤Þ¤êÀºÅÙ¤¬Íߤ·¤±¤ì¤ÐÈ¿Éü²ó¿ô¤òÁý¤ä¤·¤Æ¤ä¤ëɬÍפ¬¤¢¤ë¡£¤·¤«¤·¡¢¤Ù¤¾èË¡(È¿ÉüË¡)¤Î¸íº¹¤Î¼ýÂ«Èæ¤Ï¡¢·¸¿ô¹ÔÎó¤Î¥¹¥Ú¥¯¥È¥ëÆÃÀ(¸ÇÍÃͤÎÀäÂÐÃͤÎʬÉÛ)¤Ë¶¯¤¯°Í¸¤¹¤ë¡£ ¶ñÂÎŪ¤Ë¤Ï¡¢ÀäÂÐÃͺÇÂç¤Î¸ÇÍÃͦË1¡¢ÆóÈÖÌܤò¦Ë2¤È¤·¡¢Í¥±ÛΨ(¤Ê¤¤¤·¤Ï¼ý«Ψ) d = ¦Ë1 / ¦Ë2 ¤È¤¹¤ë¤È¡¢ d ¤¬ 1 ¤Ë¶á¤¤¤Û¤É¼ý«¤¬ÃÙ¤¯¤Ê¤ë¤³¤È¤¬ÃΤé¤ì¤Æ¤¤¤ë¡£¤À¤¬¡¢d ¤Ï¡¢N ¤¬Â礤¤¾ì¹ç¤Ë¤ÏÅöÁ³ 1 ¤Ë¶á¤¯¤Ê¤ë¡£¤Ê¤¼¤Ê¤é¡¢ÀäÂÐÃͺÇÂç¸ÇÍÃͤ¬ 1 ¤Ç¤¢¤ë¤³¤È¤«¤é¡¢Â¾¤Î N-1 ¸Ä¤Î¸ÇÍÃͤÎÀäÂÐÃͤϤ¹¤Ù¤Æ 1 ¤è¤ê¾®¤µ¤¤¡£¤À¤¬¡¢ N-1 ¸Ä¤¬¤Ò¤·¤á¤¤¢¤¦¤³¤È¤«¤é ¦Ë1 ¤È¦Ë2 ¤Î´Ö¤Ë¤Ï¤Û¤È¤ó¤Éº¹¤¬¤Ê¤¤¤¿¤á¤Ç¤¢¤ë¡£¤³¤Î¤¿¤á°ìÈ̤˼ý«¤¬ÃÙ¤¯¤Ê¤ë¡£
¼ý«¤¬ÃÙ¤¤¤È¤¤¤¦¤Î¤Ï¡¢¥Ù¥¿¤Ê¸ÀÍդǸÀ¤¨¤Ð¡¢¤¤¤Ä¤Þ¤Ç·Ð¤Ã¤Æ¤â·×»»¤¬½ª¤é¤Ê¤¤¤È¤¤¤¦¤³¤È¤Ç¤¢¤ë¡£ÂФ·¤Æ¡¢¼ý«¤ò®¤á¤ë¤¿¤á¤ÎŬÅö¤Ê²Ã®ˡ¤â¤¤¤¯¤Ä¤«Â¸ºß¤¹¤ë¤³¤È¤Ï¸ºß¤¹¤ë¤¬¡¢¤½¤ì¤é¤òŬÍѤ¹¤ë¤¿¤á¤Ë¤Ï¿ôÃÍ·×»»µ»Ë¡¤ËÂФ¹¤ë½½Æóʬ¤ÊÍý²ò¤¬É¬ÍפȤʤ뤿¤á¡¢¿ôÃÍ·×»»¤ÎÀìÌç²È¤Ç¤Ê¤¤¸Â¤ê¤ÏƳÆþ¤Ï°×¤·¤¤¤â¤Î¤Ç¤Ï¤Ê¤¤¡£

