一般論文
୍⯡ㄽᩥ‫ݡࡍ࡛ࣝࣉࣥࢧ࡛ࡲࡃ࠶ࡣࢀࡇݡ‬1. 䛿䛨䜑䛻

␗䛺䜛どⅬ䛛䜙䛾䝜䞊䝗ᶵ⬟䛻ᇶ䛵䛟䝁䝭䝳䝙䝔䜱ᢳฟἲCommunity Extraction Method Based on
Nodes· Function from Different Viewpointsఅぢ ༟ᜤjụ⏣ ဴኵi

DBSJ
Vol.11,DBSJ Journal,
Journal,Vol.
11,No.3
No.3
February
February 20132013ᩧ⸨ ࿴ᕭi㢼㛫 ୍ὒkTakayasu FUSHIMI Kazumi SAITO
Tetsuo IKEDA Kazuhiro KAZAMAᮏ✏䛷䛿䠈䝜䞊䝗䛾どⅬ䛻ᇶ䛵䛟ᶵ⬟䝁䝭䝳䝙䝔䜱ᢳฟ䜢୺㢟䛸䛩䜛䠊ᶵ⬟䝁䝭䝳䝙䝔䜱䛸䛿䠈䝛䝑䝖䝽䞊䜽඲య䜢ᐈほど䛧䛯኱ᇦⓗ䛺ᶵ⬟䛜㢮ఝ䛩䜛䝜䞊䝗䛛䜙䛺䜛䝁䝭䝳䝙䝔䜱䛷䛒䜛䠊୍᪉䠈䝜䞊䝗䛾ᙺ๭䞉ᶵ⬟䛿どⅬ䜢ኚ䛘䜛䛣䛸䛻䜘䛳䛶ኚ໬䛩䜛䛸᝿ᐃ䛥䜜䜛䠊䛭䛣䛷䠈ಶ䚻䛾䝜䞊䝗䠄䜶䝂䝜䞊䝗䠅䛾どⅬ䛻ᇶ䛵䛟䝟䞊䝋䝘䝷䜲䝈ᶵ⬟䝁䝭䝳䝙䝔䜱䛸䛔䛖ᴫᛕཬ䜃䛭䛾ᢳฟᡭἲ䜢ᥦ᱌䛩䜛䠊ලయⓗ䛻䛿䠈ᶵ⬟䝁䝭䝳䝙䝔䜱ᢳฟἲ䛻䛚䛡䜛 PageRank 䝇䝁䜰ィ⟬䛻䛚䛔䛶䜶䝂䝜䞊䝗䛰䛡䛻್䜢タᐃ䛧䛯ึᮇ䝧䜽䝖䝹䜢⏝䛔䠈䛥䜙䛻௵ព䛾䝜䞊䝗䛛䜙䜶䝂䝜䞊䝗䜈䝆䝱䞁䝥䛩䜛䜶䝂䝆䝱䞁䝥䛸࿧䜆ᶵᵓ䜢ᑟධ䛩䜛䠊ேᕤ䝛䝑䝖䝽䞊䜽䛚䜘䜃ᐇ䝛䝑䝖䝽䞊䜽䜢⏝䛔䛯ホ౯ᐇ㦂䜘䜚䠈㑅ᢥ䛥䜜䛯䜶䝂䝜䞊䝗䛾どⅬ䛻ᇶ䛵䛝䠈䜶䝂䝜䞊䝗࿘㎶䝜䞊䝗䛾ศ㢮⢏ᗘ䜢⣽䛛䛟䠈㐲䛟䛾䝜䞊䝗䛾ศ㢮⢏ᗘ䜢⢒䛟ศ㢮䛷䛝䜛䛣䛸䠈ᐈほⓗ䛺ᶵ⬟䛜㢮ఝ䛩䜛䝜䞊䝗䛷䜒䠈䜶䝂䛸䛾㛵ಀ䛜␗䛺䜜䜀␗䛺䜛䝁䝭䝳䝙䝔䜱䛸䛧䛶ᢳฟ䛷䛝䜛䛣䛸䜢♧䛩䠊
In this paper, we attempt to extract functional
community based on personalized view of each node. A
conventional method of functional community extraction
can divide all nodes into some node groups with similar
global functions based on objective viewpoint for whole ofa network. On the other hand, we could assume thatfunctions and roles of each node can differ according toviewpoint shifts. Thus we propose a concept of
personalized functional community and a method of
extracting these communities based on viewpoint of eachnode(ego node). Concretely, we adjust an initialized vectorof PageRank and introduce an ego-jump mechanism to the
proposed method. From experimental results using an
artificial and two real networks, we show that our
proposed method can divide neighbor nodes from the ego
node into fine clusters and distant nodes into coarse
clusters, and also divide functionally similar nodes basedon objective viewpoint into several clusters according torelation with the ego node.
jᏛ⏕఍ဨ 㟼ᒸ┴❧኱Ꮫ኱Ꮫ㝔⤒Ⴀ᝟ሗ࢖ࣀ࣮࣋ࢩࣙࣥ
◊✲⛉༤ኈᚋᮇㄢ⛬ j11507@u-shizuoka-ken.ac.jpiṇ఍ဨ 㟼ᒸ┴❧኱Ꮫ⤒Ⴀ᝟ሗᏛ㒊{k-saito,t-ikeda}@u-shizuoka-ken.ac.jpkṇ఍ဨ ࿴ḷᒣ኱Ꮫࢩࢫࢸ࣒ᕤᏛ㒊kazama@ingrid.org⌧ᐇ♫఍࡟࠾ࡅࡿே㛫㛵ಀࡸ㸪Web࣮࣌ࢪࡢࣁ࢖ࣃ࣮ࣜࣥ
ࢡࢿࢵࢺ࣮࣡ࢡ㸪Twitterࡸmixi࡜࠸ࡗࡓWebࢧ࣮ࣅࢫୖ࡛ࡢ
ࢯ࣮ࢩ࣭ࣕࣝࢿࢵࢺ࣮࣡ࢡ࡟ᑐࡍࡿ㛵ᚰࡀ㧗ࡲࡗ࡚࠸ࡿ㸬ࡇࢀࡽ࡟௦⾲ࡉࢀࡿ⌧ᐇࢿࢵࢺ࣮࣡ࢡ࡟࠾࠸࡚㸪ྛࣀ࣮ࢻࡣᆒ㉁࡛ࡣ࡞ࡃ㸪ᅛ᭷ࡢ❧ሙࡸᙺ๭㸪ᶵ⬟ࢆ᭷ࡋ࡚࠸ࡿ࡜᝿ᐃࡉ
ࢀࡿ㸬ྛࣀ࣮ࢻࡢ≉ᚩ࡟ᇶ࡙ࡁ㸪ከ኱࡞ࣀ࣮ࢻ⩌࠿ࡽ㢮ఝࡍࡿࣀ࣮ࢻࢆⓎぢࡋࡓࡾ㸪㔜せࣀ࣮ࢻࢆᢳฟࡍࡿࡓࡵࡢᡭἲ
[1]ࡀᥦ᱌ࡉࢀ࡚࠸ࡿ㸬ࢿࢵࢺ࣮࣡ࢡᵓ㐀࡟㛵ࡋ࡚ࡶ඲యࡀ
ᆒ➼࡛ࡣ࡞ࡃ㸪ࣜࣥࢡࡀᐦ࡞㒊ศࡶ࠶ࢀࡤ␯࡞㒊ศࡶ࠶ࡾ㸪ࢥ࣑ࣗࢽࢸ࢕ᵓ㐀ࢆ᭷ࡍࡿࡇ࡜ࡀᣦ᦬ࡉࢀ࡚࠸ࡿ[2]㸬
᪤Ꮡࡢࢥ࣑ࣗࢽࢸ࢕ᢳฟᡭἲ࡜ࡋ࡚㸪 Newmanࡽ࡟ࡼࡿModularity࡜࠸࠺ࢿࢵࢺ࣮࣡ࢡศ๭ᣦᶆࢆ⏝࠸ࡓࢥ࣑ࣗࢽ
ࢸ࢕ᢳฟᡭἲࡀ㧗㏿࡛㸪኱つᶍࢿࢵࢺ࣮࣡ࢡ࡟ᑐࡋ࡚ࡶ᭷ຠ
࡛࠶ࡾὀ┠ࢆᾎࡧ࡚࠸ࡿ[3]㸬ࡇࡢᡭἲࡣ㸪ࣀ࣮ࢻྠኈࡢ⤖ྜࡀ␯࡞㒊ศࢆษ᩿ࡋ㸪࠸ࡃࡘ࠿ࡢࢧࣈࢿࢵࢺ࣮࣡ࢡ࡟ศ๭
ࡍࡿ᪉ἲ࡛࠶ࡿ㸬ࡲࡓ㸪ࢿࢵࢺ࣮࣡ࢡୖ࡛ࡢࣀ࣮ࢻྠኈࡀᐦ
⤖ྜࡋࡓࢧࣈࢿࢵࢺ࣮࣡ࢡࢆࢥ࣑ࣗࢽࢸ࢕࡜ぢ࡞ࡋ࡚㸪ࢡ࣮ࣜࢡ(clique)ࡢ᮲௳ࢆ⦆ࡵࡓࢧࣈࢿࢵࢺ࣮࣡ࢡࢆࡳࡘࡅࡿ
ࡓࡵࡢᡭἲࡶᥦ᱌ࡉࢀ࡚࠸ࡿ[4][5][6]㸬ࡇࢀࡽࡢᡭἲࡣ㸪ࣜࣥࢡᵓ㐀ࡢ⢒ᐦ࡟╔┠ࡋ㸪ࢧࣈࢿࢵࢺ࣮࣡ࢡࢆᢳฟࡍࡿ㸬ࡲࡓ㸪ࢿࢵࢺ࣮࣡ࢡ඲య࡟ᑐࡍࡿ኱ᇦⓗ࡞ᙺ๭ࡀ㢮ఝࡍࡿࣀ࣮ࢻ⩌ࢆࢥ࣑ࣗࢽࢸ࢕࡜ࡋࡓᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ࡀ࠶ࡿ
[7][8]㸬ⴭ⪅ࡽࡢᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟἲࡣ㸪ࢿࢵࢺ࣮࣡ࢡ
ୖ࡛ࡢࣛࣥࢲ࣒࢛࣮࢘ࢡ࡟╔┠ࡋ㸪PageRankࢫࢥ࢔ࡢ཰᮰㐣⛬࡟࠾ࡅࡿྛࣀ࣮ࢻࡢࢫࢸࢵࣉࡈ࡜ࡢࢫࢥ࢔ࢆ≉ᚩ࣋ࢡࢺࣝ࡜ࡋ㸪ࡑࡢ㢮ఝᗘ࡟ᇶ࡙ࡁࣀ࣮ࢻࢆศ㢮ࡍࡿᡭἲ࡛࠶ࡿ㸬ᩥ⊩[7]࡛ࡣ㸪ேᕤࢿࢵࢺ࣮࣡ࢡ࠾ࡼࡧࣁ࢖ࣃ࣮ࣜࣥࢡࢿࢵ
ࢺ࣮࣡ࢡࢆᑐ㇟࡟㸪Newmanࡽࡢ᪉ἲ࡟ࡼࡿࢥ࣑ࣗࢽࢸ࢕ᢳฟ
⤖ᯝ࡜ᥦ᱌ᡭἲ࡟ࡼࡿᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ࡢ㐪࠸ࢆᐃᛶⓗ࡟ホ౯ࡋ㸪ᚑ᮶ࡢࢥ࣑ࣗࢽࢸ࢕ᢳฟ⤖ᯝ࡜ࡣ␗࡞ࡿ㸪ጇᙜ࡞ᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ࡀᢳฟ࡛ࡁࡿࡇ࡜ࢆ♧ࡋࡓ㸬ᩥ⊩[8]࡛ࡣ㸪ᒁᡤⓗ࡞ࣜࣥࢡᵓ㐀ࡢ㢮ఝᛶࡢᴫᛕ࡜ࡋ࡚ᵓ㐀ྠ್ࡸṇ๎ྠ್ࢆྲྀࡾୖࡆ㸪ࡑࢀࡽࢆ㏆ఝⓗ࡟ᢳฟࡍࡿᡭἲ࡜ᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟἲࡢ㐪࠸ࢆホ౯ࡋࡓ㸬ᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟἲ
ࡣ㸪඲ࣀ࣮ࢻࢆᑐ➼࡟ᢅ࠸㸪ࢿࢵࢺ࣮࣡ࢡ඲యࢆᐈほどࡋࡓ㝿ࡢྛࣀ࣮ࢻࡢᶵ⬟࡟ᇶ࡙ࡃᡭἲ࡛࠶ࡿ࡜ゝ࠼ࡿ㸬౛࠼ࡤ㸪఍♫⤌⧊ෆࡢே㛫㛵ಀࢿࢵࢺ࣮࣡ࢡ࡛ࡣ㸪♫㛗࡜࠸࠺㝵ᒙୖࡢࢺࢵࣉࣀ࣮ࢻ࠿ࡽ㡰࡟㸪㒊㛗㸪ㄢ㛗ࡢࡼ࠺࡟ࡑ
ࢀࡒࢀࡢࣀ࣮ࢻ࡟㝵ᒙⓗᆅ఩ࡸᙺ๭ࡀ࠶ࡿ㸬ྠᵝ࡟Web࣮࣌ࢪࡢࣁ࢖ࣃ࣮ࣜࣥࢡࢿࢵࢺ࣮࣡ࢡ࡛ࡶ㸪ࢺࢵࣉ࣮࣌ࢪ࡜࠸࠺
㝵ᒙୖࡢࢺࢵࣉࣀ࣮ࢻ࠿ࡽ㡰࡟㸪ࢥࣥࢸࣥࢶࡢ୍ぴࢆ♧ࡍ࣮࣌ࢪ㸪ࢥࣥࢸࣥࢶࡢヲ⣽ෆᐜࡢ࣮࣌ࢪ࡞࡝ࡢࡼ࠺࡟㸪ࡑࢀࡒࢀࡢࣀ࣮ࢻ࡟㝵ᒙࡸᙺ๭ࡀ࠶ࡿ㸬ࡇࢀࡽࡢබᘧⓗ࡞ᙺ๭ࡔࡅ
࡛࡞ࡃ㸪㒊㛛ෆ࡟እ㒊࠿ࡽࡢ᝟ሗࢆఏ㐩ࡍࡿᙺ๭ࡢ፹௓ᗘࡢ
㧗࠸♫ဨࡸ㸪ᑠࢢ࣮ࣝࣉෆ࡛ࡢࣁࣈⓗᙺ๭ࡢ♫ဨ࡞࡝㸪㠀බᘧ࡟ᐃࡲࡿᶵ⬟ࡀ㢮ఝࡍࡿࣀ࣮ࢻࡶྠᐃࡍࡿ㸬ࡓࡔࡋ㸪ࣀ࣮ࢻࡢᙺ๭࣭ᶵ⬟ࡣどⅬࢆኚ࠼ࡿࡇ࡜࡟ࡼࡗ࡚
ኚ໬ࡍࡿࡇ࡜ࡀ࠶ࡿ㸬౛࠼ࡤ㸪఍♫⤌⧊ෆࡢே㛫㛵ಀࢿࢵࢺ࣮࣡ࢡ࡛ࡣ㸪♫㛗ࡣ⤯ᑐⓗ࡞ࢺࢵࣉࣀ࣮ࢻ࡛࠶ࡾ㸪௚ࡢࣀ࣮ࢻ࠿ࡽぢ࡚ࡶ❧ሙࡀኚ໬ࡋ࡞࠸㸬ࡋ࠿ࡋ㸪㒊㛗ࡸㄢ㛗࡞࡝ࡣ⮬㒊㛛࡜௚㒊㛛࡛ࡣ㸪⮬㌟࠿ࡽぢࡓᙺ๭࣭ᶵ⬟ࡣ␗࡞ࡿ㸬ࡲࡓ㸪⮬㒊㛛ෆࡢ♫ဨ࡞࡝⮬㌟ࡢ㏆ࡃࡢࣀ࣮ࢻࡣ㸪┤᥋ⓗ࡞┦஫㛵ಀࡀẚ㍑ⓗ኱ࡁ࠸ࡓࡵᶵ⬟ࢆ⣽࠿ࡃศ㢮ࡍࡿᚲせࡀ࠶ࡿࡀ㸪⮬㌟ࡢ㐲ࡃࡢࣀ࣮ࢻࡣ┦஫㛵ಀࡀẚ㍑ⓗᑠࡉ࠸ࡓࡵ㸪⣽࠿ࡃศ㢮ࡍࡿᚲせࡀ࡞࠸㸬ࡃࡔࡅࡓゝ࠸᪉ࢆࡍࡿ࡜㸪͆ಶ

