| With the rapid development of Internet technology,a variety of social networking sites and new social media is rapidly spreading among people.The analysis of social networks has attracted more and more attentions of all walks of life.As an important means of social network analysis,community detection has been a very popular field of study in recent years.Traditional community discovery methods is mostly non-overlapping community detection methods,and focuses on only one kind of network relationship among people.In reality,the community structure of the social network is often overlapping,which means an individual may belong to multiple communities,and people interact with others in various ways.Only considering a single type of network relationship can most likely caused inaccurate results because of insufficient information.In this paper,the following three aspects are studied on the overlapping community detection of single-relational social network and the non-overlapping one of multi-relational social network : 1.The traditional seed expansion based overlapping community discovery algorithm completes community discovery through greedy expansion after selecting seed nodes,It usually can not guarantee the centrality of selected seed nodes,and greedy expansion is likely to cause improper subsequent expansion due to errors in the first expansion.In view of the above two defects,this paper proposes a new overlapping community discovery method based on seed node expansion(OSE).To begin with,OSE introduced a random walk on the network before the community was discovered to reduce the impact of network noise on the inaccuracy of community discovery.Then I combine the clustering algorithm Fast Search and find of Density Peaks to calculate the center value of the network node and select the seed node to ensure the centrality of the selected seed.Finally,by calculating the average similarity,I select a part of the neighboring nodes to join the seed node to form a central area and carry on greedy expansion.The experimental results show that compared with some traditional algorithms,the method has some improved function in accuracy and anti-jamming ability.2.Inspired by the above idea of seed expansion,we propose a multi-relational social network community discovery method based on seed community expansion(Multi-SC).To begin with,Multi-SC method collect community information of each relation in the network and choose individuals who are in the same community in all relationships to form a seed community set.Then,I improved Jaccard similarity function considering the similarity degree effects from correlation coefficient of two node belonging to the same community and the degree of tightness between their public neighbors.A method of calculating node similarity in multi-relational social network is proposed and the similarity between communities is calculated based on this.Finally,seed community is completed based on the improved similarity function and a kind of local fitness function.Experiments on artificial networks and real social networks show the more accuracy of the algorithm compared to some existing methods in the medium and low noise environment.3.Most of the existing community division approaches of multi-relational network do not take into account the differences between social relationships,which will cause the lower accuracy of multi-relational community detection than single-relational community detection under the condition of some strong relationship’s noise.In order to solve the above problem,I proposes a multi-relational community detection method based on multi-objective evolutionary(Multi-MOE).The main idea of our algorithm is to reflect the importance of each relationship in the community division by giving different weights to different relationship.To begin with,two optimization objective functions are established based on the module density function D and the normal mutual information function NMI.Then the weight ratio of each relationship in the network are seen as the decision variables of objective function.The multi-objective genetic algorithm is used to optimize the objective function to obtain the optimal weight ratio of each relation.Doing so to integrate the multi-relational network into a single-relational network which can both effectively integrate different relation community and reduce the noise brought by the single relationship.Finally we use the traditional single-relational community discovery algorithm BGLL to get the final result.Artificial network and real social network experiments show that this method has improved accuracy and stability in community detection compared with some existing multi-relational community discovery methods.Especially in the case of noise gap between relationship is relatively large,the method can still maintain a high accuracy. |
