2008年10月31日
第11回情報論的学習理論ワークショップ(IBIS2008)

複雑ネットワークと機械学習

無限関係モデルとその周辺

NTTコミュニケーション科学基礎研究所
創発環境研究グループ
山田 武士© NTT Communication Science Labs.

２００８年１１月２９日改訂版

関係データやネットワークのクラスタリング
ネットワークからのコミュニティ抽出
コミュニティ１

コミュニティ２
リンクのクラスタリング

より複雑な関係データのクラスタリング

コミュニティ３

各手法の紹介と手法間の関係の整理

多重クラスタリング
２ドメインの場合は Co-Clustering（stochastic block models）© NTT Communication Science Labs.

スケールフリーネットワーク
k：次数（ノードのリンク数）、P(k)：次数 k のノード数の割合（確率）一定の確率でリンクを張る

pER =0.2

次数分布

Erdös
Erdös-Rényi ランダムネットワーク
次数分布

次数に比例する確率でリンクを張る

スケールフリーネットワーク

もっとも次数の高い5ノード（赤）と繋がっている（緑）のは２７％

power law

もっとも次数の高い5ノード（赤）と繋がっている（緑）のは６０％

Scale-free and hierarchical structures in complex networks, Albert-László Barabási et al. Physical Review E 67, 026112, 2003
© NTT Communication Science Labs.

優先選択モデル（Preferential Attachment）[Barabasi & Albert 1999]
現在のネットワークに新たなノード x を追加
z 次数（リンク数）に比例する確率で、既存のノードをランダムに選択し、x からリンクを張る、これを m 回行う（x からのリンク m 本）z

⇒ほぼ係数 γ＝３ のべき則（power law)に従うネットワークを生成
ノード数
次数小次数大10000

power law1000

γ＝３100

確率小10確率大
x1
1101001000

次数• すでにたくさんリンクを持つノードほど、新たなリンクを張りやすい• リンクが密な部分、疎な部分が混在⇒「構造」を持つネットワーク「構造」抽出© NTT Communication Science Labs.

Newman の Network Modularity
同一コミュニティ内のリンクは密、コミュニティ間のリンクは疎
e13 = e31 = 2/60
e11 = 12/60

C1C3
e33 = 18/60

e12 = e21 = 2/60
e22 = 20/60

C2

e23 = e32 = 1/60

全リンク数：６０/２

Ci , Cj間のリンク数の割合
相手コミュニティを区別せずリンクを張る場合の Ci , Cj 間のリンク数の割合の期待値

Modularity（モジュール度）→ 最大
コミュニティ内リンクに着目

コミュニティがリンクで特徴付けられない⇒両者はほぼ一致

Find and evaluating community structure in networks M.E.J. Newman and M. Girvan, Physical Review E, 2004
© NTT Communication Science Labs.

Network Modularity の特徴と問題点
特徴• 同一クラスタ（コミュニティ）内は、クラスタ間に比べて、相対的に、より密に結合している。
• クラスタ外へのリンクの張り方は似ていなくても良い
問題点• 確率モデルではない（ノイズ等を考慮していない）• resolution limit の問題がある

0.790476
0.794921

Resolution limit in community detectionSanto,Fortunato and Marc Barthélemy, Proc. Natl. Acad. Sci. USA 104, 36–41 (2007).
© NTT Communication Science Labs.

Mixture Model によるノードクラスタリング
同じクラスのノードは、同じ相手にリンクを張る★prior なし
コミュニティとは言えない？
261630

k=328
32

15
23
21

25
29

27

19

34,33,32,31,30,29,28,27,26,25,24,23,21,19,16,15,10,9,8,7,6,5,4,3,2,1,18,17,14,13,12,11,22,20

24

34

22

61720

33
9711331 1410215418813

文書の場合の uni-topic model と同じ

12k=2
Mixture models and exploratory analysis in networks, M. E. J. Newman and E. A. Leicht, Proc. Natl. Acad. Sci. USA 104,
© NTT Communication Science Labs.
9564–9569 (2007).

