Research On The Community Discovery Algorithm In Social Network

Many complex systems in the real life can be depicted as the form of networks, suchas communication networks and social networks, which belong to complex networks. Allthe complex networks follow a rule that birds of a feather flock together. And that is thecomminity structure--The memebers in the same community link densely but in thedifferent link sparsely. Community detection in complex networks has an importanttheoretical and practical significance, such as in business or services. The division of thesocial networks into several gruops can do benefit to individual recommendation andproviding personalized service, etc.The community discovery methods based on resistor network represented byWu-Huberman algorithm can partition the communities of the whole network in lineartime, but there are some defects about it which restrict its applicable scope. Thus someimprovements and innovative research are made as follows.Firstly, a community predicting method based on the candidate central nodes isproposed to solve the problem that the communities’ number needs to be given in theresistor network algorithm. It can predict the number of the communities in the networkwithout being specified by the person.Then, a method based on regarding the community core points’ voltages as thesector to find maximum voltage in the voltage spectrum is proposed to solve the problemthat the original algorithm can only discover the communities of similar size. It makes fulluse of the central position of the central nodes to find the maximum voltage, thusdetecting communities with rather different sizes.Thirdly, one critical question in the Wu-Huberman algorithm--poles picking isdeeply researched and some new problems are discovered about it. To testify the existenceof the problem, this paper propose a abstract network model and a method picking edgenodes as poles to solve it, which makes the division more accurate.Finally, by researching on the overlapping community discover algorithms comparedwith the non-overlapping ones, this paper can find the overlapping nodes between two communities based the improved Wu-Huberman algorithm, which use the nodes’distribution rule in the voltage spectrum.The rationality and validity of the proposed methods are verified on the classic realdata in the end.