Contributions To Several Issues Of Community Detection And Community Deception

Complex networks play a vital role in many areas,ranging from social sciences,bioinformatics and computer sciences.In networks,community structures provide a significant clue to understand structural and functional properties of complex networks.The methods for detecting community structures can be very useful for interpreting network data.Due to the rapid development of community detection technologies,we can easily find friends on social networks and can be recommended nice items on e-commerce sites.However,it also arises the concerns that individual information may be over-mined,e.g.,a user’s interest can be inferred by mining the websites he/she browses.Criminals can use those information to adopt malicious marketing and even commit fraud.So,in this dissertation,we study the topics of community detection as well as community deception.The details and main contributions are summarized as follows:First,we propose overlapping community detection methods based on Local link structures.The existing community detection methods suffer from two issues: incorrect base-structures and incorrect membership of weak-ties.To resolve both problems,we introduce local link structures(LLSs)based on the cosine similarity.Then,we transform mining LLSs as a cosine pattern mining problem.Moreover,we prove that LLS with an appropriate threshold can filter weak-ties.Finally,we construct a hypergraph to assemble all local link structures and employ hypergraph partitioning and hypergraph embedding methods to detect true community structures in real world networks.Second,based on the weighted modularity and game theory,we propose a method to detect crisp community as well as overlapping community structures.Firstly,we apply cosine similarity to determine the edge weights which can resolve the resolution limit problem to a great extent for modularity.Then we transform the community detection as a game theory problem in which each player’s goal is to maximize their profits.Meanwhile,we prove that the function based on the weighted modularity is the potential function.Finally,we propose a local moving heuristic based on the potential game to detect crisp communities and overlapping communities.Third,we propose two methods for community deception based on multi-objective reinforcement learning.Previous works on community deception focus on modifying existing graph structures,which is infeasible in most real-world applications.In contrast,it is more practical to inject nodes and edges into existing graphs.Firstly,we model community deception as the network growth model and introduce two deception measures based on ratio association and ratio cut.Then,based on reinforcement framework,we define the action space as the different models of network growth,state as the performance vector of the agent’s latest l strategies and reward as the vector of two deception measures.Finally,we adopt two strategies to optimize the two objectives,i.e.,scalarized multiobjective Q-learning and pareto optimized multi-objective Q-learning.