Sign Social Network Community Structure Discovery And Symbol Prediction Research

In social networks,members not only have positive social relations such as cooperation,friends,support and likes,but also have negative social relations such as competition,enemy,opposition and hatred.This kind of network with both positive and negative social relations is called signed networks.Signed networks have become one of the hotspots for domestic and foreign scholars since it contains more comprehensive social relations.As the basis of signed network analysis,community structure and sign generative mechanism have theoretical and practical significance for understanding the organizational structure of social system and improving the level of social service.In this paper,the structure of signed social networks is analyzed from two parts: community discovery and sign prediction.In the research of community discovery,evolutionary algorithms have incomparable advantages in operative efficiency compared with others.During evolution,only one interaction mode is considered,which avoids a lot of complex computation.This makes the evolution only a process of updating nodal state in time.Due to evolution,the nodes belonging to the same community will converge uniformly because of the close connection or mutual attraction,while the nodes belonging to different communities will converge differently because of the loose connection or mutual exclusion.To overcome the shortcomings of existing algorithms,a new evolutionary mechanism is proposed.The changed value of nodal state is the sum of the influential weights of all its neighbors.In order to eliminate the influence of initialization on evolution,the initial state of the network is a unit matrix,that is,each node belongs to a unique community at the initial time.For further improve the cohesion of the community,the node always chooses the best community to get the highest degree of balance.Since the evolution of each node is consistent with the goal of partitioning,any nodal evolution will increase the objective's value.Thus,the network will eventually enter a convergent state.Moreover,during the evolutionary process,the evolution of a node wills directly affecte its neighbors,so the evolution has a cumulative effect and the denser the network,the faster the convergence rate.In order to exclude the influence of random evolution maximizing the degree of balance,the merging conditions are set for cross-communities.From the experimental results,the new evolutionary algorithm is superior to existing algorithms in the evaluation indexes of balance,signed modularity and normal mutual information.The following is the analysis on the discovered community structure:(1)The embeddedness of community structure is analyzed.By defining the concept of positive and negative fitness of nodes in the community,it is found that nodes can be divided into two categories according to the degree of embeddedness in the community.One kind of node has a higher degree of embeddedness in the community,and it has a higher degree of positive fitness in the community,such nodes are often ingeniously embedded in the community.The other type of node is ingeniously embedded in the community.The degree of embeddedness is low,and it has a low positive fitness in the community,even in other societies,there is still a positive fitness,such nodes are often located at the junction of the community,acting as intermediaries.By defining the concept of inter-community density,we find that the relationship between communities in the network is not equal.There are confrontations or dissimilarities between some communities,which are obviously weaker than those between other communities.(2)The evaluation criterion of community structure—balance and signed modularity,are compared from two aspects,one is balance and modularity,the other is metrics and mode.It is found that signed modularity index tends to divide the network into smaller communities,while balance index does not,and it has no obvious restriction on the size of communities.When evaluating the community structure by balance,the overall goal is consistent with the goal of a single node;while when evaluating the community structure by signed modularity,a single node does not have modularity.(3)We analyse overlapping communities from the perspective of structural balance,proposes a conflict edge mining algorithm,and applies it to the international military alliance and confrontation network,and analyse the nature and application of overlapping nodes.Based on the spectral characteristics of the adjacency weighted matrix of signed networks,by analyzing the relationship between the eigenvectors and the network balance,we find that the balance of edges can be measured by their corresponding eigenvector elements.Thus,the hierarchical spectral algorithm based on the principal eigenvector and the hierarchical spectral algorithm based on the top-k eigenvectors are proposed:(1)In Section 4.2,it is analyzed that when the network is partitioned into two communities,the main eigenvector of its adjacency weight matrix can be used as an indicator of community structure,and the nodes corresponding to positive elements are one community,and the nodes corresponding to the negative elements are another community.For each community,it can be partitioned into two sub communities by calculating the main eigenvector of the adjacent weight matrix of its corresponding sub network.In this way,the idea of hierarchical partition is used to discover the community structure of signed network.(2)Respect to the analysis,each eigenvector can partition the network into two communities,and the balance of the partition of different eigenvectors corresponds to their eigenvalues,that is,the larger the eigenvalues,the higher the balance of their corresponding eigenvectors.Therefore,we can gradually increase the eigenvector to find the community structure with the highest balance.In Section 4.3,different artificial signed networks are generated to verify the rationality of the partition based on the eignvectors.(3)Due to the continuity of the element value of the eigenvector under the standardized condition(the element value is greater than-1 and less than 1),when the element value is approximately 0,it will inevitably cause the partition error.In this paper,the optimization stage is designed according to the objective function.During the optimization,the fitness of each node in its community is calculated.If the fitness of the node in other communities is greater than that in its community,it is adjusted to the community with the largest fitness.When the nodes adjust their communities,only local(neighbors around the nodes)calculation is carried out,which makes the efficiency of the optimization stage very high,which is proved in the experiment in Section 4.3.In this paper,a highly symmetrical quadrilateral structure is proposed by analyzing the generation mechanism of edge signs,which conforms to the theory of social balance and the theory of social status at the same time.Therefore,it can effectively filter the interference factors caused by the complexity of network connection,thereby extracting the similarity and dissimilarity between nodal pairs that can effectively reflect the generation mechanism of edge signs.In addition,by analyzing the positive and negative degrees of nodes in real large-scale signed networks,the preference and reputation that can effectively reflect the attitudes of nodes are proposed.A prediction model of edge signs based on the above four factors is constructed.The simulation experiments on three real large-scale signed social networks and the comparison with the results of existing prediction methods prove the scientificity and rationality of the prediction model.The complexity of the prediction algorithm is analyzed.Since the factors that make up the prediction model reflect the local structural features of the target edge,the complexity of the prediction algorithm is very low and suitable for large-scale signed networks.