Assortative ｖｓ disassortative
assortative:• コミュニティ内のリンクが密、コミュニティ間のリンクが疎
disassortative：• コミュニティ間のリンクが密、コミュニティ内のリンクが疎

assortative

disassortative© NTT Communication Science Labs.

ＤＰに基づく「無限」クラスタリング
Mixture Model の「無限」化
Mixture Model

Infinite Mixture Model

Stick Breaking Process＝「無限次元の多項分布」を生成
Chinese Restaurant Processπ1π2π3π4 . . .

ノンパラメトリックベイズモデルによるグラフクラスタリング、桑田 修平、上田 修功 、山田 武士、 Vol.107,© NTT Communication Science Labs.
No.115 (20070621) pp. 81-86、PRMU2007-41

Chinese Restaurant Process
クラスタ数をあらかじめ固定せず、データごとに最適なクラスタリングをしたい
Chinese Restaurant Process「自然な」「無限個クラスタ」のモデル• すでにたくさん人がいるテーブル（クラスタ）ほど新たな客が座りやすい• 一定の確率で新しいテーブルに座る場合もある
客
1

2

j

K+1

： テーブル j の客の数
： 現在の総テーブル数： 新テーブル生成頻度

N 人着席した状態の生起確率
N 番目の客既存テーブル
新規テーブル

クラスタサイズは大きい、クラスタ数は少ない、ほうが良い
α が大きいほど、クラスタ数多い• 優先選択モデル(Preferential Attachment)と共通する考え方• 中立進化説（自然淘汰が存在しない場合の進化）のモデル
例えば、Hierarchical Dirichlet Processes, Y.W. Teh, et al., Journal of the American Statistical Association, 101, 1566-1581, 2006.
© NTT Communication Science Labs.

Collapsed Gibbs Sampling
12j

K

K+1j

K

K+1j

K

K+1

割り当て解除

繰り返し

12

予測確率

12

尤度(new)

予測確率

尤度(old)© NTT Communication Science Labs.

単語連想ネットワーク
元データは、南フロリダ大学心理学科のプロジェクトで作成
被験者数：平均149人（±１５程度）
被験者にキューとなる単語を与え、関連する単語を連想してもらう
RED

CORE
0.304
(45人/148人中)

ORANGE

0.208

APPLE

ORCHARD
0.291

0.174
FRUIT

NEWTON

0.138

0.154
0.074

0.252
PEAR

0.047

0.228
PIE

双方向のリンクの強さの和を一定の閾値（0.025）で無向化⇒ ノード数 : 7,207、リンク数 : 31,784
University of South Florida Free Association Norms, http://w3.usf.edu/FreeAssociation/© NTT Communication Science Labs.

単語連想ネットワークのクラスタリング例© NTT Communication Science Labs.

単語連想ネットワークの例
FOOD
VINEGARTASTE
TOPPINGHAIRSPRAYLUNCH
VEGETABLESCHIPSCOOKIESFRESH
COCKTAILGRAIN
BOWL
BUTTER
CANDY
CHOCOLATESOUPPIECRACKERSFEEDPICNIC
APPLE
BAKED
BANANA
CHERRY
COBBLER
FRUIT
GRAPE
JUICE
ORANGEORCHARD
PEACH
PEAR
PLUM
APPLE_JUICEORANGE_JUICE
PLATE
TRAY
BREAKFAST
CRISP
FRY
SOUR
STALE
TEA
BAGEL
BREAD
CREAM_CHEESE
DOUGHNUT
BAKE
BROIL
CAKE
COOKIEFLOURCOOKEDFRIEDPOTATOPOTATOES
BAKER
BAKERY
BUTCHERCHEF

