An Influence Maximization in Social Networks Based on Community Structure (IMSC)

By adding billions of devoted users, social networks have developed into potent platforms for disseminating knowledge and marketing. The social impact, which charts the interactions between people in the network and can be assessed based on reputation and trust, is an underlying factor supporting the capabilities [1]. Marketing, which recognizes the significant impact of "word-of-mouth" that develops the interpersonal influence of relationships with customers and can change consumers' attitudes and behaviors, is a common application that social networks encourage [2, 3].

The proliferation of internet communication channels has facilitated the quick and straightforward transmission of emotions, information, ideas, and other experiences, which has given influence over decisions to buy (or adopt) products a significant amount of weight [4]. Even though social influence has always been acknowledged as a component in decision-making, contact can now be easily traced because of conveniently accessible internet customer footprints. Social networks are essential for transmitting knowledge, influence, and opinions among their users. As a result, there is a lot of interest in comprehending the dynamics of adoption within a social network because it could provide information on more effective marketing tactics.

Through word-of-mouth, the social network is exposed to influence or information [5]. A significant problem in analyzing and researching the social network is information dissemination. Based on this topic, the influence maximization (IM) problem is created. With IM, the issue is reaching a select group of power users who can disseminate their influence throughout the network the fastest [6, 7]. Numerous uses for choosing influential users exist, including network monitoring, social recommendation, rumor management, viral marketing, and income maximization.

Promoting and selling their products are essential to the survival of many commercial enterprises. For this reason, they are always looking for new strategies to advertise their products efficiently. This goal might be attained by word-of-mouth and the appropriate context-based dissemination of advertising messages by carefully chosen individuals [8]. Online social networks are suitable options for disseminating product marketing. These networks' captivating surroundings have drawn many users, multiplying daily. The characteristics of online social networks, where a seed set of users is chosen to start distributing the content on the network, can significantly assist viral marketing [9, 10]. There are only a few seed members because businesses have restricted advertising expenditures. Here, the issue of efficiently finding the most influential users and adding them to the seed set arises. A group of k users on which the spreading process is started must be identified to solve the IM issue, which is what this issue is known as. Although user behavior and interests have been considered essential components in the spreading process in various techniques, such information is only sometimes present in actual networks. Therefore, to identify prominent users, we frequently only have network structural information at our disposal [11, 12].

The Influence Maximization with Monarch Butterfly Optimization Algorithm (IMSC) is a novel strategy aimed at enhancing the identification of influential nodes within communities. Building on the foundations laid by recent advancements in network analysis, IMSC offers a promising solution to the challenges posed by existing methods. Community structure identification, a crucial initial step, has often been approached with conventional algorithms. IMSC, however, employs the Monarch Butterfly Optimization Algorithm to delineate community boundaries meticulously. This ensures a more accurate representation of social clusters and serves as a departure from the limitations associated with some widely used techniques [13]. Furthermore, IMSC's candidate generation phase optimizes the selection of potential influencers within identified communities. Unlike traditional methods that may rely on heuristic approaches, IMSC's use of the Monarch Butterfly Optimization Algorithm enables a more nuanced network exploration, systematically identifying individuals with a higher potential for influence. Seed node selection, the ultimate determinant of influence spread, has often been approached with a one-size-fits-all mindset. IMSC, in contrast, tailors its seed node selection based on the specific characteristics of each community [14]. This strategic approach, facilitated by the Monarch Butterfly Optimization Algorithm, not only enhances the precision of influence maximization but also marks a departure from rigid methodologies.

1.png

Figure 1. Architecture diagram for the proposed algorithm

To notice the problem of the IM problem, focusing on the diffusion of influence, we offer a novel strategy in this study called IMSC. The three phases of our IMSC approach—candidate generation, community detection, and seed selection—are shown in an overview in Figure 1. In the IMSC, various problems occur. As indicated, community structure offers a way to identify nodes with duplicate influence spreads, eliminating the need for additional influence spread computation. Contribution is,