1― 27 ―

᪥ᮏ䝕䞊䝍䝧䞊䝇Ꮫ఍ㄽᩥㄅ Vol.11, No.3
日本データベース学会論文誌 Vol.11,
2013 ᖺ No.3
2᭶
2013年 2月

一般論文
୍⯡ㄽᩥ

‫ݡࡍ࡛ࣝࣉࣥࢧ࡛ࡲࡃ࠶ࡣࢀࡇݡ‬ே࠿ࡽぢࢀࡤ㐲ࡃࡢࣀ࣮ࢻࡣࡳࢇ࡞୍⥴࡟ぢ࠼ࡿ͇ࡇ࡜࡟࡞
ࡿ㸬ᮏ✏࡛ࡣࡇࢀࡽࡢⅬ࡟╔┠ࡋ㸪ಶࠎࡢࣀ࣮ࢻࡢどⅬ࠿ࡽぢࡓᶵ⬟࡟ᇶ࡙ࡃࣃ࣮ࢯࢼࣛ࢖ࢬᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟἲࢆ
ᥦ᱌ࡍࡿ㸬ලయⓗ࡟ࡣ㸪ᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟἲ࡟࠾ࡅࡿ
PageRankィ⟬ࡢึᮇ࣋ࢡࢺࣝ࡟ࣂ࢖࢔ࢫࢆຍ࠼㸪ࡉࡽ࡟࢚ࢦ
ࢪࣕࣥࣉ࡜࿧ࡪᶵᵓࢆᑟධࡍࡿ㸬ேᕤࢿࢵࢺ࣮࣡ࢡ࠾ࡼࡧᐇ
ࢿࢵࢺ࣮࣡ࢡࢆ⏝࠸ࡓホ౯ᐇ㦂ࡼࡾ㸪㑅ᢥࡉࢀࡓࣀ࣮ࢻ㸦࢚ࢦࣀ࣮ࢻ㸧ࡢどⅬ࡟ᇶ࡙ࡃᶵ⬟ࡢ㢮ఝࡍࡿࢥ࣑ࣗࢽࢸ࢕ࢆᢳ
ฟ࡛ࡁࡿࡇ࡜ࢆ♧ࡍ㸬ᮏ✏ࡣ௨ୗࡢࡼ࠺࡞ᵓᡂ࡛࠶ࡿ㸬2⠇࡛㏻ᖖࡢᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟ࢔ࣝࢦࣜࢬ࣒࠾ࡼࡧ୺せᢏ⾡࡛࠶ࡿPageRankࢫ
ࢥ࢔ኚ໬᭤⥺࡜K-medianἲ࡟ࡘ࠸࡚ㄝ᫂ࡍࡿ㸬3⠇࡛ࣃ࣮ࢯࢼࣛ࢖ࢬᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟἲ࡬ࡢᣑᙇⅬ࡟ࡘ࠸࡚㏙࡭ࡿ㸬ࡑࡋ࡚㸪ᥦ᱌ἲࡢྍど໬࡟ࡼࡿホ౯ᐇ㦂ࡢ⤖ᯝࢆ4⠇࡛♧ࡍ㸬᭱ᚋ࡟ᮏ◊✲ࡢࡲ࡜ࡵ࡜௒ᚋࡢᒎᮃࢆ5⠇࡛㏙࡭ࡿ㸬

2. ᶵ⬟䝁䝭䝳䝙䝔䜱ᢳฟἲࡇࡢ⠇࡛ࡣ㸪ࣀ࣮ࢻࡢᶵ⬟࡟╔┠ࡋ㸪ᶵ⬟ࡢ㢮ఝࡍࡿࣀ࣮
ࢻ⩌࠿ࡽᵓᡂࡉࢀࡿᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ࢆᢳฟࡍࡿ᪉ἲ࡟ࡘ
࠸࡚ㄝ᫂ࡍࡿ㸬ᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟἲࡣ㸪ࣀ࣮ࢻ㞟ྜ V㸪ࣜࣥࢡ㞟ྜ E࠿ࡽ࡞ࡿࢿࢵࢺ࣮࣡ࢡ G=(V, E) ࡜ࢥ࣑ࣗࢽࢸ࢕ᩘ K ࢆධຊ࡜ࡋ㸪௨ୗࡢࡼ࠺࡞࢔ࣝࢦࣜࢬ࣒࡟ࡼࡾᶵ⬟ࢥ࣑ࣗࢽࢸ࢕
ࢆᢳฟࡍࡿ㸬
1.

ྛࢫࢸࢵࣉ࡛ࡢ PageRank ࢫࢥ࢔࣋ࢡࢺࣝ {y1«yS }ࢆィ⟬;ྛࣀ࣮ࢻࡢ≉ᚩ࣋ࢡࢺࣝ࡜ࡋ࡚ PageRank ࢫࢥ࢔ኚ໬
᭤⥺ xv ࢆᵓ⠏;ྛࣀ࣮ࢻ࣌࢔ࡢ≉ᚩ࣋ࢡࢺࣝ xu ࡜ xv ࡢࢥࢧ࢖ࣥ㢮ఝᗘ ߩ(u, v) ࢆィ⟬;K-median ἲ࡟ࡼࡾ඲ࣀ࣮ࢻࢆ K ಶࡢࢢ࣮ࣝࣉ࡟ศ
๭;ᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ {C1, «, CK} ࢆฟຊ;

2.
3.
4.
5.

௨ୗ࡟ヲ⣽ࢆㄝ᫂ࡍࡿ㸬

