next up previous
Next: Up: ϵľ̬ Previous: ϵľ̬

ĿǰѵõоĵInternet磬ӰԱ磬ѧҺ磬Թϵ磬ʻ磬 ѧ磬۵ϵ硣

Ļ[1,2]Уȼֲȵԣ۳̶ȼֲ̾뼰ֲBetweenness ֲͨŵĹģֲ

һĶָ˶ӵıߵ

dv = $\displaystyle \sum_{{l\in E}}^{}$$\displaystyle \delta^{{v}}_{{l}}$, (1)
$ \delta^{{v}}_{{l}}$ǺȡֵΪ1lvΪ㣬

$\displaystyle \delta^{{v}}_{{l}}$ = $\displaystyle \left\{\vphantom{ \begin{array}{ll} %array ʾĿʼ,ll˵... ...vetex $v$\ included in edges $l$} \\ 0 & \mbox{if not} \end{array} }\right.$$\displaystyle \begin{array}{ll} %array ʾĿʼ,ll˵,. 1 & \mbox{if vetex $v$\ included in edges $l$} \\ 0 & \mbox{if not} \end{array}$; (2)
ͬʱΪԺ㣬Ƕ͵$ \delta$Ǻţ $ \delta^{{uv}}_{}$ $ \delta_{{lm}}^{}$ֱʾһе 磬 $ \delta^{{uv}}_{}$ $ \delta^{{vu}}_{}$ֱʾuvӺͱʾvuӣ $ \delta_{{lm}}^{}$ƹΪ $ \delta_{{l\rightarrow m}}^{}$,$ \delta_{{l\leftarrow m}}^{}$,$ \delta_{{l\rightarrow\leftarrow m}}^{}$$ \delta_{{l\leftrightarrow m}}^{}$ ڼȨ磬üǺ Wuv$ \delta^{{uv}}_{}$ $ \delta^{{uv}}_{}$ͿWuvʾuv֮ӵȨء

$ \forall$v $ \in$ VǶԵõdvֵķֲҪʡֵͬ$ \delta$ֲ ϲɷֲ3.1ڣʵʽĶȷֲ[1,2]Ϊޱ 磨Scale Free NetworksInternet[44,45]ӰӾԱ[18,32,46]ѧҺ[66,67] Թϵ[47]ʻ[48]ѧ[49]ȣͬʱڸ˹ ͣ絰۵[46]ָ˥͵ĸʷֲӾԱ[46]

һǣǷȷֲ걸أȷֲһһӦǾ˵ȷֲ磬Ҳֻ ҪöȷֲһĶȷֲͨǿԸӦÿһһֵֵֶһӷʽ һ硣һӶӦһΪʵΪͬһ硣Ȼܱ֤Ҳһô ֵֶӣ֮ûԣǷԳΪĴأԶȷֲ֮һҪļ NewmanΪƥģʽ[16]˼ǿֵĵںͶֵĵӣںͶֵСĵӡķǣͨһ ߶ҵ㣬õֵͨеıǾ͵õУеԼɡоʵ һ̶ϵƥģʽеƥ䣬Ҳе練ƥ䡣ǣ磬һĶȷa һĶȷbģһԷӰ첢ûеõоʵķͬڲͬƥ ģʽҲиء

۳̶ȵ缯Żij̶ȣһļŸԵĽ֮жǹͬĽڡһֶǶÿһv ڼNv n = $ \left\vert\vphantom{N_v}\right.$Nv$ \left.\vphantom{N_v}\right\vert$NvдڵıߵΪ

M = $\displaystyle \sum_{{l\in E; x,y \in N_v}}^{}$$\displaystyle \delta^{{x}}_{{l}}$$\displaystyle \delta^{{y}}_{{l}}$, (3)

Cv = $\displaystyle {\frac{{M}}{{C^{2}_{n}}}}$. (4)
ǿԵõжļ۳̶ȣͳƷֲǿ̻һҪƽֵΪƽ۳̶C

·lijΪͨ $ \left(\vphantom{i,j}\right.$i, j$ \left.\vphantom{i,j}\right)$ͨ·Уٵһ· $ \left(\vphantom{i,j}\right.$i, j$ \left.\vphantom{i,j}\right)$ ֮·ļΪSijӦ·Ϊ dij = $ \left\vert\vphantom{l_{ij}}\right.$lij$ \left.\vphantom{l_{ij}}\right\vert$ $ \left(\vphantom{i,j}\right.$i, j$ \left.\vphantom{i,j}\right)$֮䲻ͨ·ôdij = NǿԵõ һN x Nľ $ \left(\vphantom{d_{ij}}\right.$dij$ \left.\vphantom{d_{ij}}\right)_{{N\times N}}^{}$ֲһҪȫּƽֵΪƽ·d

һҪȫּǽBetweenness[17]uĽΪе·֮Уu ӳ˶uӰ $ \left(\vphantom{i,j}\right.$i, j$ \left.\vphantom{i,j}\right)$֮·ļΪSijuĽΪ

Bu = $\displaystyle \sum_{{i,j}}^{}$$\displaystyle {\frac{{\sum_{l\in S_{ij}}\delta^{u}_l}}{{\left\vert S_{ij}\right\vert}}}$. (5)
ɴ˿ԵõÿһĽBvʵ֤оʵĽֲҲӵйͬͳ[17]Ƶأ ԶߵĽNewman˷֣ߵĽڷľ[24]˼ڰͬŵ ·ıߣҲǽıߣȻ֮ıߡȻӸȨϵ Hierarchical Clustering㷨Ҳܸ϶ķࡣ

ָͨGһͼͼڣ֮䶼ͨ·һܴڶ໥ͨšģУ ϵͳٽ״̬ʱͨŵĹģֳʷֲʵ֤оڴScale-free 磬ͨŵĹģҲʷֲ[1]

ĶȷֲһʽڶĿõֵȻжĶֵһٰѽڶĶֵӵ Ķζֵظ һֱ̣õȶĶֵ[6]õÿһĶֵʵڽӾֵӦıʵϾǾ ֵ½ĶȷֲеļĿǰûеõо


wwwwjs 2004-01-04