PASTRY
CATCHERPITCHERRACKETPEELBANQUETDINNER
EATFEASTCRUNCHSALAD
SALOONCHARCOALHAMBURGER
SAUCE
BARLEYHERB
HOPS
OATS
SPICE
WHEAT
CRACKERPICKLES
HOT_DOGS
EASTERSTRAW
CHILI
COFFEEFARTFRANKS
RICE
STALK
FARTS
LIMA
PEAS
REFRIEDHONEYSIRLOIN
STEW
BUD
PIZZA
BEET
CARROTRADISHTURNIPBERRYBLUEBERRYRASPBERRYSTRAWBERRY
BIG_MACMCDONALD'SKIWIPARCHEDPARROT
SWALLOWTURKEYBISCUIT
BUN
DOUGH
MUFFINBIT

FROST
BITTERSWEETTANGY
TARTOLIVESTALLIONBLACKBERRY
JAM
WINE_COOLER
STARCHMILKSHAKEPANCAKESCHECKERSBOILEDCHEESEOSCAR_MAYER
SANDWICHRESTAURANT
BOTTOMLESSCEREAL
DISH
SPOON
BOWLS
PLATES
BOWS
BRAN
FIBER
RAISINTWIGCINNAMONCORN
CRUMBCRUSTGARLIC
JELLY
MAYONNAISE
RYE
SHORTCAKE
SLICE
TOAST
TOASTYCHIPOATMEALWAFFLESMILK
MINTMINTS
LAYER
BROCCOLICAULIFLOWERSPINACHVEGETABLEZUCCHINIBROWNIEFUDGESQUASHCARROTSBURGER_KING
WAITERFATTENING
POPCORNCABBAGECOLESLAWCORNBEEF
LETTUCE
CUPBOARDCAFE
DINER
CAFETERIA
DESSERT
FROSTEDFROSTINGICE_CREAM
ICING
PUDDINGSNACKSPATULACAKESCAMPBELL
SARDINE
CRUNCHYSUGAR
TREAT
LEMON
PROTEIN
CELERYPEANUT_BUTTERCRACKLECHEDDAR
CREAM
GOURMETCHERISHFLAVOR
CHOMP
MUNCH
CHEWY
NUGGETSPEPPERSPICY
SILVERWARE
DIP
DORITOSPRETZELS
MOUSSE
VANILLAYOGURTYUMMY
CHOWDERHUNKCITRUSDRESSING
SEASONINGWAITRESSSTIRTEAPOT
POTATO_SALAD
CONDIMENTCONSUMECOOKBOOKRECIPESKILLETFIG
MOLASSESUTENSILLEMONADEHASHJELLOCRUMBS
HUNGER
SOGGYNESTLESCUCUMBERPICKLETOMATOHOSTESSMUGSCUSTARDMUSTARDDADDYDANISH
FAMINEPARSLEY
DELICIOUS
SCRUMPTIOUS
TASTY
DINE
MEAL
SUPPERTHANKSGIVINGTAPIOCAFORKHUNGRYSTARVENOGSCRAMBLESCRAMBLEDESCARGOTETHIOPIAFAMISHEDOPTICSFLAPJACKSFRIESMEATBALLSOREGANOPRODUCESERVERFORKS
KETCHUPPRUNE
TANGERINEGELGEORGIAPASTE
SHRED
GREASYLIME
GREENSGRITSHOSTPUMPKIN
HAWAIIAN
HERBAL
SYRUP
IDAHO

食べ物

INPUT
OUTPUTOUTTAKEISAAC
KERNELTEQUILASUCKER
LOW_FATSAP
PARKAYMARTINIMASHEDPENICILLIN
PLANTERSVITAMIN_C
POD
PILGRIMSSPOONSPOPS
TOMATOESSHRIVELSAVOR
RICE-A-RONI
RUBBERMAID
SNICKERSSTUFFING
THINS
WHIPPED_CREAM
TUMMY© NTT Communication Science Labs.