2.1 PageRank 䝇䝁䜰ኚ໬᭤⥺ᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟἲ࡛ࡣ㸪Web࣮࣌ࢪࡢࣛࣥ࢟ࣥࢢ࢔
ࣝࢦࣜࢬ࣒࡜ࡋ࡚⏝࠸ࡽࢀPageRank[9]࡟࠾࠸࡚㸪ྛࣀ࣮ࢻࡢPageRankࢫࢥ࢔ࡀ཰᮰ࡍࡿࡲ࡛ࡢࢫࢸࢵࣉࡈ࡜ࡢࢫࢥ࢔
ࢆྛࣀ࣮ࢻࡢ≉ᚩ࣋ࢡࢺࣝ࡜ࡋ࡚᥇⏝ࡍࡿ㸬↓ྥࢿࢵࢺ࣮࣡ࢡ G = (V, E) ࡢྛࣀ࣮ࢻ࡟ 1 ࠿ࡽ |V|ࡲ࡛ࡢᩚᩘ್ࢆ୍ព࡟๭ࡾ᣺ࡿ.ࡇࡇ࡛㸪(u,v) Ѯ E ࡢ࡜ࡁa(u,v) = 1㸪ࡑࢀ௨እࡢ࡜ࡁ a(u,v) = 0࡜ࡋ㞄᥋⾜ิ A Ѯ{0,1}|V|×|V| ࢆᐃ⩏ࡍࡿ.ྛࣀ࣮ࢻ u Ѯ V ࡟ᑐࡋ࡚㸪 ī u) ࢆࣀ࣮ࢻ u ࡢ㞄᥋ࣀ࣮ࢻ㞟ྜ࡜ࡍࡿ㸬ࡍ࡞ࢃࡕ㸪ī u) = {v ѮV ; (u, v) Ѯ E}࡜࡞ࡿ㸬ࡇࡇ࡛㸪⾜᥎⛣☜⋡⾜ิ P ࡢྛせ⣲ࡣ㸪 p(u,v) = a(u,v)/|ī u)| ࡛࠶ࡿ㸬㏻ᖖ㸪|ī u)| ࢆࣀ࣮ࢻ u ࡢḟᩘ࡜࠸࠺㸬ྛࣀ࣮ࢻࡢPageRankࢫࢥ࢔ࢆせ⣲࡜ࡍࡿ࣋ࢡࢺࣝ y ࡣ‫ݕ‬ሺ‫ݒ‬ሻ ൒ 0 ࡛ σ‫ݕ ܸאݒ‬ሺ‫ݒ‬ሻ ൌ 1 ࡜࡞ࡿ.⧞ࡾ㏉ࡋࢫࢸࢵࣉࡢࣃ࣓࣮ࣛࢱ s ࢆ⏝࠸㸪PageRankࢫࢥ࢔࣋ࢡࢺࣝ y ࡣ௨ୗࡢ᭦᪂ᘧࡢᴟ㝈ศᕸ࡜ࡋ࡚ᐃ⩏ࡉࢀࡿ:ܶܶ‫ ݏܡ‬ൌ ‫ିݏܡ‬1 ‫۾‬

(1)

DBSJ
Vol.11,DBSJ Journal,
Journal,Vol.
11,No.3
No.3
February
February 20132013‫ ݏݕ‬൫‫ݑ‬൯ ൌ ෍‫אݒ‬Ȟ൫‫ݑ‬൯ൌ ෍ ൝‫אݒ‬Ȟሺ‫ݑ‬ሻቄ‫ିݏݕ‬1 ൫‫ݒ‬൯‫݌‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻቅ‫ିݏݕ‬1 ሺ‫ݒ‬ሻหȞሺ‫ݒ‬ሻหൡ ሺ2ሻ

࡛ィ⟬ࡉࢀࡿ㸬཯᚟ᅇᩘ S ࡲ࡛཯᚟ࢆ⧞ࡾ㏉ࡋ㸪ྛࢫࢸࢵࣉ࡛ࡢࣀ࣮ࢻ u ࡢPageRankࢫࢥ࢔ࢆせ⣲࡜ࡋࡓ࣋ࢡࢺࣝࢆ
xu = (y1(u), y2(u),«, yS(u))T ࡜ᐃ⩏ࡍࡿ㸬ࡇࡢ࣋ࢡࢺࣝ xu ࢆࣀ࣮ࢻ u ࡢPageRankࢫࢥ࢔ኚ໬᭤⥺࡜࿧ࡪ㸬

2.2 K-median 䜽䝷䝇䝍䝸䞁䜾K-median㸦K-medoid࡜ࡶ࿧ࡤࢀࡿ㸧ἲࡣ㸪㠀㝵ᒙࢡࣛࢫࢱࣜࣥࢢ࡛᭷ྡ࡞K-meansἲ࡜ྠᵝ࡟㸪Nಶࡢ࢜ࣈࢪ࢙ࢡࢺ
ࡢ㞟ྜ V ࡀ୚࠼ࡽࢀࡓ࡜ࡁ㸪࢜ࣈࢪ࢙ࢡࢺ㞟ྜࢆKಶࡢࢡࣛࢫࢱ࡟ศ๭ࡍࡿᡭἲ࡛࠶ࡿ㸬௵ពࡢ࢜ࣈࢪ࢙ࢡࢺ࣌࢔
‫ݑ‬ǡ ‫ ܸ א ݒ‬㛫࡟㸪㐺ษ࡞㢮ఝᗘ ߩሺ‫ݑ‬ǡ ‫ݒ‬ሻ ࡀᐃ⩏ࡉࢀ࡚࠸ࡿ࡜௬
ᐃࡋ㸪࢜ࣈࢪ࢙ࢡࢺ㞟ྜࡢ୰࠿ࡽ௚ࡢ࢜ࣈࢪ࢙ࢡࢺ࡜ࡢ㢮ఝᗘࡢ࿴ࡀ㧗࠸௦⾲࢜ࣈࢪ࢙ࢡࢺࢆ㑅ᐃࡋ㸪㢮ఝᗘࡢ㧗࠸㸦㊥㞳ࡢᑠࡉ࠸㸧࢜ࣈࢪ࢙ࢡࢺ࣌࢔ࡣྠࡌࢡࣛࢫࢱ࡟㸪㢮ఝᗘࡢప࠸㸦㊥㞳ࡢ኱ࡁ࠸㸧࢜ࣈࢪ࢙ࢡࢺ࣌࢔ࡣ␗࡞ࡿࢡࣛࢫࢱ࡟
ᒓࡍࡿࡼ࠺࡟ศ๭ࡍࡿ㸬୍⯡ⓗ࡟ᖹᆒ(mean)ࡼࡾࡶ୰ኸ್
(median)ࡢ᪉ࡀ㡹೺࡛࠶ࡿࡓࡵ㸪K-medianἲࢆ᥇⏝ࡍࡿ㸬
K-medianࡢゎἲ࡟ࡣ཯᚟ἲࡸ㈎ḧἲࡀ࠶ࡿࡀ㸪ᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟἲ࡛ࡣゎࡢ୍ពᛶࡀಖドࡉࢀࡿ㈎ḧἲࢆ᥇⏝ࡍࡿ㸬ࡉࡽ࡟㈎ḧゎἲࡢ┠ⓗ㛵ᩘ㸦ᚋ㏙ࡍࡿ f 㸧ࡀࢧࣈࣔࢪࣗ
ࣛᛶࢆ᭷ࡍࡿࡇ࡜ࡼࡾ㸪ཝᐦゎ࡛ࡣ࡞࠸ࡶࡢࡢ㸪࠶ࡿ⛬ᗘጇᙜ࡞⢭ᗘ࡛᭱ᝏࢣ࣮ࢫࡢゎရ㉁ࡀ⌮ㄽⓗ࡟ಖドࡉࢀ࡚࠸ࡿ
[10]㸬㈎ḧἲ࡜ࡣ㸪᪤࡟㑅ᐃࡋࡓ௦⾲࢜ࣈࢪ࢙ࢡࢺࢆᅛᐃࡋ㸪࠶ࡿ┠ⓗ㛵ᩘ್ࢆ᭱኱࡟ࡍࡿ࢜ࣈࢪ࢙ࢡࢺࢆồࡵ㸪┠ⓗ㛵ᩘࡀቑຍࡍࡿ࡞ࡽࡤ௦⾲࢜ࣈࢪ࢙ࢡࢺ㞟ྜ࡟㏣ຍࡍࡿࡇ࡜࡛㸪⤖ᯝࡢ௦⾲࢜ࣈࢪ࢙ࢡࢺ㞟ྜࢆồࡵࡿ᪉ἲ࡛࠶ࡿ㸬ྛ࢜ࣈࢪ࢙ࢡࢺࡣ㸪᭱ࡶ㢮ఝᗘࡢ㧗࠸௦⾲࢜ࣈࢪ࢙ࢡࢺ࡜ྠࡌࢡࣛࢫ
ࢱ࡟๭ࡾᙜ࡚ࡽࢀࡿ㸬᪤࡟㑅ᐃࡋࡓ௦⾲࢜ࣈࢪ࢙ࢡࢺ㞟ྜࢆP ࡜ࡋ㸪᪂ࡓ࡟㏣ຍࢆヨࡳࡿ࢜ࣈࢪ࢙ࢡࢺࢆ w ࡜ࡍࡿ࡜ࡁ㸪௨ୗࡢ┠ⓗ㛵ᩘࢆ⪃࠼ࡿ㸬݂൫ܲ ‫ ׫‬൛‫ݓ‬ൟ൯ ൌ σ௩‫א‬௏ ሼߤሺ‫ݒ‬ǡ ܲሻǡ ߩሺ‫ݒ‬ǡ ‫ݓ‬ሻሽǤ
(3)ࡇࡇ࡛㸪ߤሺ‫ݒ‬ǡ ܲሻ ࡣ᪤࡟㑅ᐃࡉࢀࡓ௦⾲࢜ࣈࢪ࢙ࢡࢺ࡜ࡢ㢮ఝᗘࡢ᭱኱್ࢆ⾲ࡋ㸪ߤሺ‫ݒ‬ǡ ܲሻ ൌ ௪‫א‬௉ ሼߩሺ‫ݒ‬ǡ ‫ݓ‬ሻሽ ࡛ᐃ⩏ࡉࢀࡿ㸬௨ୗ࡟㈎ḧἲ࡟ࡼࡿK-medianἲࡢ࢔ࣝࢦࣜࢬ࣒ࢆㄝ᫂
ࡍࡿ㸬
1.
2.

3.
4.

݇ ՚ 1ǡ ܲ0 ՚ ‫׎‬ǡ ྛ࢜ࣈࢪ࢙ࢡࢺ ‫࡟ ܸ א ݒ‬ᑐࡋ㸪ߤ൫‫ݒ‬Ǣ ‫׎‬൯ ՚ 0 ࡜ึᮇ໬ࡍࡿ㸹
ᘧ(3) ࡛ ‫݌‬෠ ൌ argmax
݇‫݇ܲךܸאݓ‬ష1

ቄ݂ ቀܲ݇ି1 ‫ڂ‬൛‫ݓ‬ൟቁቅ ࢆồࡵ㸪ܲ݇ ՚ ܲ݇ି1 ‫ ׫‬ቄ‫݌‬෠݇ ቅ ࡜ࡍࡿ㸹෡ ൌ ቄ‫݌‬෠ ǡ ‫ ڮ‬ǡ ‫݌‬෠ ቅ ࢆฟຊࡋ⤊஢ࡍࡿ㸹݇ ൌ ‫ܲ ࡤࡽ࡞ ܭ‬
‫ܭ‬

1

‫ܭ‬

ྛ࢜ࣈࢪ࢙ࢡࢺ ‫࡟ ܸ א ݒ‬ᑐࡋ㸪ߤ ቀ‫ݒ‬Ǣ ܲ݇ ቁ ࢆồࡵ㸪݇ ՚ ݇ ൅ 1 ࡜ࡋࢫࢸࢵࣉ 2. ࡬ᡠࡿ㸬ྛ࢜ࣈࢪ࢙ࢡࢺࢆ㸪᭱ࡶ㢮ఝᗘࡢ㧗࠸௦⾲࢜ࣈࢪ࢙ࢡࢺ
‫ ࢱࢫࣛࢡࡢܲ א ݇݌‬Ck ࡟๭ࡾᙜ࡚ࡿ㸬Tࡇࡇ࡛ b ࡣ࣋ࢡࢺࣝ b ࡢ㌿⨨ࢆ⾲ࢃࡍ㸬ࣀ࣮ࢻ u ࡟ὀ┠ࡍࡿ࡜㸪2― 28 ―

