Influence maximization in online social networks (OSNs) is the problem of discovering few nodes or users in the social network termed as ‘seed nodes', which can help the spread of influence in the network. With the tremendous growth in social networking, the influence exerted by users of a social network on other online users has caught the attention of researchers to develop effective influence maximization algorithms to be applied in the field of business strategies. The main application of influence maximization is promoting the product to a set of users. However, a real challenge in influence maximization algorithms to deal with enormous amount of users or nodes obtainable in any OSN is posed. The authors focused on graph mining of OSNs for generating ‘seed sets' using standard influence maximization techniques. Many standard influence maximization models are used for calculation of spread of influence; a novel influence maximization technique, namely the DegGreedy technique, has been illustrated along with experimental results to make a comparative analysis of the existing techniques.
TopIntroduction
The conceptualization of Online Social Networks (OSNs) has been one of the most stimulating events in this century. A social network can be considered to be any website or web application which allows for social experience in the form of user interactions. Nowadays, such online social interactions have led to several amusing online activities including posting photos, chatting, tweeting, online shopping, etc. Many popular OSNs such as Facebook, Orkut, Twitter, LinkedIn and YouTube have become more popular day-by-day. Statistics reveal that currently over 75% of all Internet users are also profoundly engaged in using social media sites [1]. Growth in usage of social media emerged mainly due to the heavy increase in the usage of smart phones, tablets, laptops, and other similar gadgets, which has become one of the defining factors in advancement of human life.
Social Network Analysis and Mining
In this new era, where social networking has gained huge popularity, social media marketing has also become a major business strategy. Social media marketing is a form of marketing that makes use of the social networking sites as a marketing tool to increase brand exposure and to expand customer reach. As a result, the vast amount of content-rich data retrieved from such OSNs is considered to be a wealth of information that is analyzed using data mining techniques for various analytical researches. This social data is generated as a result of various implicit and/or explicit user activities such as purchasing of products, rating an item, liking an image, chatting with others, posting tweets, and so on. However, the real challenge lies in how to accurately and efficiently analyze and process such data to extract meaningful and valuable patterns or knowledge. It is also important to note that OSN data used in various researches is noisy, enormous, scattered and dynamic. To analyze such vast, complex, and regularly changing raw data requires proper data mining techniques, commonly known as social network mining. Social Network Analysis and Mining (SNAM) is one of the hot topics in the area of research in data mining and it is still in its infancy.
Influence Maximization
Currently, as OSNs have become a daily activity for majority of the Internet users, the latter largely rely on making decisions based on the influence of such sites. For instance, influence propagation helps a social network user to consciously or unconsciously decide in making a choice on which product to buy, which movie to watch, which community to join, which programmed to participate in, and so on. Patterns of influence can also be studied as an indication of user trust and utilized for computing trust propagation. For instance, a user „X‟ writes in her timeline about a movie that she recently watched and liked. This update gets communicated to many of her online friends who read her update. When few such friends give a comment on that update, the information is passed on to their friends, and this becomes a chain process. Thus, an update has the potential to be propagated positively through a social network.
A major goal of influence maximization is „viral marketing‟ or „viral advertising‟, which is nowadays considered a major marketing technique being adopted by every company and organization to promote their products or brands, or to create awareness about their organization (Ahamed, B. B., & Ramkumar,2016). The basic principle of viral marketing is to initially find a set of few influential users of a particular social network, and convince those users about the goodness of a product (one way of doing so is to supply free samples of the product), so that it can generate a cascade of influence among the users’ friends who will, in turn, recommend the same product to other friends, and this will result in a grand promotion of the product. But the major issue lies in initially finding the best influential users in the social network, who are considered as the „seed set‟ of the network. A similar strategy of viral marketing via social networks is also adopted in political campaigns or personalized recommendations.
Figure 1.
The generic influence maximization framework