単語連想ネットワークの例
OVERFLOWABUNDANTSPILLAEROSOLBOATSAILOR
SHIP
WATER
GLIDE
NAVIGATOR
LAKE
POND
POOL
ALLIGATORGULLYREPTILEANCHOR
LIZARDMARINEOTTERPORPOISE
OCEAN
BAY
SURFACETANKSWIMMERATLANTIC
DRIFT
BABBLINGBROOK
BAHAMASCRUISESNORKELBAIT
FISH
SHRIMP
CLAM
FLOAT
RIVER
OYSTER
BUCKET
REEF
SINK
DOCK
HARBOR
INLET
SEA
SHORE
BEACH
COAST
CORAL
GULL
PELICAN
PIER
ROCKS
SAND
SEAGULL
SEASHORE
SHELLSURF

TIDE
WAVES
MERMAID
WATERFALLDAMDEEPLAGOONDIVEDIVING
CANAL
CANOE
DECK
FISHINGMOATOARPADDLE
PORT
RAFT
ROW
SAIL
SAILINGSINKERSKISUBMARINEYACHTMARSH
BON_VOYAGEBOULDERLOAF
UNDERWATER
WINDY
LEAK
CREEK
STREAMDUNE
BUOYANTC.B.
ERIE
PANAMASWIM
VALLEYWETMUSSELSCALLOP
SEAFOODDRAIN
DRANO
UNCLOGDRIPCROAKHOOVER
DEW
DROWN
DEPTH
SHALLOWFLOODDISNEY_WORLD
SCUBA
DIVER
SWIMMING

海

DOLPHIN
FIN
FLIPPERTUNAUPSTREAMDOWNSTREAMFLOW
SALMONFAUCET
DRENCH
POURMALLARD
SLAMEXCESSSPIGOT
FERN
REEL
FINS
FIVE_0
FLOATER
SLIMY
GUSH
OLD_FAITHFULSPOUTYELLOWSTONEGOO-GAASNAGGED
KEY_WEST
MOISTENSPLASHPUDDLESEA_LIONOVERFILLPEBBLESPIPESPLUNGER
RAIN_FORESTSPAWASHBASIN
WEIGH_TSPLISHSPRITZSQUIRT
SUBMERGE

ALPHABETANLETTERTYPE
ACCENTUATEWRITERBILLBOARD
PAPER
BOOK
MAIL
LIST
DOCUMENTTERMS
ALMANACDICTIONARYENCYCLOPEDIAFACTSFARMERSINFORMATIONALOUDREADINGLETTERSSTATEMENTANTITHESIS
PAD
STAMP
AUTHOREDITOR
POET
PUBLISHER
TITLE
WRITE
BACKPACKBOOKBAGPARCELTOTE
SONNET
SERIESPOEM
POETRYBEDTIMESCROLLVERSE
BINDERFOLDERNOTEBOOKDOTRAPINKPENBLOTTER
BULLETIN
BRITANNICA
JOURNAL
LITERATURE
NOTE
NOTES
NOVEL
PAGE

READ
TEXT
WORDS
WRITINGESSAYPHRASESSPEECHPOE
CARDBOARDTYPINGOUTLINESCRABBLE
BRITTANICASENTENCES
COLUMN
SPELLING
CAPTIONSYNONYMHEADING
WORD_PROCESSORREPORTDIAGRAMGRAFTMARKSIGNATURE
CLEARING_HOUSE
MARKERSENTENCE
I.B.M.
PRINT
PRINTERPRINTING
SOFTWARE
TYPEWRITER
WHIZ
CONS
PROSE
PENCILCURSIVEISSUE
TERM
LEXICONINGEST
READERSTOPIC
DISSERTATIONDOODLEEMPHASIZE
PARAGRAPHPHRASEENVELOPEQUILL
STAPLERTOWARDSPOTLIGHT
UNDERLINEHIGHLIGHTER
PAPERCLIP
HOLD_BACKTHEMEJOTPOSTMAN
POST_OFFICEPERMANENTMEMOMISSPELLSPIRAL文字© NTT Communication Science Labs.

