信任容量优先搜索方法：最大流优化

在本节中，我们对Advogato的最大流方法进行修改，提出了信任容量优先最大流搜索方法（Capacity-firstmaximum flow search-CFMS），来对源节点的可信用户进行搜索和排序。与Advogato方法一致，节点的信任容量越高，源节点对它的信任值也越大。

CFMS方法按照以下步骤进行。

输入：节点u，u的个性化信任网络邻接矩阵M，u的信任网络中所有节点的信任容量表CM，服务评价矩阵RM，u的信任阀值Thu，u的候选朋友集CFM。

输出：u的有序可信群体列表TruList。

1.设定节点u为源节点；

2.从邻接矩阵M读取u的所有信任容量大于Thu，且不在CFM及TruList中的1跳朋友节点进入候选朋友集CFM；

3.对CFM内的所有节点进行信任容量对比，选取出信任容量最大的节点vi，存入可信群体列表TruList；(www.xing528.com)

4.将CM中的vi信任容量减1，并在邻接矩阵M中建立vi与u的关联；

5.将vi的所有信任容量大于Thu，且不在CFM及TruList中的1跳朋友节点读入候选朋友集CFM，并在CFM中删除vi节点；

6.检查CFM中是否还有节点存在，如果有，则返回第3步，否则输出TruList列表。

当CFMS方法结束时，我们将得到源节点u的有序可信群体列表TruList。

图3-6展示了采用CFMS方法将图3-5的信任网络转换为改进后的Advogato信任网络结构，并对源用户的可信群体进行识别和排序。根据CFMS方法，我们得到的用户u的可信用户列表为B、C、G、A、D、H、E、F（限于篇幅，E、F节点没有画出）。

图3-6　采用CFMS方法对图3-5的信任网络进行转换和搜索