数学论文_基于motif连通性的社区搜索方法
10-08文章摘要:社区搜索的目标是从数据图中得到包含查询顶点的紧密子图，在社会学、生物学等领域有着广泛应用。针对现有基于子图连通性的社区模型的基础连通结构都是完全连通图，无法满足实际应用中用户对社区结构多样性的需求，提出了一种基于motif连通性的社区搜索方法，包括基于motif连通性的MCC社区模型、相应的两个社区搜索算法——MPCS算法和基于MP-index索引的算法。MCC社区模型可以协助用户自由指定社区的基础连通结构，MPCS算法可以用来完成对MCC社区的搜索问题。进一步，提出了针对motif实例搜索过程及所属社区判断过程的剪枝优化技术。最后，设计了MP-index索引森林，避免了社区搜索过程中的冗余遍历操作。在多个真实数据集上进行实验，实验结果表明剪枝优化可以使MPCS算法耗时减少60%至85%，基于MP-index索引森林的算法相较于加入剪枝优化的MPCS算法，效率提升至少两个数量级。所提方法可在商品推荐，社交网络等问题上有着实际应用价值。
文章关键词:
论文分类号:O157.5