᪥ᮏ䝕䞊䝍䝧䞊䝇Ꮫ఍ㄽᩥㄅ Vol.11, No.3
日本データベース学会論文誌 Vol.11,
2013 ᖺ No.3
2᭶
2013年 2月

一般論文
୍⯡ㄽᩥ

‫ݡࡍ࡛ࣝࣉࣥࢧ࡛ࡲࡃ࠶ࡣࢀࡇݡ‬3. 䝟䞊䝋䝘䝷䜲䝈ᶵ⬟䝁䝭䝳䝙䝔䜱ᢳฟἲ㏻ᖖࡢᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ࡣ㸪ࡍ࡭࡚ࡢࣀ࣮ࢻࢆᑐ➼࡟ᢅ࠸㸪ࢿࢵࢺ࣮࣡ࢡ඲య࡟ᑐࡍࡿྛࣀ࣮ࢻࡢ኱ᇦⓗ࡞ᶵ⬟ࡢ㢮ఝᗘ࡟ࡼࡾᢳฟࡉࢀࡿ㸬ᮏ✏࡛ࡣ㸪࢚ࢦࣀ࣮ࢻࡢどⅬ࠿ࡽぢࡓ௚ࡢࣀ࣮ࢻࡢᶵ⬟࣭ᙺ๭ࡢ㢮ఝᗘ࡟ࡼࡾࢥ࣑ࣗࢽࢸ࢕ࢆᢳฟ
ࡍࡿ᪉ἲࢆ㸪Personalized PageRank[11]ࢆᇶ࡟ࡋ࡚ᥦ᱌ࡍ
ࡿ㸬
どⅬࡢཎⅬ࡜࡞ࡿ╔┠ࡍࡿࣀ࣮ࢻࢆ࢚ࢦࣀ࣮ࢻ࡜࿧ࡧ㸪࢚ࢦࣀ࣮ࢻ㞟ྜࢆ R ӨV ࡜⾲ࡍ㸬PageRank ࢫࢥ࢔ィ⟬ࡢึᮇ࣋ࢡࢺࣝࢆ y0 Ѯ{0, |R|-1}|V| ࡛ᐃࡵࡿ㸬ణࡋ㸪

­ 1
if v  R°
y 0 (v ) ® | R |°̄ 0 otherwise࡜ࡍࡿ㸬ࡇࢀ࡟ࡼࡾ㸪཯᚟ィ⟬ࡢึᮇẁ㝵࡛ࡣ㸪࢚ࢦࣀ࣮ࢻ
࠾ࡼࡧࡑࡢ࿘㎶ࣀ࣮ࢻࡢࡳࡀ್ࢆᣢࡕ㸪㐲ࡃࡢࣀ࣮ࢻࡣ 0ࡢࡲࡲ࡜࡞ࡿ㸬࿘㎶ࣀ࣮ࢻࡣ㸪࢚ࢦࣀ࣮ࢻ࡜ࡢ㛵ಀ㸦ᒁᡤⓗ࡞ࣜࣥࢡᵓ㐀㸧࡟ࡼࡾ㸪≉ᚩ࣋ࢡࢺ࡛ࣝ࠶ࡿ PageRank ࢫࢥ࢔ኚ໬᭤⥺ࡀኚືࡍࡿࡓࡵ㸪࢚ࢦࣀ࣮ࢻ࠿ࡽぢࡓྛࣀ࣮ࢻࡢ
ᶵ⬟࣭ᙺ๭ࢆ⾲ࡍࡇ࡜ࡀ࡛ࡁࡿ࡜⪃࠼ࡽࢀࡿ㸬཯᚟ࢆ⧞ࡾ㏉ࡍ࡟ᚑ࠸㸪㐲ࡃࡢࣀ࣮ࢻ࡟ࡶ್ࡀఏ᧛ࡋ㸪ྠᵝ࡟࢚ࢦࣀ࣮ࢻ
࡜ࡢ㛵ಀ࡞࡝࡟ࡼࡾ PageRank ࢫࢥ࢔ኚ໬᭤⥺ࡀኚືࡍࡿ㸬ࡇࡢᣑᙇ࡟ຍ࠼㸪PageRank ࢫࢥ࢔ィ⟬࡟࢚ࢦࢪࣕࣥࣉ࡜
࿧ࡪᶵᵓࢆᥦ᱌࣭ᑟධࡍࡿ㸬࢚ࢦࢪࣕࣥࣉ࡜ࡣ㸪࣐ࣝࢥࣇ㐃㙐ࡢ㐣⛬࡟࠾࠸࡚㸪௵ពࡢࣀ࣮ࢻ࠿ࡽ࢚ࢦࣀ࣮ࢻ࡬☜⋡ ߚ࡛ࢪࣕࣥࣉࡍࡿࡇ࡜࡛࠶ࡿ㸬⧞ࡾ㏉ࡋࢫࢸࢵࣉࡢࣃ࣓࣮ࣛࢱs ࢆ⏝࠸㸪ࣃ࣮ࢯࢼࣛ࢖ࢬᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟἲ࡛ࡢ
PageRank ࢫࢥ࢔࣋ࢡࢺࣝ y ࡢ᭦᪂ᘧࢆ௨ୗࡢࡼ࠺࡟ᐃ
⩏ࡍࡿ:

y Ts