単語連想ネットワークの例
AARDVARKANIMALANTEATERPINK_PANTHER
ADAMS
PUPPY
SAFARIAFRICAGAZELLEJUNGLELION
ZEBRA
PENGUINCAT
CROCODILE
STAG
FURRY
FURY
FIERCEANTELOPE
APE
BEAR
BEAVERBUCKCAGE
CHIMPANZEECLAWCOUGAR
COYOTEDEER
DOG
DONKEYELEPHANT
ELK
EWE
FOX
FUR
GIRAFFEGOATHUNTLEOPARD
MAMMALMINKMONKEY
MOOSE
MULE
PANTHER
PAW
PET
PREDATORPRIMATERACCOONRATSHEEPSPHINXTAIL
TAME
TIGER
TRAP
VET
WALRUSWOLFZOOANIMALS
HUNTINGPETSANTLERCANTELOUPE
ANTLERSHORNSGORILLAHAIRYTARZAN
BAMBI
SMOKY
BRAWL
BARK
MEOW
GLOVE
CLEAVER
WHALE
FAWN
PIGEONHOUNDCARTON
TRUNK
DOE
BUCS
LICE
RODENTROCKYKITTEN
MOUSE
CAVE_MANCHEETAH
LAMB
TALON
CLEAT
COBRA
CONNIVING
JOHN
CUDDLYDALMATIANDOCILE
QUACK
JANE
RAE
KONG
TUSK
PUFFY
NAVEL
WUZZY
GERMAN
IN_THE_MISTIVY
HAGAARLEE
LOUISIANA
MANATEE
MINNESOTA
PEEVE
POLKADOTS
SHREW
SOFTENERSTAINSTOCKVIETNAM

動物

20/20
HINDSIGHT
UNDERSTANDKNOW
NOTICEREALIZESEE
KNOWLEDGEOBJECTIVE
SUBJECTIVE
OPINIONWISDOM
FORESIGHT
EINSTEINAMOEBADATA
THINKANALYZECOMPAREFIGURE
INTERPRETLOOK
DETERMINEGUESSTHESISRATIONALIZE
ARISTOTLEASSUME
PRESUMESUPPOSE
CONCENTRATE
FOCUS
VISIONVIEW
REASONSO
WHY
PHILOSOPHY
BELL_TOLLS
MIND
STARE
GLARE
SUBJECTBRAIN
INTELLECTINTELLIGENCE
LOGIC
SMART
THINKING
THOUGHT
BRILLIANTGIFTEDINTELLIGENTGENIUSLENSDISCOVER
CARED
DECIDEDECISION
CLASSYWISE
IDEA
CONCEPTSUBCONSCIOUS
KNOWINGCONTEMPLATEPONDERRECONSIDERIMAGINATIONIMAGINEINVENTIMAGINATIVEINGENIOUS
INVENTORCYNIC
WHATPERCEPTIONREVEAL
HOW
ESP
INSIGHTPREDICTFACTHYPOTHESISTHEORYPUPIL
INTUITIONPSYCHICFRAME
GAZE
THEOREMTALENTED
WHO
WHERE
WHEN
I.Q.
IMAGE
SURVIVALINTELLECTUAL
IQ
LIGHT_BULBPERISCOPE
PERCEIVE
LAPSE
REFLECTOBSERVE
ORGANISM
WATCHEDWHOO
PLATO
SOCRATESTHINKERPOSTULATEPYTHAGOREAN
THEY

DRESS
CLOTHESSLEEVESUITASSEMBLE
CLOSET
ATTIRECASUAL
FORMALWEAR
COTTON
CROCHET
FUZZ
YARN
BANDANNA
CLOTH
SCARF
ROBE
PANTS
SASH
TROUSERSRACKTUXEDOVELVETKNITTING
QUILTBLEACH
JEANS
BLOUSESHIRTSKIRTSWEATERCOLLAR
RIBBON
TIE
BOOBS
BRA
SHELF
SUEDE
SHORTSUNDERWEARHOOD
PANTIESDRAWERCOAT
JACKET
MUTTONSEWZIPPERCABINETCABOODLE
MATERIALGOWN
CAPONEDRESSYINFORMAL
POLYESTERPLAIDCHECKEREDPATTERN
STOCKING