• We provide a unique approach that uses the network's community spread and seeding phase to maximize information dissemination.
• The experimental findings on four real-world datasets of varying sizes and applications show that the suggested approach performs better than many other IM algorithms.
• We provide a topic-aware, community-based influence maximization method that is superior in efficiency and spread.
• We carry out testing with real datasets. The testing findings show that the IMSC algorithm performs much better than other methods.

The structure of this paper follows as. The study problem is described in Section 2, along with our observations and a review of some pertinent literature. The IMSC method and related algorithms are described in Section 3. The trials on three real datasets are presented in Section 4. Section 5 concludes.

In this part, we outline the IMSC algorithm and discuss our methods for dealing with the problems it raises. The Monarch Butterfly Optimization Algorithm in IMSC enhances the process of candidate generation. Traditional methods have limitations in efficiently selecting potential influencers within communities. IMSC's optimization ensures a more thorough and practical network exploration, identifying candidates with a higher likelihood of influence. IMSC goes beyond conventional approaches in selecting seed nodes by leveraging the Monarch Butterfly Optimization Algorithm. This results in a more strategic identification of key influencers. Unlike some existing methods that might struggle to adapt to dynamic community changes, IMSC, powered by the Monarch Butterfly Optimization Algorithm, demonstrates high adaptability. It can efficiently adjust its influence maximization strategy as communities evolve, ensuring continued effectiveness. Three phases make up IMSC, as seen earlier in Figure 1: (i) recognition of community, (ii) generating the candidate, and (iii) selecting the seed. Each stage of IMSC is described in the section that follows.

3.1 Community detection in IMSC

A community in a social network is a portion of users who communicate with one another more frequently than users out of the community. We see some potential benefits of investigating community structures in the influence maximization problem, so our first aim is to create a powerful clustering technique for IMSC. An immediate challenge is that such an algorithm needs to achieve our long-term objective of lowering computing costs in the impact maximization problem. The ideas and values of the community may effectively grab human nature activity in social networks. Thus, without utilizing heuristics such as the number of regions, our community detection method seeks to identify the social networks' most organic communities. Be aware that even though an influence maximization task would want to choose four seeds, we shouldn't push a social network to split into four communities if it can accommodate three communities spontaneously. Therefore, this paper aims to build a clustering approach without defining the number of communities to uncover community structures.

Definition. (Influence maximization based on community) Finding a subset S* of k nodes such that the objective method specified in Eq. (1) is maximized is the goal of the influence maximization based on community issue given a network G(V; E) with a non-overlapping community structure C. i.e.,

$S^*=\arg _S \max f(S)$         (1)

Let $P_v\left(S, S^{\prime}, C\right)$ represent the likelihood that node $\mathrm{v}$ in community $\mathrm{C}$ will eventually become active. If so, the computation of $f\left(S, S^{\prime}, C\right)$ is as follows:

$f\left(S, S^{\prime}, C\right)=\sum_{v \in C} P_v\left(S, S^{\prime}, C\right)$              (2)

Although Eq. (2)'s form is unique, the computation of $P_v\left(S, S^{\prime}, C\right)$ is open. It is simple to observe that any $v \in S$, we have $P_v\left(S, S^{\prime}, C\right)=1$. For any $v \in S^{\prime}$, i.e., $v \in N(S)$, we have $P_v\left(S, S^{\prime}, C\right)=1-\Pi_{u \in N(v) \cap S\left(1-p_{u v}\right)}$. The calculation of the key value is $P_v\left(S, S^{\prime}, C\right)$ for the rest vertices. The method figures out the different groups or communities within a larger network. Imagine a social media platform - it's like identifying distinct groups of friends who frequently interact with each other.

3.2 Candidate generation

The candidate generation section seeks to identify a collection of candidate seeds depending on the number of groups and the connection of the nodes across groups in light of the found community framework. The search space for choosing seeds with the most significant influence diffuse is enormous due to the size of social networks in realistic settings. As a result, it's essential to lower the number of candidate seeds efficiently. One of the main problems IMSC is facing at this point is how to reduce the quantity of the candidate seeds.

