Detecting Communities From Social Network Based On Multi-agent

With the rapid development of Internet technology, real-time communication and freeinteractive platform provide great convenience for human communication. Against thebackdrop of Internet Age, research on social networks has attracted increasingly moreattention from scholars and become a research hotspot. Based on social network analysis, wecan mine data and information hidden behind a network, explain its formation and evolution,and predict its changing trend, which are important in the theoretical study and practicalapplication.Network structure analysis as a basis of social network research has obtained certainachievements in recent years. With the appearance of the small-world phenomenon and scalefree characteristics,Girvan and Newman are the first to point out the community structure is aubiquitous structure in social networks, which opens the door to the research on community.Community structure is one of the most common forms of social networks, and has thecharacteristic of dense connections within the community and sparse connection betweencommunities. Based on this characteristic, a lot of community detection algorithms have beenproposed by researchers. However, most algorithms in existence are centralized method,which means that to discover community structure hidden within complex networks, theinformation of the whole network need to be known. This requirement is demanding becausethe global information of network is hard to obtain when the network is large. Besides that,the existing methods only take the information of link into consideration, omitting itssignificance. In social network, link represents not only the active relations of fondness, trustand kindness, but also the passive relations of disgust, distrust and hostility. The existingcommunity discovery algorithms process the social networks into a simple binary networkand lose all the negative connection information. The community obtained does not reflect thetrue network structure.Based on the above issues, this paper proposes a community detection algorithms basedon local search by avoiding the need to obtain global information and able to handlecommunity detection of unsigned network and signed networks. The main contributions in thethesis are as follow:(1) Based on the existing community detection algorithms need to know global information, this paper proposes a local optimization algorithm based on multi-agent. Thisalgorithm overcomes the deficiency of centralization. Firstly, the proposed method has a set ofautonomous agents randomly are dispersed throughout the network. Next, in order to optimizethe local objective function, each agent node uses the local connection information to updatethe node’s label. Finally, agent transfers to the next node through the connection and continueto optimize the local objective function. This group of agents walks on the network andfinally is able to get the optimal value of objective function and get the ideal communitystructure. The method using the limited local information could find the network communitystructure and has high accuracy.(2)Due to the differences of community structure in unsigned network and signednetwork, different objective functions are proposed together with a versatile optimizationstrategy. So this method can not only deal with community detection problems in unsignednetwork, but also in symbolic network. Finally, the validity of the algorithm is verified withthe help of real-world data sets. The comparison of the results of the calculations and theexperiments indicate that the proposed algorithm is of great accuracy and efficiency.