WARDROBEFABRIC
SATIN
SILK
FAD
FASHIONLACE
OUTFITSEAM
STITCHVEST
LAPEL
WOOLNYLONCREASEKNIT
CUFF_LINKPROM
DECORATIVE
DENIM
HEM
SLACKSDUNGAREESFEMININE
FIRST_AID
FLANNEL
FLUFF
TUX
RIP
RUFFLEPANTY
LEVI'S
KAT
SEWINGLOOM
MATCHING
THREADNIGHTIE
SEVENTIESSIXTIESSETTER
STUFFER
TAKE_OFF知能 服飾© NTT Communication Science Labs.

多ドメイン間の多重関係モデル
authors

documents

coauthorshipcitationwords© NTT Communication Science Labs.

ブロックモデルの例：動物とその特徴
50種類の動物と８５の特徴からなるデータをクラスタリングした例
F1 2 3 4 5 62部グラフ

12個のうち7個

O1O2O3O4O5O6O7O1O2O3O4O5killer whale, blue whale, humpback, seal, walrus, dolphin
antelope, horse, giraffe, zebra, deermonkey, gorilla, chimp
O4hippo, elephant, rhino
grizzly bear, polar bear

F1F2F3F4F5F6flippers, strain teeth, swims, arctic, coastal, ocean, waterhooves, long neck, horns
O5hands, bipedal (two-legged), jungle, treebulbous body shape, slow inactive
meat teeth, eats meat, hunter, fiercewalks, quadrapedal (four-legged), ground

O1
O3O2

© NTT Communication Science Labs.
Learning Systems of Concepts with an Infinite Relational Model, C.Kemp, J.B.Tenenbaum, T.Yamada, N.Ueda, AAAI 2006 381-388

ブロックモデルにおける関係生成モデル（１）左のリンク確率にしたがって右のようにリンクが生成。

0.1

0.9

0.15

0.05

0.10.85

0.98

0.01

0.01

© NTT Communication Science Labs.

ブロックモデルにおける関係生成モデル（２）
実際に観測される接続行列は、左のようにランダムにシャッフルされている
123456789178235946
1 2 3 4 5 6 7 8 9リンクのあるところが黒、ないところが白

0.1

0.9

0.15

0.05

0.1

0.85

0.98

0.01

0.01

1 7 8 2 3 5 9 4 6
同一クラスタ内は、白・黒がはっきり分かれる© NTT Communication Science Labs.

ブロックモデルにおけるクラスタリング
左の「接続行列」をうまく並び替えて、右のような、隠れた「ブロック構造」を見つけることに相当する
123456789178235946
1 2 3 4 5 6 7 8 9

リンクのあるところが黒、ないところが白0.1

0.9

0.15

0.05

0.1

0.85

0.98

0.01

0.01

1 7 8 2 3 5 9 4 6
同一クラスタ内は、白・黒がはっきり分かれる© NTT Communication Science Labs.

Stochastic Block Models
リンクを張る相手もクラスタリングされている

Estimation and prediction for stochastic blockstructures
K.Nowicki and T.A.B.Snijders, JASA 96 (455), 2001

Stochastic block models
同じクラスのノードは、みな同じ相手クラスにリンクを同じ相手クラス｛張る、張らない｝

Infinite Relational Model

リンク生成確率Mixture model

Infinite Mixture Model
同じクラスのノードは、みな同じ相手にリンクを張る
同じ相手バイナリなら Beta-Bernoulli
カウントなら Gamma-Poisson© NTT Communication Science Labs.

ブロックモデルにおける次元圧縮
N1×N2 次元の行列 A を K1×K2 次元に「次元圧縮」しているとみなせる

N2K1K2K2

N1(Aij) ≈N1Meeds, E., Ghahramani, Z., Neal, R. and Roweis, S.T.
Modeling Dyadic Data with Binary Latent Factors.
In Advances in Neural Information Processing Systems 19 (NIPS-2006)

K1(ηkl)T
N2

クラス所属確率 or どのクラスに所属するかを指定する行列© NTT Communication Science Labs.

