实例
如下有三个网页A，B，C及其链接关系：
构造邻接矩阵（Adjacent Matrix）：
A=⎡⎣⎢110100110⎤⎦⎥
A
=
[
1
1
1
1
0
1
0
0
0
]
<script type="math/tex; mode=display" id="MathJax-Element-232">
A=
\begin{bmatrix}
1 & 1 & 1 \\
1 & 0 & 1 \\
0 & 0 & 0
\end{bmatrix}
</script>
每个节点都有一个Hub分数和Authority分数，所以有一个Hub向量
h
h
<script type="math/tex" id="MathJax-Element-233">\mathbf{h}</script>和Authority向量
a
a
<script type="math/tex" id="MathJax-Element-234">\mathbf{a}</script>，向量的每个元素都初始化为
1n√
1
n
<script type="math/tex" id="MathJax-Element-235">\frac{1}{\sqrt{n}}</script>，其中
n
n
<script type="math/tex" id="MathJax-Element-236">n</script>为节点数：
h0=⎡⎣⎢⎢⎢13√13√13√⎤⎦⎥⎥⎥,a0=⎡⎣⎢⎢⎢13√13√13√⎤⎦⎥⎥⎥
<script type="math/tex; mode=display" id="MathJax-Element-285">
\mathbf{h}_0=
\begin{bmatrix}
\frac{1}{\sqrt{3}}\\
\frac{1}{\sqrt{3}}\\
\frac{1}{\sqrt{3}}
\end{bmatrix}
, \quad
\mathbf{a}_0=
\begin{bmatrix}
\frac{1}{\sqrt{3}}\\
\frac{1}{\sqrt{3}}\\
\frac{1}{\sqrt{3}}
\end{bmatrix}
</script>
按如下方式交替更新
h
h
<script type="math/tex" id="MathJax-Element-286">\mathbf{h}</script>和
a
a
<script type="math/tex" id="MathJax-Element-287">\mathbf{a}</script>的值：
h1a2=Aa0=ATh1(41)
(41)
h
1
=
A
a
0
a
2
=
A
T
h
1
<script type="math/tex; mode=display" id="MathJax-Element-462">\begin{equation}
\begin{aligned}
\mathbf{h}_{1} & =A \mathbf{a}_0 \\
\mathbf{a}_{2} & =A^T \mathbf{h}_1
\end{aligned}
\end{equation}</script>
过程如下，直到任一向量不再变化（收敛）：
需要注意的是每一步都需要对得到的向量进行归一化：
f(v)=⎡⎣⎢⎢⎢⎢⎢⎢⎢v1n√v2n√⋮vnn√⎤⎦⎥⎥⎥⎥⎥⎥⎥
f
(
v
)
=
[
v
1
n
v
2
n
⋮
v
n
n
]
<script type="math/tex; mode=display" id="MathJax-Element-374">
f(\mathbf{v})=
\begin{bmatrix}
\frac{v_1}{\sqrt{n}}\\
\frac{v_2}{\sqrt{n}}\\
\vdots \\
\frac{v_n}{\sqrt{n}}
\end{bmatrix}
</script>
Python代码
分析
考虑两步，则：
a2=AT(Aa0)=(ATA)a0
a
2
=
A
T
(
A
a
0
)
=
(
A
T
A
)
a
0
<script type="math/tex; mode=display" id="MathJax-Element-475">
\mathbf{a}_2 = A^T(A \mathbf{a}_0)= (A^TA) \mathbf{a}_0
</script>
h3=A(ATh1)=(AAT)h1
h
3
=
A
(
A
T
h
1
)
=
(
A
A
T
)
h
1
<script type="math/tex; mode=display" id="MathJax-Element-573">
\mathbf{h}_3 = A(A^T \mathbf{h}_1)= (AA^T) \mathbf{h}_1
</script>
所以最终得到的
h∗
h
∗
<script type="math/tex" id="MathJax-Element-574">\mathbf{h}^*</script>是
AAT
A
A
T
<script type="math/tex" id="MathJax-Element-575">AA^T</script>的主特征向量，
a∗
a
∗
<script type="math/tex" id="MathJax-Element-576">\mathbf{a}^*</script>是
ATA
A
T
A
<script type="math/tex" id="MathJax-Element-577">A^TA</script>的主特征向量。主特征向量也就是最大的特征值对应的那个特征向量。
References
Hubs and Authorities
7
0
已为社区贡献5条内容
所有评论(0)