Research On Cognition And Evolution On Large Social Networks Based On Graph Vocabulary

With the development of online social networks, network has beenintegrated into people daily life. At the same time, network plays animportant role in special fields, such as online social network, epidemicnetwork, power network。Under the new situation, it is important to cognize the network in asimple way. The existing research work focus on graph cuts, graphcompression, community detection and so on, but the aim of theseresearch is to resolve the size of the network. The VoG(vocabulary ofgraph) is a method about cognition based on graph vocabulary proposedby Dainail from CMU. Though the method can cognize on large graph,but the role of the graph vocabulary is equal. In fact, the vocabularieshave affiliation relations which results out some error on cognition.Research work of this paper is divided into two areas, one about graphcognition and the other about evolution based on the result of step one.1) Based on the algorithms of VoG, each vocabulary has a priority. Firstdivide the graph into multi sub-community using community detection method and then labe the sub-community structure by the priority andfinally contrast the Top-k and greedy way to get the cognition.2) Basedon the key structures, the paper proposed a weighted way to measure theratio of the structures every day and using weighted way and normalizedmutual information to research the evolution of the key structures.The experiment result shows that: the greedy way of priority VoGalgorithm can achieve18%compression ratio which is better than Top-kmethod and the result also verify the most structures of microblogging isstar structure. The weighted way and normalized mutual informationmethod shows the change of evolution of experiment data is small,indicating that the relation of users is stable.