IRM （無限関係モデル）
ブロックモデルの「無限」化

Learning Systems of Concepts with an Infinite Relational Model,
C.Kemp, J.B.Tenenbaum, T.Yamada, N.Ueda, AAAI 2006 381-388

Chinese Restaurant Process
積分消去

積分消去

: ベータ関数lk

リンク数□の黒の個数

非リンク数□の白の個数: ベータ分布

jointmax© NTT Communication Science Labs.

Collapsed Gibbs Sampling
C1C2

C3

C1行の入れ替え

C2C3行の入れ替えと列の入れ替えを交互に行う

列の入れ替え© NTT Communication Science Labs.

UMLS 生物医学オントロジデータのクラスタリング
UMLSデータ：135の概念と49の述語から構成
概念(T1)： Disease or Syndrome， Diagnostic Procedure， “Mammal”, ....
述語(T2)： “complicates”， “afffects”， “causes”, ...
T1 x T1 x T2 のデータとして ＩＲＭを適用• biological functions affect organisms• chemicals cause diseases• biologically active substances complicate diseases© NTT Communication Science Labs.

Erdös-Renyi mixture for graphs + DP
Jean-Jacques Daudin, Franck Picard, Stephane Robin, INRIA technical report

２次元のブロックモデルにおいて、Ｔ１＝Ｔ２の時、ネットワーク（グラフ）のノードクラスタリングと解釈できる
ブロック内、ブロック間では、Erdös-Renyi
random graph を仮定

ブロックの分布はＣＲＰ（≈Preferential Attachment）を仮定© NTT Communication Science Labs.

Collapsed Gibbs Sampling• 行列、両方とも一度に動く• 対角成分（self-link）はゼロを仮定© NTT Communication Science Labs.

A Bayesian Approach to Network Modularity + DPJake M. Hofman and Chris H. Wiggins, Phys. Rev. Lett. 100, 258701 (2008)「対角成分」と「非対角成分」の二種類の Bernoulli パラメータ（のみ）で、リンクが生成されると考える
対角成分のカウントはすべてのブロックに関して和をとり、まとめる

非対角成分のカウントについても、すべてまとめる• 目的関数が modularity に近い• resolution limit の問題を回避• パラメータ数が少ないため、高速© NTT Communication Science Labs.

単語連想ネットワークのクラスタリング例(1) Newman Modularity(2) ER-Mixture(3) Bayesian Modularity★ (2) (3) は尤度(1) 0.458846(2) -229109.434651(3) -227065.176490(1) 0.469602(2) -229454.252000(3) -226995.589016(1) 0.451034(2) -216655.963400(3) -215454.118461(1) 0.366086(2) -544871.856043(3) -210315.793002(1) 0.416832(2) -302196.556078(3) -205114.768975(1) 0.407359(2) -462895.811110(3) -196126.488926© NTT Communication Science Labs.

単語連想ネットワークのクラスタリング例（２）対角成分のみリンク（黒）ブロックとは限らない(1) 0.451034(2) -216655.963400(3) -215454.118461(1) 0.18102(2) -196019.767261(3) -243797.817000

対角成分が非リンク（白）ブロックとなってしまった例(1) 0.519364(2) -214157.548246(3) -234105.801714(1) -0.043643(2) -231381.906832(3) -230924.126523© NTT Communication Science Labs.

ここまでのまとめblock model

Stochastic Block Model (SBM)

IRMgraph
Erdös-Renyi mixture for graphs(ERMG)IERMG

Bayesian Approach to Network
Modularity (BNM)

IBNM

modularity

Network Modularity (NM)non-BayesianMixture model

uni-topic model
Infinite Mixturemodel© NTT Communication Science Labs.

ノードのクラスタリング

リンクのクラスタリング© NTT Communication Science Labs.

ICMc: Interaction Component Model for Communities
Inferring vertex properties from topology in large networks,J.Sinkkonen, J.Aukia and S. Kaski

無向リンクのクラスタリング（bag of links）

