Research On Community Influence Maximization Algorithms And Diffusion Model

We come into the network's era as the IT is fast developing. In this era, many kinds of communication technology and internet link the whole world into a close whole. In this situation, people can conveniently exchange his/her opinion or attitude to a novelty with his/her friends. Choosing some important persons to maximize the spread of novelty's influence among the group has received a lot of attention.In this paper, we mainly research community influence maximization and we refer influence to novelty/innovation's influence. Influence maximization means to spread an influence to the members of a social network as many as possible in a given time. This is a new interdisciplinary research direction which mainly involves collective behavior, social network, innovation's diffusion etc. People propose some simple algorithm (Degree algorithm, Random algorithm) and influence's diffusion model (Threshold model in collective behavior, SIR model, Bass model, Binary influence model, Linear threshold model, Independence cascade diffusion model, Decreasing cascade model, Voter model etc). People can understand the dynamic of influence's spreading process better from those influence diffusion model.In fact, people form different social cycles or communities in real life due to the different relationships such as friendship, colleagueship, interest etc. In diffusion theory people believe that if two persons have more common characteristics such as similar opinion, belief, background etc, the interacting between these people is more likely to happen. The people in the same community have many common characteristics so the contact between these people is dense, but the people in the different community have a lot of dissimilar characteristics so the contact is sparse. Actually, there are many communities in social network. The development of social network theory has supplied many algorithms for extracting the community structure from a social network such as bisection method (Kernighan-Lin algorithm, spectral bisection methods and ICS algorithm), divisive method (GN algorithm, Radicchi algorithm) and agglomerative method (Newman fast algorithm) etc. In this paper we propose the concept of maximizing the influence's community coverage by taking into account of the advantage of these two theories.Researchers have found that the communities are the only nature obstacles to stop the influence's spread. In the sake of spreading the influence to as many communities as possible we propose two algorithms of community influence maximization and a diffusion model based on the research of collective behavior's threshold model, innovation's diffusion theory, social network theory, influence maximization, including:1. In this paper, we discuss the concept of opinion leader and its role in the spread of influence. Moreover, we also describe and analysis the process of influence's diffusion, including the node's network threshold and cascade behavior.2. To choose the best target nodes we propose the AMICS (Approach to Maximizing the spread of Influence based on Community Structure). Based on the strength of weak ties, homogeneity or heterogeneity of diffusion network and the concept of opinion leader and community structure, we first employ the community mining algorithm such as Radicchi or ICS algorithm to extract the community structure from a network, then AMICS calculate each node's community amount and iteratively choose a few important nodes which across the maximum communities to maximize the influence's community coverage.3. For the sake of evaluating node's importance more effective we propose the AMICD (Approach to Maximizing the spread of Influence based on Community Amount and Degree). Inspiriting the concept of leadership in innovation diffusion, we first employ the community mining algorithm such as Radicchi or ICS algorithm to extract the community structure from a network, then use the comND, which is the combination of node's community amount and it's degree, to evaluate each node's opinion leadership, so we can choose the best k nodes which have the highest comND to maximize the influence's community coverage.4. The power of node's influence may be change such as decrease or increase in the process of influence's spread. To deal with this situation, we propose comprehensive cascade diffusion model. We have investigated the concept of node's threshold and the cascade behavior in the process of diffusion. And we have studied the many different influence diffusion models such as Threshold model, SIR model, Binary influence model, Linear threshold diffusion model, Independence cascade diffusion model, Voter model etc. Further more, we propose the comprehensive cascade diffusion model by taking into consideration of the dynamic change of influence's strength. Our model employs the random change to simulate the dynamic change of influence's strength.We do a few experiments on a simulating dataset and two real datasets for AMICS, AMICD and Comprehensive cascade diffusion model. And we compare those results to the traditional algorithm's results and independence cascade diffusion model's results. The comparison shows our algorithms and diffusion model are feasible and effective.Community influence maximization, which introduces the concept of social network's community structure into the research of influence maximization, will have a promising development in both theory and practice. This research can improve our understanding of dynamic of the process of influence's diffusion, and it also can be used to social psychology, diffusion, public relations, advertising, marketing, customer behavior etc. Although innovation theory and social network have become two fully-fledged academic subjects, but the community influence maximization which combines the two subject's advantage is still at starting stage. We believe our investigation will shed new lights on this research and hope other researchers do more further research in this direction.