一种基于模糊相似关系的局部社区发现方法

Local Community Discovery Approach Based on Fuzzy Similarity Relation

近几年,在线社交媒体发展飞速,出现了大规模社会网络.传统的基于网络全局结构的社区发现方法难以有效地处理这些大网络.局部社区发现作为一种无需知道网络的全局结构、仅通过分析给定节点的周围节点之间的关系即可找出给定节点所在社区的方法,在社会网络大数据分析中具有重要的应用意义.针对真实世界网络结构中个体间的相似关系是模糊的或不确定性的,提出了一种基于模糊相似关系的局部社区发现方法.首先,采用模糊关系来描述两个节点之间的相似关系,以节点对的相似度作为该模糊关系的隶属函数;然后证明了该关系是一种模糊相似关系,将局部社区定义为给定节点关于模糊相似关系的等价类,进而采用最大连通子图算法求得给定节点所在的社区.分别在仿真网络和真实网络上进行了实验,实验结果表明,该算法能够有效地揭示出给定节点所在的局部社区,相比其他算法,具有更高的F-score.

Online social media has developed rapidly in recent years,and many massive social networks have emerged.Traditional community detection methods are difficult to deal with these massive networks effectively for requiring knowledge of the entire network.Local community detection can find out the community of a given node through the connection relationship between the nodes around the given node without knowledge of the entire network structure,so it is of great significance in social media mining.For the relations between pairs of nodes in real-world networks are fuzzy or uncertain,the similarity relationship between two nodes with fuzzy relation is firstly described,and similarity between nodes as membership function of the fuzzy relation is defined.Then,it is proved that the fuzzy relation is a fuzzy similarity relation,and local community is defined as the equivalence class of the given node about fuzzy similarity relation.Moreover,local community of the given node is discovered by adopting maximal connected subgraph approach.The proposed algorithm is evaluated on both synthetic and real-world networks.The experimental results demonstrate that the proposed algorithm is highly effective at finding local community of the given node,and achieves higher F-score than other related algorithms.