component wise
node degrees
link counts in z

# of nodes# of links© NTT Communication Science Labs.

リンクのクラスタリングからリンクの両端のクラスタリングへ別々のクラスタ＝（表記簡略化）© NTT Communication Science Labs.

SSN-LDA: LDA-based community discovery approach
An LDA-based community structure discovery approach for large-scale social
networks, H.Zhang, B.Qui, C.L.Giles, H.C.Foley and J.Yen
LDA を用いた、リンクのクラスタリング

topic（イメージ）

0.4
0.4
0.2
0.0
0.5
0.5
ノード毎にカウント

できるだけ少数のトピック/文書ノード
トレードオフ

できるだけ少数の単語/トピックノード
LDA = Latent Dirichlet Allocation© NTT Communication Science Labs.

リンクの両端のクラスタリングから全ノードペアのクラスタリングへ

無向リンク○無向非リンク×？

© NTT Communication Science Labs.

Mixed membership stochastic block models•Mixed membership stochastic block models for relational data withapplication to protein-protein interactions, E.M.Airoldi, D.M.Blei, S.E.Fienberg
and E.P.Xing

LDALDA

block model

LDA と block modelの融合

LDAblock model© NTT Communication Science Labs.

Mixed membership stochastic block models (2)N(N-1)/2
これらを新たにノードと考えると block model と解釈できる
ノードペア上のブロック構造

ノードペアの両端（self link なしならN(N-1)/2個）をLDA + block modelとしてクラスタリング

N(N-1)/2

HDP + IRM

Eliassi-Rad, T., Koutsourelakis, P.S. (2008). Finding Mixed-Memberships inSocial Networks. AAAI Spring Symposium on Social Information Processing © NTT Communication Science Labs.

まとめblock model

multi-topic model

Stochastic Block Model (SBM)

I(H)RMgraphmixed membership
SBM

LDA for graph(SSN-LDA)

Erdös-Renyi mixture for graphs(ERMG)IERMG

Bayesian Approach to Network
Modularity (BNM)

IBNM

modularity

HDP for graph

Network Modularity (NM)ICMc

uni-topic model

non-Bayesian

Mixture model

PLSVInfinite Mixture
modelvisualization

link clustering

Model-based clustering
for social networks

node clustering© NTT Communication Science Labs.

主な文献リスト
••
••
•
•••
••

Learning Systems of Concepts with an Infinite Relational Model, C.Kemp,
J.B.Tenenbaum, T.Yamada, N.Ueda, AAAI 2006 381-388
A mixture model for random graphs, Jean-Jacques Daudin, Franck Picard,
Stephane Robin, INRIA technical report
A Bayesian Approach to Network Modularity, Jake M. Hofman and Chris H.
Wiggins, Phys. Rev. Lett. 100, 258701 (2008)
Learning infinite hidden relational models, Z. Xu, V. Tresp, K. Yu and H.P.
Kriegel: 本質的に、IRM と同じInferring vertex properties from topology in large networks, J.Sinkkonen,
J.Aukia and S. Kaski: もっとも単純なリンククラスタリング
An LDA-based community structure discovery approach for large-scalesocial networks, H.Zhang, B.Qui, C.L.Giles, H.C.Foley and J.Yen: LDA を用いた、リンクのクラスタリング
Knowledge discovery of semantic relationships between words using
nonparametric Bayesian graph model, I.Sato, M.Yoshida and H.Nakagawa:
LDA を「無限化」してＨＤＰを用いた
Mixed membership stochastic block models for relational data withapplication to protein-protein interactions, E.M.Airoldi, D.M.Blei,
S.E.Fienberg and E.P.Xing: 一種のブロックモデル
Model-based clustering for social networks, M.S.Handcock and A.E.Raftery:「可視化」を意識
Probabilistic Latent Semantic VisualizationTopic Model for Visualizing
Documents, T.Iwata, T.Yamada and N.Ueda: 「可視化」を意識、ＰＬＳＩに近い© NTT Communication Science Labs.