y Ts1 1  E P  EezT
1  E y Ts1P  Ez T(4)ࡇ ࡇ ࡛ z Ѯ {0, |R|-1}|V| ࡛ ࠶ ࡿ . z ࡣ z(v) ൒ 0 ࡛σ௩‫א‬௏ ‫ݖ‬ሺ‫ݒ‬ሻ ൌ ͳ ࢆ‶ࡓࡍ㸬ࡲࡓ㸪ࣀ࣮ࢻ u ࡢࢫࢥ࢔࡟ὀ┠ࡍࡿ࡜㸪y s (u )1 E¦^y (v)  p(v, u)` E  z(u)v* ( u )

1 E

s 1

­° y s 1 (v) ½°®
¾  E  z (u )¦v* ( u ) °̄ *(v ) °
¿

(5)

DBSJ
Vol.11,DBSJ Journal,
Journal,Vol.
11,No.3
No.3
February
February 20132013㸦ࣛࣥࢲ࣒ࢧ࣮ࣇ࢓࣮ࢪࣕࣥࣉ㸧㸬ࡋࡓࡀࡗ࡚㸪Brin ࡽ࡟ࡼࡾᥦ᱌ࡉࢀࡓ࢜ࣜࢪࢼࣝࡢ PageRank ࡜➼౯࡜࡞ࡾ㸪⮬↛࡞ᣑᙇ࡟࡞ࡗ࡚࠸ࡿ㸬

4. ホ౯ᐇ㦂ᮏ⠇࡛ࡣ㸪⌧ᐇࡢ Web ࢿࢵࢺ࣮࣡ࢡࢹ࣮ࢱ࡞࡝ࢆᑐ㇟࡟㸪ᥦ᱌ἲࢆ⏝࠸࡚ࣃ࣮ࢯࢼࣛ࢖ࢬᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ࢆᢳฟࡍ
ࡿ㸬࠸ࡃࡘ࠿ࡢࣀ࣮ࢻࢆ࢚ࢦࣀ࣮ࢻ࡜ࡋ࡚㑅ᢥࡋ㸪ࢥ࣑ࣗࢽࢸ࢕ᢳฟ⤖ᯝࡢጇᙜᛶࢆྍど໬࡟ࡼࡾᐃᛶⓗ࡟ホ౯ࡍࡿ㸬

4.1 䝛䝑䝖䝽䞊䜽䝕䞊䝍ホ౯ᐇ㦂࡛ࡣ㸪ࣃ࣮ࢯࢼࣛ࢖ࢬᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟἲࡢ
≉ᛶ࠾ࡼࡧጇᙜᛶࢆホ౯ࡍࡿࡓࡵ࡟㸪ேᕤࢿࢵࢺ࣮࣡ࢡ࠾ࡼ
ࡧ 2 ࡘࡢᐇࢿࢵࢺ࣮࣡ࢡࢆ⏝࠸ࡿ.
1 ࡘ┠ࡢࢿࢵࢺ࣮࣡ࢡࡣ㸪Ravasz ࡽ࡟ࡼࡗ࡚ᥦ᱌ࡉࢀࡓ
㝵ᒙᛶࡢ࠶ࡿࢿࢵࢺ࣮࣡ࢡࢆ⏕ᡂࡍࡿ HN ࣔࢹࣝ࡟ࡼࡾ⏕ᡂࡋࡓேᕤࢿࢵࢺ࣮࣡ࢡ࡛࠶ࡿ[12]㸬㝵ᒙᛶࡢ࠶ࡿࢿࢵࢺ࣡
࣮ࢡ࡜ࡣ㸪௻ᴗෆࡢ♫ဨࡢࢿࢵࢺ࣮࣡ࢡࡸ Web ࢧ࢖ࢺࡢࣁ
࢖ࣃ࣮ࣜࣥࢡࢿࢵࢺ࣮࣡ࢡࡢࡼ࠺࡟ࢺࢵࣉࣀ࣮ࢻ࡜௚ࡢࡍ
࡭࡚ࡢࣀ࣮ࢻ㛫࡟ࡣࣜࣥࢡࡀᙇࡽࢀ࡚࠸ࡿࡀ㸪ࡑࡢ௚ࡢࣀ࣮
ࢻྠኈࡣ㝈ࡽࢀࡓ⠊ᅖ࡛ࡢࡳࣜࣥࢡࡀᙇࡽࢀ࡚࠸ࡿࡼ࠺࡞
ᵓ㐀ࢆᣢࡗ࡚࠸ࡿ㸬ࡍ࡞ࢃࡕࢺࢵࣉࣀ࣮ࢻ㸦♫㛗ࡸࢺࢵࣉ࣌
࣮ࢪ࡟┦ᙜࡍࡿࣀ࣮ࢻ㸧ࡣ㧗࠸ḟᩘࢆ᭷ࡋ࡚࠸ࡿࡀ㸪ࢡࣛࢫࢱಀᩘࡀ㠀ᖖ࡟ᑠࡉ࠸㸬୍᪉㸪ࡑࡢ௚ࡢࣀ࣮ࢻ㸦୍⯡♫ဨࡸ
ᬑ㏻ࡢ࣮࣌ࢪ࡟┦ᙜࡍࡿࣀ࣮ࢻ㸧ࡣప࠸ḟᩘࢆ᭷ࡋ࡚࠸ࡿࡀ㸪⊃࠸⠊ᅖෆ࡛ᐦ࡟ࡘ࡞ࡀࡗ࡚࠸ࡿࡓࡵࢡࣛࢫࢱಀᩘࡀ኱ࡁ
ࡃ࡞ࡿ㸬ᮏㄽᩥ࡛ࡣ Hierarchical ࢿࢵࢺ࣮࣡ࢡ࡜࿧ࡪ㸬2 ࡘ┠ࡢࢿࢵࢺ࣮࣡ࢡࡣ㸪ࢿࢵࢺ࣮࣡ࢡศᯒࡢ࣋ࣥࢳ࣐࣮
ࢡ࡜ࡋ࡚ᗈࡃ⏝࠸ࡽࢀ࡚࠸ࡿ㸪✵ᡭࢡࣛࣈෆࡢ཭ே㛵ಀࢿࢵࢺ࣮࣡ࢡ࡛࠶ࡿ[13]㸬♫఍ࢿࢵࢺ࣮࣡ࢡࡢ≉ᚩ࡛࠶ࡿࢫࢣ࣮
ࣝࣇ࣮ࣜᛶ࡜ࢫ࣮࣮ࣔࣝ࣡ࣝࢻᛶࢆ᭷ࡍࡿ㸬ࡇࡢࢿࢵࢺ࣮࣡
ࢡ࡟ࡣ㸪࢖ࣥࢫࢺࣛࢡࢱ࣮࡜࢔ࢻ࣑ࢽࢫࢺ࣮ࣞࢱࡢࡑࢀࡒࢀ
࠿ࡽ࡞ࡿ 2 ࡘࡢὴ㛸ࡀᏑᅾࡋ࡚࠸ࡿ㸬ᮏ✏࡛ࡣ Karate ࢿࢵࢺ࣮࣡ࢡ࡜࿧ࡪ㸬
3 ࡘ┠ࡢࢿࢵࢺ࣮࣡ࢡࡣ㸪Web ࡢࣁ࢖ࣃ࣮ࣜࣥࢡ࣭ࢿࢵ
ࢺ࣮࣡ࢡ࡛࠶ࡿ㸬኱Ꮫࡢ࢙࢘ࣈࢧ࢖ࢺෆࡢ࣮࣌ࢪࢆ 2010 ᖺ
8 ᭶࡟཰㞟ࡋ㸪࢙࢘ࣈࢧ࢖ࢺࡢࣁ࢖ࣃ࣮ࣜࣥࢡᵓ㐀࠿ࡽࣁ࢖ࣃ࣮ࣜࣥࢡࢿࢵࢺ࣮࣡ࢡࢆᵓ⠏ࡋ↓ྥ໬ࡋࡓ[14]㸬ᮏ✏࡛ࡣ㸪
Hosei ࢿࢵࢺ࣮࣡ࢡ࡜࿧ࡪ㸬

4.2 ᐇ㦂⤖ᯝ䛸⪃ᐹ࡛ィ⟬ࡉࢀࡿ㸬㏻ᖖࡢᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟἲ࡜ྠᵝ࡟㸪཯᚟ᅇᩘ S ࡲ࡛཯᚟ࢆ⧞ࡾ㏉ࡋ㸪ྛ཯᚟ᅇᩘ࡛ࡢࣀ࣮ࢻ u ࡢࢫࢥ࢔ࢆせ⣲࡜ࡋࡓ࣋ࢡࢺࣝࢆ xu = (y1(u), y2(u),«, yS(u))T ࡜ᐃ⩏ࡍࡿ㸬ࡇࡢ࣋ࢡࢺࣝ xu ࢆࣀ࣮ࢻ u ࡢ PageRank ࢫࢥ࢔ኚ໬᭤⥺࡜࿧ࡧࣀ࣮ࢻ u ࡢ≉ᚩ࣋ࢡࢺࣝ࡜ࡋ࡚ᢅ࠺㸬ᥦ᱌ἲ࡟࠾ࡅࡿึᮇ࣋ࢡࢺࣝࡢㄪᩚ࠾ࡼࡧ㸪࢚ࢦࢪࣕࣥࣉ
ࡢᑟධ࡟ࡼࡾ㸪㑅ᢥࡉࢀࡓ࢚ࢦࣀ࣮ࢻࡢ㏆ࡃ࡛ࡣ㸪ᒁᡤⓗ࡞ࣜࣥࢡᵓ㐀ࡀᙉࡃᙳ㡪ࡍࡿࡓࡵ⣽࠿ࡃศ㢮ࡉࢀࡿ㸬୍᪉࢚ࢦࣀ࣮ࢻࡢ㐲ࡃ࡛ࡣ㸪࢚ࢦࣀ࣮ࢻ࠿ࡽࡢ┤᥋ᙳ㡪ࡀᑡ࡞ࡃ㸪⢒ࡃศ㢮ࡉࢀࡿᮇᚅ࡛ࡁࡿ㸬ᮏ✏࡛ᣑᙇࡋࡓ PageRank ࢫࢥ࢔ኚ໬᭤⥺ࡢィ⟬ἲࡣ㸪࢚ࢦࣀ࣮ࢻ࡜ࡋ࡚ࢿࢵࢺ࣮࣡ࢡࡢ඲ࣀ࣮ࢻࢆ㑅ᢥࡋࡓሙྜ㸦R= V㸧
㸪ึᮇ࣋ࢡࢺࣝࡣ඲ࣀ࣮ࢻ࡛ᑐ➼࡜࡞ࡾ㸪࢚ࢦࢪࣕࣥࣉࡣ☜⋡ ߚ ࡛ࢿࢵࢺ࣮࣡ࢡ඲ᇦ࡟ࢪࣕࣥࣉࡍࡿࡇ࡜࡟࡞ࡿ

ୖ㏙ࡋࡓࢿࢵࢺ࣮࣡ࢡ࡟ᑐࡋ㸪཰᮰ุᐃᇶ‽ࢆԡ‫ܡ‬௦ െ ‫ܡ‬௦ିଵ ԡ୐ଵ ൑ ͳͲି଼ 㸪࢚ࢦࢪࣕࣥࣉ☜⋡ࢆߚ=0.0001㸪ࢥ࣑ࣗࢽࢸ࢕ᩘࢆ ʹ ൑ ‫ ܭ‬൑ ͳͲ࡜ࡋ㸪ᥦ᱌ἲ࡟ࡼࡿࣃ࣮ࢯࢼࣛ࢖
ࢬᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟ⤖ᯝࢆᅗ 1 ࠿ࡽᅗ 3 ࡟♧ࡍ㸬࡞࠾ㄝ᫂ࡢ౽ᐅୖ㸪᭱ࡶ㐺ษ࡜ᛮࢃࢀࡿࢥ࣑ࣗࢽࢸ࢕ᩘ K ࢆ㑅ᢥࡋ࡚࠸ࡿࡀ㸪௚ࡢ K ࡢሙྜ࡛ࡶ▩┪ࡢ࡞࠸⤖ᯝࡀᚓࡽࢀ࡚
࠸ࡿ㸬ᮏ✏࡛ࡣ㸪࢚ࢦࣀ࣮ࢻࢆ 1 ࡘ㑅ᢥࡋࡓ⤖ᯝࢆ♧ࡍ㸬

4.2.1 Hierarchical 䝛䝑䝖䝽䞊䜽䛾ฎ⌮⤖ᯝ

Hierarchical ࢿࢵࢺ࣮࣡ࢡࡢ⤖ᯝࢆᅗ 1(a)࠾ࡼࡧᅗ 1(b)࡟ࡑ
ࢀࡒࢀ♧ࡍ㸬ࡑࢀࡒࢀ࢚ࢦࣀ࣮ࢻࢆ㯮࠸୸࡛ᅖࡗ࡚࠸ࡿ㸬ࡇࡢࢿࢵࢺ࣮࣡ࢡࡢ≉ᚩࡣ㸪௻ᴗෆࡢ♫ဨࡢࢿࢵࢺ࣮࣡ࢡࡸ
Web ࢧ࢖ࢺࡢࣁ࢖ࣃ࣮ࣜࣥࢡࢿࢵࢺ࣮࣡ࢡࡢࡼ࠺࡟㝵ᒙᛶࢆ᭷ࡋ࡚࠸ࡿࡇ࡜࡛࠶ࡿ㸬㏻ᖖࡢᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟἲ࡛
ࡣ㸪㝵ᒙⓗᆅ఩ࡢࡼ࠺࡞ࢿࢵࢺ࣮࣡ࢡෆ࡛ࡢ኱ᇦⓗ࡞ᶵ⬟࣭ᙺ๭࡟ᇶ࡙࠸࡚ࣀ࣮ࢻࢆศ㢮࡛ࡁࡿ[7]㸬

3― 29 ―

᪥ᮏ䝕䞊䝍䝧䞊䝇Ꮫ఍ㄽᩥㄅ Vol.11, No.3
日本データベース学会論文誌 Vol.11,
2013 ᖺ No.3
2᭶
2013年 2月

一般論文
୍⯡ㄽᩥ

‫ݡࡍ࡛ࣝࣉࣥࢧ࡛ࡲࡃ࠶ࡣࢀࡇݡ‬DBSJ
Vol.11,DBSJ Journal,
Journal,Vol.
11,No.3
No.3
February
February 20132013(a) ࢚ࢦࣀ࣮ࢻ㸸ࢢ࣮ࣝࣉ࣮ࣜࢲ࣮㸦K=6㸧
(b) ࢚ࢦࣀ࣮ࢻ㸸᭱ୗᒙࣀ࣮ࢻ㸦K=9㸧
(a) Ego node : A group leader㸦K=6㸧
(b) Ego node : A node in the lowest layer㸦K=9㸧
ᅗ 1 Hierarchical 䝛䝑䝖䝽䞊䜽 ᶵ⬟䝁䝭䝳䝙䝔䜱ᢳฟ⤖ᯝ
Fig.1

Results of Functional Communities of Hierarchical Network(a) ࢚ࢦࣀ࣮ࢻ㸸ὴ㛸ࡢ࣮ࣜࢲ࣮㸦K=6㸧
(b) ࢚ࢦࣀ࣮ࢻ㸸ࡣࡎࢀࣀ࣮ࢻ㸦K=5㸧
(a) Ego node : A faction leader㸦K=6㸧
(b) Ego node : A fringe node㸦K=5㸧
ᅗ 2 Karate 䝛䝑䝖䝽䞊䜽 ᶵ⬟䝁䝭䝳䝙䝔䜱ᢳฟ⤖ᯝ
Fig.2

Results of Functional Communities of Karate Networkᅗ 1(a)ࡢ࢚ࢦࣀ࣮ࢻࡣ㸪఍♫⤌⧊࡛࠸࠺࡜㸪࠶ࡿࢢ࣮ࣝࣉ
ࡢ࣮ࣜࢲ࣮ⓗᏑᅾ࡛࠶ࡿ㸬࢚ࢦࣀ࣮ࢻࡢどⅬ࠿ࡽࡢᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟ⤖ᯝࢆぢࡿ࡜㸪࢚ࢦࣀ࣮ࢻࡢᒓࡍࡿࢢ࣮ࣝࣉ࣓
ࣥࣂ࣮㸦᱈‫ۻ‬㸧㸪࿘㎶ࢢ࣮ࣝࣉࡢࢢ࣮ࣝࣉ࣮ࣜࢲ࣮㸦㯤‫ی‬㸧࡜ࡑࡢ࣓ࣥࣂ࣮㸦⥳‫ڸ‬㸧㸪ࢺࢵࣉࣀ࣮ࢻ㸦㉥‫ە‬㸧ࡢࡼ࠺࡟㸪࢚ࢦࣀ࣮ࢻࡢ┤᥋㛵ಀࡍࡿࣀ࣮ࢻࢆࡑࡢᙺ๭࡟ࡼࡾ⣽࠿ࡃศ㢮ࡋ࡚࠸ࡿ㸬୍᪉㸪࢚ࢦࣀ࣮ࢻ࠿ࡽ㐲ࡃ࡟Ꮡᅾࡍࡿࣀ࣮ࢻ
⩌ࡣ 2 ࡘࡢࢥ࣑ࣗࢽࢸ࢕㸦㟷‫࡜ڦ‬Ỉ 㸧࡟⢒ࡃศ㢮ࡉࢀ࡚࠸ࡿ㸬
ᅗ 1(b)ࡢ࢚ࢦࣀ࣮ࢻࡣ㸪఍♫⤌⧊࡛࠸࠺࡜㸪୍⯡♫ဨ࡟┦ᙜࡍࡿࣀ࣮ࢻ࡛࠶ࡿ㸬࢚ࢦࣀ࣮ࢻࡢどⅬ࠿ࡽࡢᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟ⤖ᯝࢆぢࡿ࡜㸪ྠ୍ࢢ࣮ࣝࣉෆࡢ௚ࡢ୍⯡♫ဨ㸦⥳‫ڸ‬㸧࡜ࢢ࣮ࣝࣉ࣮ࣜࢲ࣮㸦ᶳ 㸧㸪୍㝵ᒙୖࡢࢢ࣮ࣝࣉ࣮ࣜ
ࢲ࣮㸦᱈‫ۻ‬㸧㸪ྠ୍㝵ᒙࡢ௚ࢢ࣮ࣝࣉࡢ࣮ࣜࢲ࣮㸦Ⲕ 㸧࡜୍⯡♫ဨ㸦㟷‫ڦ‬㸧ࡢࡼ࠺࡟⣽࠿ࡃศ㢮ࡉࢀࡿ㸬୍᪉㸪࢚ࢦࣀ࣮ࢻ࠿ࡽ㐲ࡃ࡟Ꮡᅾࡍࡿࣀ࣮ࢻ⩌ࡢከࡃࡣ 1 ࡘࡢࢥ࣑ࣗࢽࢸ

࢕㸦Ỉ‫ۂ‬㸧࡜ࡋ࡚⢒ࡃศ㢮ࡉࢀࡿ㸬
㏻ᖖࡢᶵ⬟ࢥ࣑ࣗࢽࢸ࢕࡛ࡣ㸪㢮ఝࡋࡓᶵ⬟ࡢࣀ࣮ࢻࡣྠ
୍ࢥ࣑ࣗࢽࢸ࢕࡟ᒓࡍࡿ[7]㸬ࣃ࣮ࢯࢼࣛ࢖ࢬᶵ⬟ࢥ࣑ࣗࢽࢸ
࢕࡛ࡣ㸪ྠࡌᶵ⬟ࡢࣀ࣮ࢻ࡛ࡶ㸪࢚ࢦࣀ࣮ࢻ࡜ࡢ㊥㞳ࡀ㐪࠺࡜ྠ୍ࢥ࣑ࣗࢽࢸ࢕࡜ุᐃࡉࢀ࡞࠸⤖ᯝࡀᚓࡽࢀࡓ㸬

4.2.2 Karate 䝛䝑䝖䝽䞊䜽䛾ฎ⌮⤖ᯝ

Karate ࢿࢵࢺ࣮࣡ࢡࡢ⤖ᯝࢆᅗ 2(a)࡜ᅗ 2(b)࡟ࡑࢀࡒࢀ
♧ࡍ㸬ࡑࢀࡒࢀ࢚ࢦࣀ࣮ࢻࢆ㯮࠸୸࡛ᅖࡗ࡚࠸ࡿ㸬Karateࢿࢵࢺ࣮࣡ࢡࡣ㸪㝵ᒙᛶࡀどㄆ࡛ࡁࡿࡼ࠺㸪ࡤࡡࣔࢹࣝ࡟ࡼࡾྍど໬ࡋࡓ[15]㸬ࡇࡢࢿࢵࢺ࣮࣡ࢡࡢ≉ᚩࡣ㸪2 ࡘࡢὴ㛸ࡀᏑᅾࡋ㸪ᅗ୰࡟♧ࡍࣀ࣮ࢻࡀྛὴ㛸ࡢ࣮ࣜࢲ࣮࡛࠶ࡾ㸪௚ࡢࣀ࣮ࢻࡣ࡝ࡕࡽ࠿ࡢὴ㛸࡟ᡤᒓࡋ࡚࠸ࡿⅬ࡛࠶ࡿ㸬ᅗ୰ࡢ
Ⅼ⥺ࡣὴ㛸ࡢቃ⏺ࢆ⾲ࡋ࡚࠸ࡿ㸬㏻ᖖࡢᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳ
ฟἲ࡛ࡣ㸪ࣁࣈࣀ࣮ࢻ㸦ὴ㛸ࡢ࣮ࣜࢲ࣮㸧࡜ࡑࡢ௚ࡢࡼ࠺࡞
ࢿࢵࢺ࣮࣡ࢡෆ࡛ࡢ኱ᇦⓗ࡞ᶵ⬟࣭ᙺ๭࡟ᇶ࡙࠸࡚ࣀ࣮ࢻࢆ
ศ㢮࡛ࡁࡿ[8]㸬

4― 30 ―

᪥ᮏ䝕䞊䝍䝧䞊䝇Ꮫ఍ㄽᩥㄅ Vol.11, No.3
日本データベース学会論文誌 Vol.11,
2013 ᖺ No.3
2᭶
2013年 2月

一般論文
୍⯡ㄽᩥ

‫ݡࡍ࡛ࣝࣉࣥࢧ࡛ࡲࡃ࠶ࡣࢀࡇݡ‬DBSJ
Vol.11,DBSJ Journal,
Journal,Vol.
11,No.3
No.3
February
February 20132013(a) ࢚ࢦࣀ࣮ࢻ㸸ࢩࣛࣂࢫ㸦K=10㸧
(b) ࢚ࢦࣀ࣮ࢻ㸸ᩍဨᡂᯝሗ࿌࣮࣌ࢪ㸦K=10㸧
(a) Ego node : A syllabus page㸦K=10㸧
(b) Ego node : An annual report page㸦K=10㸧
ᅗ 3 Hosei 䝛䝑䝖䝽䞊䜽 ᶵ⬟䝁䝭䝳䝙䝔䜱ᢳฟ⤖ᯝ
Fig.3

Results of Functional Communities of Hosei Networkᅗ 2(a)ࡢ࢚ࢦࣀ࣮ࢻࡣ㸪๓㏙ࡋࡓࡼ࠺࡟ὴ㛸ࡢ࣮ࣜࢲ࣮ⓗᏑᅾ࡛࠶ࡿ㸬࢚ࢦࣀ࣮ࢻࡢどⅬ࠿ࡽࡢᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟ⤖ᯝࢆぢࡿ࡜㸪࢚ࢦࣀ࣮ࢻࡢ࿘㎶ࣀ࣮ࢻ㸪≉࡟࢚ࢦࣀ࣮ࢻࡢ
ὴ㛸࡟ᒓࡍࡿࣀ࣮ࢻࢆ⣽࠿ࡃศ㢮ࡋ࡚࠸ࡿ㸬࡝ࡕࡽࡢὴ㛸࡟ࡶᙉ࠸ࢥࢿࢡࢩࣙࣥࢆᣢࡘࣀ࣮ࢻ㸦㉥‫ە‬㸧㸪ࣁࣈⓗᏑᅾࡢࣀ࣮ࢻ㸦᱈‫ۻ‬㸧㸪ࣁࣈࣀ࣮ࢻ࡜ࡢࡳ㞄᥋ࡋ࡚࠸ࡿࣀ࣮ࢻ㸦⥳‫ڸ‬㸧㸪࢚ࢦࣀ࣮ࢻ࡜ࡔࡅ㞄᥋ࡋ࡚࠸ࡿࣀ࣮ࢻ㸦Ỉ㸩㸧࡞࡝࡟ศ㢮ࡉࢀ࡚࠸ࡿ㸬㐲᪉ࡢࣀ࣮ࢻ㸪ࡍ࡞ࢃࡕ㸪௚ࡢὴ㛸ࡢࣀ࣮ࢻࡢከ
ࡃࡣྠ୍ࡢࢥ࣑ࣗࢽࢸ࢕࡜ࡋ࡚⢒ࡃศ㢮ࡉࢀ࡚࠸ࡿ㸬ᅗ 2(b)ࡢ࢚ࢦࣀ࣮ࢻࡣ㸪ࢿࢵࢺ࣮࣡ࢡࡢࡣࡎࢀ࡟఩⨨ࡍࡿࣀ࣮ࢻ࡛࠶ࡿ㸬࢚ࢦࣀ࣮ࢻࡢどⅬ࠿ࡽࡢᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟ⤖ᯝࢆぢࡿ࡜㸪࢚ࢦࣀ࣮ࢻࡢ㞄᥋ࣀ࣮ࢻ㸦㟷‫ڦ‬㸧࡜ࡑࡢࢢ࣮ࣝࣉ㸦⥳‫ڸ‬㸧㸪ὴ㛸ෆࡢ௚ࡢࣀ࣮ࢻ㸦㉥‫ە‬㸧㸪௚ࡢὴ㛸ࡢࣀ
࣮ࢻ㸦㯤‫ی‬㸧࡟ศ㢮ࡉࢀ࡚࠸ࡿ㸬ࡇࡢ⤖ᯝ࠿ࡽ᝿ᐃ࡛ࡁࡿࡇ
࡜࡜ࡋ࡚㸪ࡇࡢ࢚ࢦࣀ࣮ࢻࡀὴ㛸ෆ࡛➃࡟Ꮡᅾࡋ࡚࠸ࡿࡓࡵ㸪ぶࡋ࠸཭ே㸦┤᥋㞄᥋ࡍࡿࣀ࣮ࢻ㸧௨እࡢὴ㛸ෆࡢࣀ࣮ࢻࡣ
ྠ୍ᶵ⬟ࡋ࠿᭷ࡋ࡚࠸࡞࠸࡜࠸࠺ࡇ࡜࡛࠶ࡿ㸬ࡇࢀࡽࡢ⤖ᯝ
ࢆ㋃ࡲ࠼ࡿ࡜㸪ࢿࢵࢺ࣮࣡ࢡࡢᶵ⬟࡜ྠ᫬࡟㸪≉࡟࢚ࢦࣀ࣮
ࢻ࠿ࡽ㐲࠸㒊ศ࡛ὴ㛸ࡢࡼ࠺࡞ࢥ࣑ࣗࢽࢸ࢕ᴫᛕࡶ⪃៖ࡉࢀࡿࡇ࡜ࡀ♧၀ࡉࢀࡓ㸬ᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ࡣ㸪ࢿࢵࢺ࣮࣡ࢡᵓ㐀࠿ࡽ❚࠸▱ࡿࡇ࡜ࡢ࡛ࡁࡿࣀ࣮ࢻࡢᙺ๭㸦㝵ᒙᛶ࡯࠿㸧࡟ࡼࡾศ㢮࡛ࡁࡿᡭἲ
࡛࠶ࡿ㸬Karate ࢿࢵࢺ࣮࣡ࢡࡢࡼ࠺࡟㝵ᒙᛶࡀ᫂☜࡟⾲ࢀ࡞࠸ࢿࢵࢺ࣮࣡ࢡ࡛ࡣ㸪ὴ㛸ࡢ࣮ࣜࢲ࣮ࡸࡣࡎࢀࣀ࣮ࢻ࡞࡝
ࡢᙺ๭࡟ࡼࡾࢥ࣑ࣗࢽࢸ࢕ࡀᢳฟࡉࢀࡿ[8]㸬ࣃ࣮ࢯࢼࣛ࢖ࢬ
ᶵ⬟ࢥ࣑ࣗࢽࢸ࢕࡛ࡣ㸪࢚ࢦࣀ࣮ࢻ࡜ࡢ㊥㞳࡜ࡑࡢᙺ๭࡟౫
Ꮡࡋ࡚ศ㢮ࡉࢀࡿ⤖ᯝࡀᚓࡽࢀࡓ㸬

4.2.3 Hosei 䝛䝑䝖䝽䞊䜽䛾ฎ⌮⤖ᯝ

Hosei ࢿࢵࢺ࣮࣡ࢡࡢ⤖ᯝࢆᅗ 3(a)࡜ᅗ 3(b)࡟ࡑࢀࡒࢀ♧ࡍ㸬ࡑࢀࡒࢀ࢚ࢦࣀ࣮ࢻࢆ㯮࠸୸࡛ᅖࡗ࡚࠸ࡿ㸬Hosei ࢿࢵࢺ࣮࣡ࢡࡣ㸪㞄᥋ᛶࡀどㄆ࡛ࡁࡿࡼ࠺㸪ࢡࣟࢫ࢚ࣥࢺࣟࣆ࣮
ἲ࡟ࡼࡾྍど໬ࡋࡓ[16]㸬ࡇࡢࢿࢵࢺ࣮࣡ࢡࡢ≉ᚩࡣ㸪ᩍဨࡢᡂᯝሗ࿌࣮࣌ࢪࡀᖺᗘࡈ࡜࡟ูࡢࢹ࢕ࣞࢡࢺࣜ࡟ࡲ࡜ࡵ
࡚ᩚ⌮ࡉࢀ࡚බ㛤ࡉࢀ࡚࠸ࡿࡇ࡜࡛࠶ࡿ㸬࡞࠾㸪࢖ࣥࢹࢵࢡ
ࢫ࣮࣌ࢪ࠿ࡽ࡝ࡢᖺᗘ࡟ࡶ㎺ࢀࡿࡀ㸪ᖺᗘ㛫ࡢࣜࣥࢡࡣᏑᅾ

ࡋ࡞࠸㸬㏻ᖖࡢᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟἲ࡛ࡣ㸪┤᥋㞄᥋ࡋ࡚࠸࡞࠸ᖺᗘࡈ࡜ࡢᡂᯝሗ࿌࣮࣌ࢪࡀྠ୍ࢥ࣑ࣗࢽࢸ࢕࡜ࡋ
࡚ᢳฟࡉࢀࡿ࡞࡝㸪ࢿࢵࢺ࣮࣡ࢡෆ࡛ࡢ኱ᇦⓗ࡞ᶵ⬟࣭ᙺ๭࡟ᇶ࡙࠸࡚ࣀ࣮ࢻࢆศ㢮࡛ࡁࡿ[7]㸬
ᅗ 3(a)ࡢ࢚ࢦࣀ࣮ࢻࡣ㸪ࢩࣛࣂࢫ࣮࣌ࢪ⩌ࡢ 1 ࣮࣌ࢪ࡛࠶
ࡾ㸪ᑐ㇟኱Ꮫෆࡢ࠶ࡿㅮ⩏࡟㛵ࡍࡿ࣮࣌ࢪ࡛࠶ࡿ㸬௒ᖺᗘ㛤ㅮㅮ⩏ࡢࢩࣛࣂࢫ඲࡚࡟ᑐࡋ࡚ࣜࣥࢡࢆࡍࡿ࢖ࣥࢹࢵࢡࢫ
࣮࣌ࢪࡈᏑᅾࡍࡿ㸬࢚ࢦࣀ࣮ࢻࡣ㸪ࡇࡢ࢖ࣥࢹࢵࢡࢫ࣮࣌ࢪ
࠿ࡽࡢࡳࣜࣥࢡࡉࢀ࡚࠸ࡿ㸬࢚ࢦࣀ࣮ࢻࡢどⅬ࠿ࡽࡢᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟ⤖ᯝࢆぢࡿ࡜㸪࢚ࢦࣀ࣮ࢻࡢ࿘㎶ࣀ࣮ࢻ㸪≉࡟ࢩࣛࣂࢫ⩌ࡣᮏᖺᗘ㛤ㅮࢩࣛࣂࢫ⩌㸦Ⲕ㸧࡜ᮍ㛤ㅮࢩࣛࣂࢫ⩌㸦῝⥳㸧㸪Ꮫ⛉ᶓ᩿ཷㅮᣦᐃㅮ⩏ࡢࢩࣛࣂࢫ㸦㯤⥳㸧࡜࠸࠺ࡼ࠺࡟⣽࠿ࡃศ㢮ࡉࢀ࡚࠸ࡿ㸬୍᪉㸪࢚ࢦࣀ࣮ࢻ࠿ࡽ㐲ࡃ࡟Ꮡᅾࡍࡿࣀ࣮ࢻ⩌ࡣ㸪㏻ᖖࡢᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟ⤖ᯝ࡜ẚ㍑ࡋ࡚㸪⢒ࡃศ㢮ࡉࢀࡿഴྥ࡟࠶ࡿ㸬ᅗ 3(b)ࡢ࢚ࢦࣀ࣮ࢻࡣ㸪ᑐ㇟ᖺᗘࡢᩍဨᡂᯝሗ࿌࣮࣌ࢪ⩌࡬ࡢ࢖ࣥࢹࢵࢡࢫ࣮࣌ࢪ࡛࠶ࡿ㸬࢚ࢦࣀ࣮ࢻࡢどⅬ࠿ࡽࡢᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟ⤖ᯝࢆぢࡿ࡜㸪࢚ࢦࣀ࣮ࢻࡢ࿘㎶ࣀ࣮ࢻ㸪ࡍ࡞ࢃࡕྠᖺᗘࡢᡂᯝሗ࿌࣮࣌ࢪࡣ㸪ึࡵࡢᩍဨ࡜᭱ᚋࡢᩍ
ဨ࣮࣌ࢪࡢࡼ࠺࡞ᮎ➃࡟఩⨨ࡍࡿ࣮࣌ࢪ࡜୰㛫࡟఩⨨ࡍࡿ࣮࣌ࢪࡢࡼ࠺࡟㸪⣽࠿࡞ࣜࣥࢡᵓ㐀ࡢ㐪࠸࡟ࡼࡾ⣽࠿ࡃศ㢮ࡉࢀ࡚࠸ࡿ㸬୍᪉㸪࢚ࢦࣀ࣮ࢻ࠿ࡽ㐲ࡃ࡟Ꮡᅾࡍࡿࣀ࣮ࢻ⩌ࡣ㸪㏻ᖖࡢᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ᢳฟ⤖ᯝ࡜ẚ㍑ࡋ࡚㸪⢒ࡃศ㢮ࡉࢀࡿഴྥ࡟࠶ࡿ㸬

5. 䛚䜟䜚䛻
ᮏ◊✲࡛ࡣ㸪ᚑ᮶࡜ࡣ␗࡞ࡾ㸪ࣀ࣮ࢻࡢどⅬ࡟ᇶ࡙ࡃࢥ࣑
ࣗࢽࢸ࢕ࡢᴫᛕ࡜ࡋ࡚ࣃ࣮ࢯࢼࣛ࢖ࢬᶵ⬟ࢥ࣑ࣗࢽࢸ࢕࠾
ࡼࡧ㸪ࡑࡢᢳฟᡭἲࢆᥦ᱌ࡋࡓ㸬ࣃ࣮ࢯࢼࣛ࢖ࢬᶵ⬟ࢥ࣑ࣗࢽࢸ࢕ࡣ㸪࢚ࢦࣀ࣮ࢻࡢどⅬ࠿ࡽぢࡓ௚ࡢࣀ࣮ࢻࡢᶵ⬟࣭ᙺ๭࡟ᇶ࡙ࡃࢥ࣑ࣗࢽࢸ࢕࡛࠶ࡾ㸪ࢥ࣑ࣗࢽࢸ࢕ᢳฟ࡛ࡣ᪂ࡋ
࠸ࣃࣛࢲ࢖࣒࡛࠶ࡿ࡜࠸࠼ࡿ㸬ᥦ᱌ἲࡣ㸪ྛࣀ࣮ࢻࡢᶵ⬟ࢆ⾲ࡍ≉ᚩ࣋ࢡࢺ࡛ࣝ࠶ࡿ PageRank ࢫࢥ࢔ኚ໬᭤⥺ࡢィ⟬࡟࠾࠸࡚㸪Personalized PageRank ࡟ᇶ࡙ࡁ㸪ึᮇ࣋ࢡࢺ
ࣝࡢ࢚ࢦࣀ࣮ࢻ࡟ᑐᛂࡍࡿせ⣲ࢆ 1㸪ࡑࡢ௚ࡢࣀ࣮ࢻࡢᑐᛂ

5― 31 ―

᪥ᮏ䝕䞊䝍䝧䞊䝇Ꮫ఍ㄽᩥㄅ Vol.11, No.3
日本データベース学会論文誌 Vol.11,
2013 ᖺ No.3
2᭶
2013年 2月

一般論文
୍⯡ㄽᩥ

‫ݡࡍ࡛ࣝࣉࣥࢧ࡛ࡲࡃ࠶ࡣࢀࡇݡ‬ࡍࡿせ⣲ࢆ 0 ࡜ࡍࡿㄪᩚࢆຍ࠼ࡓ㸦࿴ࡀ 1 ࡟࡞ࡿࡼ࠺࡟ṇつ໬ࡍࡿ㸧㸬ࡉࡽ࡟㸪௵ពࡢࣀ࣮ࢻ࠿ࡽ☜⋡ ș࡛࢚ࢦࣀ࣮ࢻ࡟
ࢪࣕࣥࣉࡍࡿᶵᵓࢆᑟධࡋࡓ㸬ேᕤࢿࢵࢺ࣮࣡ࢡ㸪ࢯ࣮ࢩ࣭ࣕࣝࢿࢵࢺ࣮࣡ࢡ㸪ࣁ࢖ࣃ࣮ࣜࣥࢡࢿࢵࢺ࣮࣡ࢡ࡜࠸ࡗࡓᵓ㐀ࡢ␗࡞ࡿ」ᩘ✀ࡢࢿࢵࢺ࣮࣡ࢡࢆ⏝࠸ࡓホ౯ᐇ㦂࡟ࡼࡾ㸪࢚ࢦࣀ࣮ࢻࡢどⅬ࠿ࡽぢ࡚ྠ㉁࡞ᶵ⬟ࢆᣢࡘࣀ࣮ࢻ⩌ࢆࢥ࣑ࣗࢽࢸ࢕࡜ࡋ࡚ᢳฟ࡛ࡁ
ࡿࡇ࡜ࢆ♧ࡋࡓ㸬ᥦ᱌ἲ࡟ࡼࡿᢳฟࡋࡓࢥ࣑ࣗࢽࢸ࢕ࡣ㸪ᐈほⓗ࡟ྠࡌᶵ⬟ࡢࣀ࣮ࢻࡀᏑᅾࡋ࡚ࡶ㸪࢚ࢦࣀ࣮ࢻ࡜ࡢ㊥㞳ࡀ㐪࠺࡜␗࡞ࡿࢥ࣑ࣗࢽࢸ࢕࡜ࡋ࡚ᢳฟࡉࢀࡿ࡜࠸࠺≉ᚩࡀ࠶ࡿ㸬ࡋ࠿ࡋ㸪༢⣧࡟㸪࢚ࢦࣀ࣮ࢻ࠿ࡽࡢ㊥㞳࡟ᇶ࡙࠸࡚
ศ㢮ࡋ࡚࠸ࡿࢃࡅ࡛ࡣ࡞࠸㸬ࡲࡓ㏻ᖖࡢᶵ⬟ࢥ࣑ࣗࢽࢸ࢕࡜
ࡢẚ㍑࡟ࡼࡾ㸪࢚ࢦࣀ࣮ࢻ㏆ࡃࢆ⣽࠿ࡃศ㢮ࡋ㸪㐲ࡃࢆ⢒ࡃศ㢮ࡍࡿ⤖ᯝࡀᚓࡽࢀࡓ㸬ࡇࢀࡣ㸪⮬㌟ࡢ࿘㎶ࡣ⮬㌟࡜ࡢ㛵ಀࡀᙉࡃ㸪┤᥋ⓗ࡟ᙳ㡪ࡍࡿࡓࡵ㸪ศ㢮ࡢ⢏ᗘࡀ⣽࠿ࡃ࡞ࡿࡀ㸪⮬㌟࠿ࡽ㞳ࢀࡓ఩⨨࡟Ꮡᅾࡍࡿࡶࡢࡣ㛵ಀࡀᙅ࠸ࡓࡵ㸪ศ㢮ࡢ⢏ᗘࡀ⢒ࡃ࡞ࡿ࡜࠸࠺┤ほ࡟ᑐᛂࡋ࡚࠸ࡿ㸬ᮏ✏ࡢ⤖ᯝࡣ㸪ࢻࣛ࢖ࣂ࣮ࡀ࣮࢝ࢼࣅ࡞࡝ࢆ㜀ぴࡍࡿ࡟㝿ࡋ࡚㸪ࢻࣛ࢖ࣂ࣮ࡢ࠸ࡿ஺ᕪⅬ௜㏆ࡣ⯆࿡ࡀ࠶ࡿࡓࡵࡑࡢ᝟
ሗࢆ⣽ศ໬ࡋ㸪㐲᪉ࡢᆅᇦࡣẚ㍑ⓗ⯆࿡ࡀⷧ࠸ࡓࡵ⣽ศ໬ࡍࡿᚲせࡀ࡞࠸㸪࡜࠸ࡗࡓ┤ほ࡟ᑐᛂࡋࡓᛂ⏝ࡀ⪃࠼ࡽࢀࡿ㸬௒ᚋࡣ㸪ᐇၥ㢟࡬ࡢᛂ⏝ࢆど㔝࡟ධࢀ࡚㸪ከᵝ࡞ࢿࢵࢺ࣮࣡
ࢡ࡛ᥦ᱌ἲࡢ᭷ຠᛶࢆ᳨ドࡋ࡚࠸ࡃࡘࡶࡾ࡛࠶ࡿ㸬ࡲࡓ㸪࢚ࢦࣀ࣮ࢻ࡜ࡋ࡚」ᩘࣀ࣮ࢻࢆ㑅ᢥࡋࡓሙྜ࡛ࡢ᳨ドࡸ࢚ࢦࢪࣕࣥࣉ☜⋡ࡢ᭷⏝ᛶࢆ῝ࡃ㏣ồࡋ࡚࠸ࡃࡘࡶࡾ࡛࠶ࡿ㸬

DBSJ
Vol.11,DBSJ Journal,
Journal,Vol.
11,No.3
No.3
February
February 20132013

Vol.5, No.2, pp. 1--10 (2012).
[9] Langville, A. N. and Meyer, C. D.: Deeper inside
pagerank, Internet Mathematics, Vol.1, (2004).
[10] Nemhauser, G.L., Wolsey, L.A. and Fisher, M.L.: Ananalysis of approximations for maximizing
submodular set functions, Math. Prog., Vol.14, pp.
265--294 (1978).
[11] Page, L., Brin, S., Motwani, R. and Winograd, T.: The
PageRank Citation Ranking: Bringing Order to theWeb., Technical Report 1999-66, Stanford InfoLab(1999).
[12] Ravasz, E. and Barabasi, A.L.: Hierarchicalorganization in complex networks, Physical Review
E, Vol.67, No.2, 026112+ (2003).
[13] Zachary, W.: An information flow model for conflict
and fission in small groups, Journal of
Anthropological Research, Vol.33, pp. 452³473(1977).
[14] http://cis.k.hosei.ac.jp/[15] Kamada, T. and Kawai, S.: An algorithm for drawing
general undirected graphs, Inf. Process. Lett., Vol.31,
pp. 7--15 (1989).
[16] Yamada, T., Saito, K. and Ueda, N.: Cross-entropy
directed embedding of network data, Proceedings ofthe 20th International Conference on Machine
Learning (ICML03), pp. 832--839 (2003).

అぢ ༟ᜤ Takayasu FUSHIMI[ㅰ㎡]ᮏ◊✲䛿䠈NTT ᮍ᮶䛽䛳䛸◊✲ᡤ䛸䛾ඹྠ◊✲䠈ཬ䜃䠈⛉◊㈝ (23500128) 䛾ᨭ᥼䜢ཷ䛡䛶⾜䛳䛯䜒䛾䛷䛒䜛䠊

[ᩥ⊩䠹
[1]

Freeman, L.: Centrality in social networks:
Conceptual clarification, Social Networks, Vol.1,
No.3, pp. 215--239 (1979).
[2] Newman, M. E. J. and Park, J.: Why social networks
are different from other types of networks, Phys. Rev.
E, Vol.68, No.3, 036122 (2003).
[3] Newman, M. E. J.: Detecting community structure in
networks, The European Physical Journal B Condensed Matter and Complex Systems, Vol.38,
No.2, pp. 321--330 (2004).
[4] Palla, G., Derenyi, I., Farkas, I. and Vicsek, T.:
Uncovering the overlapping community structure ofcomplex networks in nature and society, Nature,
Vol.435, pp. 814--818 (2005).
[5] Saito, K., Yamada, T. and Kazama, K.: The k-Dense
Method to Extract Communities from Complex
Networks, Mining Complex Data (Zighed, D.,
Tsumoto, S., Ras, Z. and Hacid, H., eds.), Studies in
Computational Intelligence, Vol.165, Springer Berlin/ Heidelberg, pp. 243--257 (2009).
[6] Seidman, S. B.: Network structure and minimum
degree, Social Networks, Vol.5, No.3, pp. 269 -- 287(1983).
[7] అぢ༟ᜤ䠈ᩧ⸨࿴ᕭ䠈㢼㛫୍ὒ䠖䝛䝑䝖䝽䞊䜽ᶵ⬟䝁䝭䝳䝙䝔䜱ᢳฟἲ䠈᪥ᮏ䝕䞊䝍䝧䞊䝇Ꮫ఍ㄽᩥㄅ㸪Vol.10, No.3,
pp. 13--18 (2012).
[8] అぢ༟ᜤ䠈ᩧ⸨࿴ᕭ䠈㢼㛫୍ὒ䠖ᶵ⬟ᛶ䛻ᇶ䛵䛟䝁䝭䝳䝙䝔䜱ᢳฟἲ䛾ẚ㍑䠈᝟ሗฎ⌮Ꮫ఍ㄽᩥㄅ 䝕䞊䝍䝧䞊䝇㸪㟼ᒸ┴❧኱Ꮫ኱Ꮫ㝔⤒Ⴀ᝟ሗ࢖ࣀ࣮࣋ࢩࣙࣥ◊✲⛉༤ኈᚋᮇㄢ⛬ᅾᏛ୰㸬2011 㟼ᒸ┴❧኱Ꮫ኱Ꮫ㝔⤒Ⴀ᝟ሗᏛ◊✲⛉ಟኈㄢ⛬ಟ஢㸬」㞧ࢿࢵࢺ࣮࣡ࢡࡢ◊✲࡟ᚑ஦㸬㟁Ꮚ᝟ሗ㏻
ಙᏛ఍㸪᪥ᮏࢹ࣮ࢱ࣮࣋ࢫᏛ఍㸪ேᕤ▱⬟Ꮫ఍㸪᝟ሗฎ⌮Ꮫ఍ྛᏛ⏕఍ဨ㸬ᩧ⸨ ࿴ᕭ Kazumi SAITO㟼ᒸ┴❧኱Ꮫ⤒Ⴀ᝟ሗᏛ㒊ᩍᤵ㸬1985 ᖺ៞ᛂ⩏ሿ኱Ꮫ⌮ᕤᏛ㒊ᩘ⌮⛉Ꮫ⛉ᩘᏛᑓᨷ༞ᴗ㸪ྠᖺ᪥ᮏ㟁ಙ㟁ヰ(ᰴ)ධ♫㸬
1998 ᖺᮾி኱Ꮫ ༤ኈ㸦ᕤᏛ㸧㸬」㞧ࢿࢵࢺ࣮࣡ࢡ㸪ᶵᲔᏛ⩦ࡢ◊✲࡟ᚑ஦㸬᝟ሗฎ⌮Ꮫ఍㸪㟁Ꮚ᝟ሗ㏻ಙᏛ఍㸪ேᕤ▱⬟Ꮫ఍㸪᪥ᮏ⚄⤒ᅇ㊰Ꮫ఍㸪᪥ᮏᛂ⏝ᩘ⌮Ꮫ఍㸪᪥ᮏ⾜ືィ㔞Ꮫ఍㸪᪥ᮏࢹ࣮ࢱ࣮࣋ࢫᏛ఍ྛ఍ဨ㸬ⴭ᭩࡟ࠕ࢙࢘ࣈࢧ࢖
࢚ࣥࢫධ㛛 -࢖ࣥࢱ࣮ࢿࢵࢺࡢᵓ㐀ࢆゎࡁ᫂࠿ࡍ-ࠖ(NTT ฟ∧)㸬ụ⏣ ဴኵ Tetsuo IKEDA㟼ᒸ┴❧኱Ꮫ⤒Ⴀ᝟ሗᏛ㒊ᩍᤵ㸬1981 ᖺᮾி኱Ꮫ኱Ꮫ㝔⌮Ꮫ⣔◊✲⛉᝟ሗ⛉Ꮫᑓᨷಟኈㄢ⛬ಟ஢㸬ྠᖺ᪥ᮏ㟁ಙ㟁ヰ(ᰴ)ධ♫㸬2002 ᖺᒾᡭ┴❧኱Ꮫࢯࣇࢺ࢙࢘࢔᝟ሗᏛ㒊ᩍᤵ㸬
2006 ᖺ㟼ᒸ┴❧኱Ꮫ⤒Ⴀ᝟ሗᏛ㒊ᩍᤵ㸬ࢹ࣮ࢱ࣮࣋ࢫᕤᏛ㸪᝟ሗ᳨⣴㸪ᆅ⌮᝟ሗࢩࢫࢸ࣒ࡢ◊✲࡟ᚑ஦㸬᝟ሗฎ⌮Ꮫ఍㸪㟁Ꮚ᝟ሗ㏻ಙᏛ఍㸪᪥ᮏࢹ࣮ࢱ࣮࣋ࢫᏛ఍ゝㄒฎ⌮Ꮫ఍㸪
ACM ྛ఍ဨ㸬㢼㛫 ୍ὒ Kazuhiro KAZAMA࿴ḷᒣ኱Ꮫࢩࢫࢸ࣒ᕤᏛ㒊ᩍᤵ㸬1988 ᖺி㒔኱Ꮫ኱Ꮫ㝔ᕤᏛ◊✲⛉⢭ᐦᕤᏛᑓᨷಟኈㄢ⛬ಟ஢㸬ྠᖺ᪥ᮏ㟁ಙ㟁ヰ(ᰴ)ධ♫㸬2005 ᖺி㒔኱Ꮫ኱Ꮫ㝔᝟ሗᏛ◊✲⛉ࢩࢫࢸ࣒⛉Ꮫᑓᨷ༤ኈㄢ⛬ಟ஢㸬༤ኈ㸦᝟ሗᏛ㸧
㸬Web ᝟ሗ᳨⣴㸪Web ࣐࢖ࢽࣥࢢࡢ◊✲࡟ᚑ஦㸬᝟ሗฎ⌮Ꮫ఍㸪ேᕤ▱⬟Ꮫ఍㸪᪥ᮏࢯࣇࢺ࢙࢘࢔⛉Ꮫ఍㸪ACM ྛ఍ဨ㸬6
― 32 ―

᪥ᮏ䝕䞊䝍䝧䞊䝇Ꮫ఍ㄽᩥㄅ Vol.11, No.3
日本データベース学会論文誌 Vol.11,
2013 ᖺ No.3
2᭶
2013年 2月