Research On Maximal Faction Detection And Evolutionary Algorithms In Online Social Networks Based On Formal Concept Analysis

In recent years,with the rapid development of Internet and the increasing popularity of smartphones,tablet PC,and laptops,Online Social Networks(OSNs)has become a way of accessing news,making friends,and disseminating information and videos in people's daily life.It is also regarded as one of the important channels for communication,entertainment and relaxation.OSNs has become a trending topic in the studies and applications of computer science,sociology,management,psychology,and human behavior.Considering that OSNs would evolve with time and human behaviors,its structure became complicated and massive with quick information spread and quantity increase.Therefore,the behaviors of OSNs users in terms of personal behaviors,dating interactions,content creations,information spread,and group meetings would have an impact on a lot of national aspects,including information safety,economic development,social stability,and political health.The booming development of OSNs applications has attracted the attention of scholars in various fields.In the field of computer science,the use of various computer data analysis methods to study OSNs is endless.This article will use graph theory and formal concept analysis methods to study maximal clique detection and evolution analysis of OSNs.The problem of maximal cliques mining is a very important research issue in graph data mining.One of the most critical aspects of this research is how to quickly identify maximal cliques from graph data.And for the maximal cliques mining of OSNs,we must take into account the complexity and variability of OSNs.To this end,this paper uses the Formal Concept Analysis(FCA)method to transform the maximal cliques mining problem of OSNs to the analysis of the corresponding concept lattices of online social networks.In this paper,two concept lattice generation algorithms are designed:Add-FCA and Dec-FCA,which are respectively suitable for the detection of maximal cliques in OSNs when users increase or decrease.The advantage of this algorithms are that it does not need to construct the formal context of OSNs with users changing,but to obtain new concept lattices by using the existing concept lattices,so as to further save time and effectively detect the maximal cliques,and describe the evolution process of the maximal cliques in OSNs.In this thesis,the mathematical correctness proof of the proposed algorithm is given,and the efficiency of the algorithm is verified by experiments.In the process of detecting maximal cliques,using the equivalence of equiconcepts and maximal cliques,studying the evolution of the equiconcepts,we discovered four evolutionary ways of maximal cliques:unchanged maximal cliques,changed maximal cliques,newly added maximal cliques,vanished maximal cliques.And through multiple experiments,the number of equiconcepts and maximal cliques in the experimental data augmentation were studied,and the identity relationship between these four maximal cliques and the number of maximal cliques of online social networks before and after the user are changed.In addition,the Add-FCA algorithm and the Dec-FCA algorithm proposed in this paper can be applied not only to OSNs,but also to the generation concept lattice when objects/attributes of the formal context changed.The main contributions of this thesis are:1.Two concept lattice generation algorithms are designed for dynamically changing formal context:Add-FCA and Dec-FCA.Among them,Add-FCA is the concept lattice generation algorithm of the formal context dynamically increased by objects or attributes and Dec-FCA is the concept lattice generation algorithm of the formal context dynamically reduced by objects or attributes.In this thesis,the concrete steps and mathematical correctness of the algorithm are given,and the correctness and efficiency of the algorithm are tested experimentally.2.Combining the graph mining problem with the problem of studying concept lattice,a new maximal cliques detection algorithm is designed:the problem of detecting maximal cliques in OSNs is transformed into the problem of detecting the equiconcept of the corresponding concept lattice in OSNs by using the equivalence relation between maximal cliques and the equiconcept.3.The evolution process of maximal cliques is classified into four different types of maximal cliques evolution(UE,CE,AE,VE),and the quantitative relationships between the four types of maximal cliques and the initial maximal cliques are derived.