According to our observations, the seeds chosen from a broad community may lead to more people accepting a thing or an invention than seeds chosen from a little group. As a result, choosing the center nodes of the social network's k-largest groups as the k-influential seeds is an intuitive strategy. However, this naive approach has a few potential issues: (1) The finding above suggests that in significant communities, we should choose more seeds, and (2) Some critical data about the community framework is disregarded. Be aware that the introduced MBO not only identifies hubs but also communities. While community centroids may seem apparent candidates for seed selection, the portal should also be considered because they can quickly extend their effects throughout numerous communities.

Definition 3 (Significant Communities)

MBO produces a collection of communities, indicated as $C=\left\{c_1, c_2, \ldots . ., c_p\right\}$. The following is a definition of the set of significant community $C_s$:

$C_s=\left\{c_j \in C \left\lvert\, n_j \geq \frac{\sum_{i=1}^p n_i}{k}\right.\right\}$               (3)

Once the communities are identified, the method looks for potential candidates to be influential or essential within these groups. Think of it as finding individuals who could significantly impact their respective friend circles or communities.

3.3 Seed selection

The community detection separates the social network into many communities, and each community's gain is then assessed using node coverage gain. We choose suitable nodes as seeds by using the outcomes of the node coverage gain evaluation and community detection. Seed nodes will be chosen from all the other communities, other than that, from only a few supposedly important groups, to minimize the rich-club effect and increase the impact dissemination. The following is a description of the three-step seed-choosing strategy:

Step 1: There is a largest-gain node inside each community. The node with the highest gain will be given preference when choosing a fresh seed if the node's gain values differ.

Step 2: The community node with no more seeds will be chosen as a new seed if more than one node in the entire network in Step 1 has the same maximum benefit.

Step 3: If many nodes in the network have the same maximum gain and every associated community has a minimum of one seed in Step 2, then the community node with the most extensive scale will be chosen as a new seed.

The most influential node, the seed, should be chosen for the initial step if a node has the highest gain value. We should prioritize the large-scale community; the second step has no seeds, and the third does not. It should be emphasized that just one seed node is chosen each time using this three-step method. The coverage gain of the available ones will be maintained for the subsequent chosen when a seed node has been chosen.

Now, from the pool of potential candidates, the method selects the best starting points, or "seed nodes." These seed nodes are like critical community influencers, serving as initial points for spreading information or influence.

3.4 Monarch Butterfly Optimization (MBO)

Swarm intelligence algorithms are believed to include the population-based algorithm known as the MBO. The behavior of certain insects, such as bees and butterflies, is what inspired these algorithms. As stated earlier, the MBO was developed in the modern era. The exquisite form of a butterfly species exclusive to North America and recognized by its orange and black colors served as the model for this ingenious program [24]. Twice a year, the monarch butterfly migrates, like many other butterflies. The first relocation originates in Canada and travels south to Mexico, while the second is upward migration from Mexico to Canada. Simulating these butterflies' migratory behavior solves several optimization problems. A few rules and fundamental concepts need to be adhered to get the optimal solution to the problem:

1. All butterflies are made of people who live in either Land 1 or Land 2 (the home following migration).

2. The migration operator produces Every butterfly's progeny, regardless of whether the parents are land 1 or inland 2.

3. A candidate function will remove one of the two since the population shouldn't fluctuate and should always remain constant.

4. The migration operator leaves the butterflies selected by the candidate function intact, passing them on to the next generation.

The butterflies begin their annual migration in early April when they depart from land l and travel to land 2. The return journey starts in September. An overall count of monarch butterflies in the two countries accurately represents the entire population or NP.

3.4.1 Migration facilitator

The following is a representation of the butterfly relocation process:

$X_{i . k}^{t+1}=X_{r 1 . k}^t$         (4)

The location of a butterfly, i, is indicated by $X_{r 1 . k}^t$, which represents the Kth components of the freshly generated location, and $X_{i . k}^{t+1}$, which represents the Kth components of Xi at the t + 1 generation. In this instance, the following equation was used to create the random integer r:

$R=$ rand $*$ peri                   (5)

where, peri denotes the period of the migration.

However, if r > p, the Kth variables determining the location of the next generation are found using the equation that follows:

$X_{i . k}^{t+1}=X_{r 2 . k}^t$                  (6)

where, $X_{r 2 . k}^t$ represents the Kth generation of X_r2's constituents for the butterfly r2. As a result, P represents the quantity of monarch butterflies present per acre.

3.4.2 Butterfly adjusting operator

To acquire the locations of the monarch butterflies, in addition to the migration operator, the following butterfly adjustment operator can also be used [25]. The butterfly adjusting operator method can be summed up in the following words. An erratically generated number can be improved if it is less than or equal to p for each of the monarch butterfly j constituent parts.

$X_{j . k}^{t+1}=X_{\text {best.k }}^t$           (7)

$X_{j . k}^{t+1}$ is the kth component of X_j at generation t + 1, which displays the monarch butterfly's j position.

$X_{j . k}^{t+1}=X_{r 3 . k}^t$            (8)

Xr3.kt denotes the randomly selected kth element from x r3 in Land 2. This instance has $r 3 \in\left\{1,2, \ldots, N P_2\right\}$. In this case, it can be updated further as indicated below if rand>BAR.

$X_{j \cdot k}^{t+1}=X_{j \cdot k}^{t+1}+\alpha \times\left(d x_k-0.5\right)$                  (9)

where, BAR is the butterfly's adjustment rate, a monarch butterfly's walk step or dx can be ascertained via Levy flying.

$d x=\operatorname{Levy}\left(x_i^t\right)$                  (10)

The weighting factor in Eq. (9), denoted by α, is derived from Eq. (11).

$\alpha=S_{\max } / t^2$                  (11)

While the small, representing a quick step in the search process, lowers the influence of dx on $x_{j . k}^{t+1}$ and encourages the exploitation phase, the bigger, representing a longer step in the search process, enhances the influence of dx on $x_{j . k}^{t+1}$. Consequently, it can characterize the individual who modifies the butterfly.

3.5 IMSC algorithm

The algorithm for the entire IMSC framework is based on the above captions for every phase. Monarch Butterfly Optimization can get data about the hubs and community frameworks—an overview of the IMSC algorithm.

All the parameters are set up before creating the initial population and assessing it using its fitness function. The whereabouts of each monarch butterfly are then gradually updated until specific standards are fulfilled. It should be noted that the quantity of monarch butterflies produced by the butterfly adjustment operator and migratory operator, respectively, is NP2 and NP1, to fix the population and community selections.

Algorithm 1. IMSC Algorithm.

Begin

Step 1: Initialization. Set the generation counter to 1 and randomly choose individuals from the population P of the community; Set the maximum generation MaxGen, the number of communities Land 1 and $N P_1$ in Land 1, the maximum step $S_{\text {max }}$, the community adjustment pace BAR, the migration ratio and the migration period peri.

Step 2: Community detection. Consider each community in light of its location.

Step 3: While the ideal answer has not been discoveredor t<MaxGendo

Sort each candidate based on how connected they are.

Separate the community of peoples into the Land 2 and Land 1 subpopulations;

For i=1to $N P_1$ (for all communities in Subpopulation 1) do

Generate new Subpopulation 1.

end for j

for j=1 to $N P_2$ (for all communities in Subpopulation 2) do

Generate new Subpopulations 2.

end for j

Then, select the seed node from the generated candidates.

Evaluate the populace in light of the most recent adjustments t=t+1.

Step 4: end while

Step 5: Produce the ideal answer.

End

MBOA can adapt to changing community dynamics. It's like having a strategy that can adjust and evolve as the social structure of a community changes over time, ensuring continued effectiveness. MBOA excels in efficiently exploring the network to find influential nodes. It's like having a team of efficient scouts that systematically search and identify the most impactful individuals within a community. Communities can have diverse structures, and MBOA can optimize for various types. Whether a community is tightly knit or loosely connected, MBOA can identify and maximize influence across different structures, making it versatile. MBOA's optimization process converges to optimal solutions relatively quickly. This means it efficiently identifies the most influential nodes without unnecessary delays, making it a time-effective approach.