Research on Community Division Method Under Network Formal Context

doi:10.3778/j.issn.1673-9418.2006072

Abstract

Abstract:

Network community division is the basis of concept cognition and pattern learning from social networks, and is also a hot topic in the study of machine learning under the network background. In order to make full use of the advantages of formal concepts and network characteristic values, this paper discusses the problem of network community division based on network formal contexts. It firstly gives the notions of network node centrality and centralization based on the information of network structure and node attributes, which makes the division of network community in a network formal context take into account the characteristics of the network structure and node connotation. Then, the network community concept of network formal context is presented. It not only obtains the formal concept of a traditional formal context, but also includes the network characteristic values of the concept. As a result, the average importance of the concept in the network can be described as well as the different quantity between the average importances. Furthermore, considering the characteristics of multiple roles and network orienta-tion in the division of a social network, the directed network is divided into single-role network and double-role network. Besides, two network community division algorithms are proposed by combining the information of network structure and node attributes, and their time complexities are analyzed. Finally, examples are used to show the effectiveness of the proposed network community division algorithms. The obtained rusults can provide a reference for the further study of network data mining and network concept cognition.

Key words: social network analysis, network formal context, community division, formal concept, network com-munity concept

摘要：

网络社区划分是从社会网络中进行概念认知、模式学习的基础，也是网络背景下机器学习研究的热点问题。为了充分发挥形式概念和网络特征值的双重优势，基于网络形式背景研究网络社区划分问题。首先，将网络结构与节点属性信息相结合给出了网络节点中心度和中心势，使得网络形式背景的网络社区划分综合考虑了网络结构和节点内涵两方面的特征；其次，提出了网络形式背景的网络社区概念，该概念不仅给出了传统形式背景的形式概念，还包含了概念的网络特征值，可以描述该概念在网络中的平均重要度和平均重要度势差；然后，考虑到社会网络划分中多角色与网络有向性的特点，又将有向网络分为单角色网络和双角色网络，运用网络结构与节点属性信息相结合的方法提出了两种网络社区划分算法，并分析了算法的时间复杂度；最后，通过实例说明了上述网络社区划分算法的有效性。所得结论为网络数据挖掘和网络概念认知的进一步研究提供了参考。

关键词: 社会网络分析, 网络形式背景, 社区划分, 形式概念, 网络社区概念

LIU Wenxing, FAN Min, LI Jinhai. Research on Community Division Method Under Network Formal Context[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(8): 1441-1449.

刘文星, 范敏, 李金海. 网络形式背景下的社区划分方法研究[J]. 计算机科学与探索, 2021, 15(8): 1441-1449.

References

[1] ZHENG B, LIU O Y, LI J, et al. Towards a distributed local search approach for partitioning large-scale social networks[J]. Information Sciences, 2020, 508: 200-213.
[2] YANG W Y, WANG G J, BHUIYAN M Z A, et al. Hyper-graph partitioning for social networks based on information entropy modularity[J]. Journal of Network and Computer Applications, 2017, 86: 59-71.
[3] LI W M, XIE J, XIN M J, et al. An overlapping network community partition algorithm based on semi-supervised matrix factorization and random walk[J]. Expert Systems with Applications, 2018, 91: 277-285.
[4] DONG Z S, WANG S S, LIU Q. Spectral based hypothesis testing for community detection in complex networks[J]. Information Sciences, 2020, 512: 1360-1371.
[5] JIANG H, LIU Z J, LIU C L, et al. Community detection in complex networks with an ambiguous structure using central node based link prediction[J]. Knowledge-Based Systems, 2020, 195: 105626.
[6] ZHOU Z, WEI H W, XIE H L. Improved community struc-ture discovery algorithm based on penalised matrix decom-position for complex networks[J]. Microprocessors and Microsystems, 2020, 75: 103047.
[7] NATH K, ROY S, NANDI S. InOvIn: a fuzzy-rough app-roach for detecting overlapping communities with intrinsic structures in evolving networks[J]. Applied Soft Computing, 2020, 89: 106096.
[8] MA N, FAN M, LI J H. Concept-cognitive learning under complex network[J]. Journal of Nanjing University (Natural Science Edition), 2019, 55(4): 609-623.
马娜, 范敏, 李金海. 复杂网络下的概念认知学习[J]. 南京大学学报(自然科学版), 2019, 55(4): 609-623.
[9] MI Y L, LI J H, LIU W Q, et al. Research on granular concept cognitive learning system under MapReduce frame-work[J]. Acta Electronica Sinica, 2018, 46(2): 289-297.
米允龙, 李金海, 刘文奇, 等. MapReduce框架下的粒概念认知学习系统研究[J]. 电子学报, 2018, 46(2): 289-297.
[10] HUANG C C. Three-way cognitive concept learning via information fusion[D]. Kunming: Kunming University of Science and Technology, 2017.
黄晨晨. 基于信息融合的三支概念认知学习[D]. 昆明: 昆明理工大学, 2017.
[11] ZHANG W X, XU W H. Cognitive model based on granular computing[J]. Chinese Journal of Engineering Mathematics, 2007, 24(6): 957-971.
张文修, 徐伟华. 基于粒计算的认知模型[J]. 工程数学学报, 2007, 24(6): 957-971.
[12] XU W H, LI W T. Granular computing approach to two-way learning based on formal concept analysis in fuzzy datasets[J]. IEEE Transactions on Cybernetics, 2016, 46(2): 366-379.
[13] YAO Y Y. Interpreting concept learning in cognitive infor-matics and granular computing[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, 2009, 39(4): 855-866.
[14] QIU G F, MA J M, YANG H Z, et al. A mathematical model for concept granular computing systems[J]. Science in China Series F: Information Sciences, 2009, 39(12): 1239-1247.
仇国芳, 马建敏, 杨宏志, 等. 概念粒计算系统的数学模型[J]. 中国科学: F辑信息科学, 2009, 39(12): 1239-1247.
[15] SHI Y, MI Y L, LI J H, et al. Concurrent concept-cognitive learning model for classification[J]. Information Sciences, 2019, 496: 65-81.
[16] LI J H, MEI C L, XU W H, et al. Concept learning via granular computing: a cognitive viewpoint[J]. Information Sciences, 2015, 298: 447-467.
[17] ZHANG T, LI H H, LIU M Q, et al. Incremental concept-cognitive learning based on attribute topology[J]. Interna-tional Journal of Approximate Reasoning, 2020, 118: 173-189.
[18] YANG R. Research on classification rule mining algorithm based on the set of formal concepts[D]. Zhengzhou: Zheng-zhou University, 2009.
杨冉. 基于形式概念集的分类规则挖掘算法研究[D]. 郑州: 郑州大学, 2009.
[19] LI Y, LIU Z T, WU Q, et al. Research on the distributed treatment of concept lattices[J]. Journal of Chinese Computer Systems, 2005, 26(3): 448-451.
李云, 刘宗田, 吴强, 等. 概念格的分布处理研究[J]. 小型微型计算机系统, 2005, 26(3): 448-451.
[20] WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[C]//LNCS 5548: Proceedings of the 7th International Conference on Formal Concept Analysis, Darmstadt, May 21-24, 2009. Berlin, Heidelberg: Springer, 1982: 445-470.
[21] NEWMAN M E J. Networks: an introduction[M]. Oxford: Oxford University Press, 2010.