Opinion Maximization in Social Networks: An Inverse Optimization Perspective

1 Introduction

In the current digital age, social networks have become crucial media for us to express and exchange opinions. To maximize the dissemination of opinions, many opinion publishers tend to select a number of opinion leaders (OLs). For instance, governments may choose certain institutions to release news or policies [Howard et al., 2000], while advertisers may select celebrities or bloggers to promote products [Casal´o et al., 2020]. Consequently, how to appropriately select OLs has emerged as an important research topic, commonly referred to as the opinion maximization (OM) problem [Gionis et al., 2013].

The initial OM problem was proposed by [Gionis et al., 2013]. They assumed that opinion dynamics on a social network G with n nodes and m edges follow the classical Friedkin-Johnsen (FJ) model [Friedkin and Johnsen, 1990], and studied how to select k (k ≪ n) OLs holding stubborn opinions of "1" (the maximum opinion value) to maximize the overall opinion (the sum of opinions of all nodes) in G. To address this problem, they demonstrated that the objective function of the OM problem satisfies monotonicity and modularity, and then employed the classical greedy algorithm (GA) [Nemhauser et al., 1978] with an approximation ratio of (1-1/e) along with several simple heuristic algorithms to solve it. Subsequently, numerous heuristic and metaheuristic algorithms have been further developed to tackle this problem, such as GA variants [Liu et al., 2018; Abebe et al., 2018], centrality-based methods [He et al., 2023; Hunter and Zaman, 2022], and metaheuristic algorithms [Liu et al., 2025b; Wan et al., 2025]. Additionally, extended OM problems under specific scenarios (e.g., behavioral constraints [Nayak et al., 2019; Hudson and Khamfroush, 2020], signed networks [Xu et al., 2021; He et al., 2021], and multi-party opinion publishers [Zhou and Zhang, 2023; He et al., 2025; Saha et al., 2025]) have also been recently studied.

∗Corresponding Author

This paper focuses on the original OM problem proposed by [Gionis et al., 2013]. Despite the progress achieved, existing methods typically struggle to achieve a satisfactory balance between theoretical performance and practical efficiency. Specifically, while GA and its variants can often provide theoretical guarantees, the multiple rounds of objective incremental evaluation they require often limit their scalability. Centrality-based heuristic algorithms, as they generally do not involve the evaluation of specific objectives, exhibit favorable scalability, but their practical performance is highly unstable due to the lack of theoretical support. Metaheuristic algorithms, by adopting various search strategies, often achieve better practical performance, but their complex algorithmic structures and numerous objective evaluations similarly constrain their scalability. Considering these facts, we aim to design an approach that integrates both theoretical performance and practical efficiency.

Upon careful analysis of the OM formulation, we find that its optimization challenges mainly stem from the complicated representation and high computational complexity of its objective function. Therefore, we first reformulate the OM problem into an opinion minimization (OMin) problem, whose objective function can be more succinctly expressed while still retaining monotonicity and modularity. Since the objective function of OMin is still computationally expensive, we then introduce a bounded estimation scheme (BES) that can estimate it with bounded error in nearly linear expected time, allowing iterative algorithms (e.g., GA, metaheuristic algorithms) to address OMin more efficiently. Next, to further enhance the efficiency for solving OMin, a decomposition-based decremental estimation algorithm (DDEA) is specifically designed. By structurally decomposing the objective increments within the GA framework, DDEA can achieve bounded estimation for each decomposed component, thereby significantly reducing computational complexity without substantially compromising the theoretical performance. We conduct extensive experiments on real-world social networks of varying scales. The results demonstrate the effectiveness of BES and the superiority of DDEA over several state-of-the-art OM approaches.

In summary, this paper makes the following contributions.

• We provide an inverse optimization perspective on the OM problem by reformulating it as the OMin problem. We show that the objective function of OMin could be expressed in a more succinct form while still preserving monotonicity and modularity.
• We propose BES to efficiently calculate the objective function of OMin, which could provide bounded error in ˜O(kn+m) expected time, allowing iterative algorithms to address OMin in a more efficient manner.
• We specifically design DDEA to address OMin. We show that DDEA could achieve a near (1 - 1/e) approximation ratio for OMin in ˜O(kmn) expected time.
• Extensive experiments on real-world social networks of varying scales demonstrate the effectiveness of BES and the superiority of DDEA.

2 RelatedWork

Influence maximization in social networks. The proposal of the OM problem was mainly inspired by the influence maximization (IM) problem. Unlike the OM problem, the IM problem typically employs diffusion models (e.g., independent cascade (IC) model, linear threshold (LT) model) to describe the influence diffusion process of seed nodes (similar to OLs in the OM problem), with the objective of maximizing the number of nodes activated by the seed nodes. The IM problem was first introduced by [Kempe et al., 2003]. After showing the modularity of the objective function under the IC and LT models, they also adopted GA as the optimization method. Given that the evaluation of the objective function involves expensive Monte Carlo simulations, several approximation methods have been proposed and widely used, such as expected diffusion value [Jiang et al., 2011] and twohop approximation [Lee and Chung, 2014]. Building upon these approximation methods, numerous heuristic and metaheuristic approaches have also been proposed to solve the IM problem, such as centrality-based measures [Guo et al., 2025; Ullah et al., 2024; Engsig et al., 2024], memetic algorithms [Gong et al., 2016], and swarm-intelligence algorithms [Wang et al., 2019]. Furthermore, IM problems under various conditional constraints (e.g., competitiveness [Hong et al., 2020], fairness [Rahmattalabi et al., 2021], robustness [Wang et al., 2023]) have been extensively studied in recent years.

Opinion optimization in social networks. In addition to the OM problem studied in this paper, numerous opinion optimization problems based on the FJ model have been proposed in recent years. [Matakos et al., 2017] defined a polarization index to measure the extent to which opinions on a social network deviate from the mean, and similarly investigated how to select k OLs to minimize this polarization index. Subsequently, [Musco et al., 2018] unified this polarization index with the disagreement index previously proposed by [Dandekar et al., 2013] into a polarization-disagreement index, and studied how to modify the Laplacian matrix of the social network to optimize it. Given the significant practical implications of the polarization-disagreement index, many other optimization approaches have been further introduced to optimize it, such as recommending new edges [Zhu et al., 2021; Wang and Kleinberg, 2023], adjusting edge weights [Cinus et al., 2023], shifting the overall internal opinions [Chen and R´acz, 2021; Tu et al., 2023], or increasing the overall opinion stubbornness [Shirzadi and Zehmakan, 2025]. Furthermore, some other opinion optimization problems have also garnered considerable attention, such as competitiveness maximization [Liu et al., 2023] and leader-follower disagreement minimization [Liu et al., 2026].

3 Preliminaries

Social networks. Following most OM studies, a social network is denoted by a connected, undirected, and weighted graph G = (V,E), where V = {v1, . . . , vn} is the node set and E = {e1, . . . , em} is the edge set. The adjacency matrix is A = (aij)n×n, where aij = aji = w ∈ (0, 1] if an edge of normalized weight w connects vi and vj, and aij = aji = 0 otherwise. The diagonal degree matrix is D = diag(d1, . . . , dn), with di = ∑nj=1 aij representing the degree of node vi. From these, the Laplacian matrix is defined as L = D - A, and the forest matrix as F = (I + L)-1 = (fij)n×n, where I is an identity matrix of appropriate size. The matrix F is doubly stochastic, satisfying fij ≥ 0, 1⊤F = 1⊤, and F1 = 1.

Opinion maximization. In the FJ model [Friedkin and Johnsen, 1990], each node vi holds an internal (innate) opinion si ∈ [0, 1] and an external (expressed) opinion zi ∈ [0, 1], where si remains unchanged and zi will be updated by:

where zi(t) is the state of zi at time step t. As t approaches infinity, zi(t) will reach its equilibrium state zi. (1) shows that zi is determined by si and the neighboring external opinions of vi. Thus, if there are some OLs holding stubborn opinions, the equilibrium external opinions of all nodes will be influenced to varying degrees. Thereby, based on the FJ model, the OM problem is defined as below.

Problem 1 (OM [Gionis et al., 2013]). Given a social network G = (V,E) and a positive integer k ≪ |V |, the aim of OM is to identify an OL set L ⊆ V (|L| = k, zi ≡ 1 for vi ∈ L) to maximize the overall opinion in G:

4 ProblemReformulation

Optimization challenges of opinion maximization. From Problem 1, it can be found that the optimization challenges of OM mainly stem from the following two aspects:

• The complex representation of the objective function. To compute (2), we must first obtain the zi value for each node. Let zl = [z1, . . . , zk] and zc = [z1, . . . , zn-k] be the equilibrium external opinion vectors of OLs and common nodes, respectively. Similarly, we can write A and D as the following block form:

Since OLs hold the stubborn opinion 1, we have

Then, combining (1) and (4), zc satisfies

which shows that

where Lc,c = Dc,c -Ac,c. Thus, (2) can be denoted as

which is very complicated, as it involves four different dynamic components: Lc,c, Ac,l, zl, and sc.

• The high computational complexity of the objective function. From (7), we can find that the calculation of F(L) involves inverting an (n - k) × (n - k) matrix, which generally requires O(n3 ) time complexity.

These two optimization challenges significantly limit the scalability of iterative algorithms (e.g., GA, metaheuristic algorithms). Therefore, we next address these challenges through problem reformulation.

Formulation of opinion minimization. As illustrated in Problem 1, the OM problem essentially models the stance of opinion publisher as the maximum value "1", and then selects k OLs to maximize the overall opinion (i.e., to maximize the propagation effect of opinion "1"). Therefore, we can naturally adopt an alternative yet equivalent modeling approach: model the stance of opinion publisher as the minimum value "0", and select k OLs to minimize the overall opinion (i.e., to maximize the propagation effect of opinion "0"). Under this modeling framework, zl = 0, which causes both 1⊤zl and Ac,lzl in (7) to equal 0, thereby significantly simplifying the computation of (7). To further unify the two remaining dynamic components (i.e., Lc,c and sc), we will next proceed to simplify the representation of the FJ model after selecting OLs with stubborn opinion "0".

Let z = [z1, . . . , zn] be the external opinion vector of all nodes. By introducing an auxiliary diagonal matrix Xk = diag(x1, . . . , xn), where xi = 0 if vi ∈ L and xi = 1 otherwise, the FJ model after selecting OLs with stubborn opinion "0" can be denoted by

Since I +D -XkA is still an M-matrix, The equilibrium state of z(t) in (8) is

where Y k = (I +D-XkA)-1 and sk =Xks. Thus, the overall opinion can be denoted as

It can be found that H(L) only has one dynamic component Xk, which is more succinct than F(L). Thereby, taking H(L) as the objective function, we reformulate Problem 1 as the following OMin problem.

Problem 2 (OMin). Given a social network G = (V, E) and a positive integer k ≪ |V |, the aim of OMin is to identify an OL set L ⊆ V (|L| = k, zi ≡ 0 for vi ∈ L) such that H(L) is minimized.

Properties of opinion minimization. [Gionis et al., 2013] demonstrated the monotonicity and modularity of F(L) using the random walk theory. Considering that H(L) possesses a more succinct expression, we will next mathematically demonstrate that H(L) still satisfies monotonicity and modularity.

Theorem 1 (Monotonicity of H(L)). H(L) is monotonically decreasing. In other words, for any two OL sets U ⊆ W ⊆ V , H(U) ≥ H(W) holds.

Proof. For brevity, we use u to denote |U|, and x ⪰ y to denote that x - y is non-negative. Then, by (9), we have

Subtracting the two equations in (11) yields

As F = (I + D - A)-1 ⪰ 0 is doubly stochastic, we have Y u = (I +D-XuA)-1 ⪰ 0. Then, as U ⊆ W, su ⪰ sw and Xu ⪰ Xw hold, showing that zu ⪰ zw. Therefore, we can derive 1⊤(zu - zw) ≥ 0, which demonstrates that Theorem 1 holds true.

Theorem 2 (Modularity of H(L)). H(L) is supermodular. In other words, for any two OL sets U ⊆ W ⊆ V , H(U) - H(U ∪ {v∗ }) ≥ H(W) - H(W ∪ {v∗ }) holds for any node v∗ ∈ V \W.

Proof. For brevity, we use U ∗ to denote U ∪ {v∗ }, and yu to denote (su - su∗ + (Xu -Xu∗)Azu∗). Similarly, by (12), we have

Since su-su∗ = sw-sw∗, Xu-Xu∗ =Xw-Xw∗, and zu∗ ⪰ zw∗, we have yu ⪰ yw. Thus, subtracting the two equations in (13) yields

As demonstrated in the proof of Theorem 1, Y u ⪰ 0, Y w ⪰ 0, and yu ⪰ 0 hold, showing that (zu -zu∗) ⪰ (zw -zw∗). Therefore, we can derive 1⊤(zu - zu∗) ≥ 1⊤(zw - zw∗), which demonstrates that Theorem 2 holds true.

Despite these desired properties of H(L), its computational complexity is still bounded by O(n3 ), making iterative optimization methods (e.g., GA, metaheuristic algorithms) difficult to be applied to optimize it in large-scale networks. Therefore, we propose BES to achieve bounded estimation of H(L), elaborated in the next section.

5 Bounded Estimation Scheme

It can be found that the general O(n3 ) computational complexity of H(L) mainly comes from inverting Y -1 k = I + D-XkA. To accelerate this critical step, we consider using the following solver for symmetric and diagonally dominant matrix (SDDM) [Spielman and Teng, 2014].

Lemma 1 (SDDM Solver [Spielman and Teng, 2014]). Given an n × n SDDM B with 2m non-zero off-diagonal entries and an accuracy parameter δ > 0, there is a solver u = Solve(B, v, δ) satisfying ||u - B†v||B ≤ δ||B†v||B, where ||v||B = √v⊤Bv and B† is the pseudo-inverse of B. The expected time of the solver is ˜O(m), where ˜O(·) suppresses the logarithmic factors.

Lemma 1 establishes that the product B-1v can, with the aid of an SDDM solver, be consistently approximated by u within controllable accuracy in nearly linear time. It is thus reasonable to contemplate estimating zk = Y ksk in an analogous manner. Nevertheless, despite the diagonal dominance of Y -1 k , its asymmetric nature prevents the direct application of this estimation approach. To address this obstacle, we subsequently construct an SDDM transformation for Y -1 k .

First, we analyze the properties of Y -1 1 , as it serves as the basic case for our purpose.

Proof. Let ai = Aei. Then, Y 1 can be computed by

According to the Sherman-Morrison formula [Sherman and Morrison, 1950], we have

Since (I +D -A)F = I, AF = (I +D)F - I holds. Thereby, we have

Similarly, we have

Hence, Lemma 2 holds true.

Lemma 3. There is an SDDM transformation for Y -1 1 , T -1 1 = Y -1 1 +aie⊤i , satisfying

• For any j ̸= i, T1ej = Y 1ej.
• T1s1 = Y 1s1.

Proof. According to the Sherman-Morrison formula and the results in Lemma 2, we have

Therefore, we have

which yields

Hence, Lemma 3 holds true.

Figure 1 uses an example social network to illustrate Lemmas 2 and 3. When L = {v4}, e⊤i Y 1ei = (1 + d4)-1 = 0.5 and the off-diagonal elements in the fourth row of Y 1 are all 0. Using the SDDM transformation, all elements except those in the fourth column will remain unchanged, which results in Y 1s1 = T 1s1. Based on the theoretical results in Lemmas 2 and 3, we can use induction to obtain the following SDDM transformation of Y -1 k .

Theorem 3 (SDDM Transformation of Y -1 k ). There is an SDDM transformation of Y -1 k , i.e., T -1 k = Y -1 k +A(I - Xk), satisfying Y ksk = T ksk.

Theorem 3 demonstrates that transforming Y -1 k into T -1 k allows zk to be equivalently computed as Tksk. Based on this result, zk can be estimated via the SDDM solver presented in Lemma 1 (i.e., ˜zk = Solve(T -1 k , sk, δ)). Next, we derive the bounds for this estimation.

Theorem 4 (Bounded Estimation of H(L)). For social network G = (V,E) with internal opinion vector s, OL set L, and error parameter ϵ ∈ (0, 1/2], if the accuracy parameter δ satisfies 0 < δ ≤ ϵ/n, then the following relation holds:

Proof. It can be found that

Since T -1 k = I +D-XkA+A(I -Xk), we can derive

Then, we have

Algorithm 1 BES

Input: social network: G = (V, E); OL set: L; internal opinion vector s; error parameter ϵ; Output: OL set: zk; 1: sk ← s, T -1 k ← I +L; 2: for i in L do 3: sk[i] ← 0; 4: for j = 1 to n do 5: if j = i then continue; 6: T -1 k [i, j] ← 0, T -1 k [j, i] ← 0; 7: end for 8: end for 9: ˜zk ← Solve(T -1 k , sk, ϵ/n); 10: ˜H(L) ← 1⊤ ˜zk; 11: return ˜H(L).

Combing (23), (24), and (25), we have

showing that Theorem 4 holds.

Based on Theorem 4, BES is presented in Algorithm 1. With the assistance of BES, the computational complexity of evaluating H(L) can be reduced from O(n3 ) to ˜O(kn +m). This reduction significantly enhances the efficiency of various iterative algorithms that rely on objective evaluation (e.g., GA, metaheuristics). We will further demonstrate this in the experimental section.

6 Decomposition-Based Decremental Estimation Algorithm

Due to the monotonicity and modularity of the objective function in the OM problem, [Gionis et al., 2013] employed GA with (1 - 1/e) approximation ratio for optimization. Given that OMin also satisfies monotonicity and modularity, GA remains the preferred choice for providing theoretical performance guarantees. The GA for the OMin problem is outlined in Algorithm 2. As can be seen, the kn objective evaluations required by GA result in a complexity as high as O(kn4 ). Although our proposed BES can effectively reduce the computational complexity of objective evaluation, the resulting complexity of ˜O(kn(kn+m)) still limits algorithmic scalability. Therefore, we introduce DDEA to further enhance optimization efficiency without significantly compromising theoretical performance guarantees.

The main idea of DDEA is to perform a decomposed estimation of the marginal decrease in line 3 of Algorithm 2. Let ∆Ht+1 i = H(Lt ) -H(Lt ∪ {vi}) be the marginal decrease of adding node vi ∈ V \Lt to Lt , it can be calculated by

The relation of T t and T t+1 can be expressed by

Algorithm 2 GA for OMin

Input: social network: G = (V, E); number of OLs: k; internal opinion vector s;

Output: solution set: Lk ;

• 1: L0 ← ∅;
• 2: for t from 0 to k -1 do
• 3: vi ← argmaxvi∈V \Lt(H(Lt ) -H(Lt ∪ {vi}));
• 4: Lt+1 ←Lt ∪ {vi};
• 5: end for
• 6: return Lk .

where Ct+1 is an auxiliary matrix. Based on the theoretical results in Lemmas 2 and 3, it can be found that

Combining (27), (28), (29), and st+1 = st - siei, ∆Ht+1 i can be decomposed into a polynomial that mainly consists of four components:

where c1 = 1⊤Ttei, c2 = a⊤i Ttst, c3 = a⊤i Ttei, and c4 = (1+a⊤i T tei)-1 . Since the structure of these four components are very similar to that of H(L) = 1⊤Y ksk, we can use the SDDM solver again to achieve bounded estimation for these four components, and then for ∆Ht+1 i .

Theorem 5 (Bounded Estimation of ∆Ht+1 i ). For social network G = (V,E) with internal opinion vector st, SDDM T -1 t , OL set Lt , node vi ∈ V \Lt , and error parameter ϵ ∈ (0, 1/2], we define quantities p = Solve(T -1 t , ei, δ), q = Solve(T -1 t , st, δ), ˜ c1 = 1⊤p, ˜ c2 = a⊤i q, ˜ c3 = a⊤i p, and ˜ c4 = (1+a⊤i p)-1 . If the accuracy parameter δ satisfies 0 < δ ≤ ϵ/(36n2 ), then the following relation holds:

The proof idea is similar to that of Theorem 4. With Theorem 5, the algorithmic framework of DDEA is presented in Algorithms 3 and 4. Since Algorithm 3 only involves ˜O(mn) expected time, the time complexity of DDEA is ˜O(kmn). Then, as the error of estimating ∆Ht+1 i is bounded by ϵ, we can follow the proof idea of the original GA to demonstrate the theoretical performance guarantee of DDEA.

Theorem 6 (Theoretical Performance Guarantee of DDEA). The output Lk of DDEA satisfies

where Lo is the optimal OL set for OMin.

7 Experiments

Datasets and baselines. The largest connected components of eight common real-world social networks of different scales are selected as our test datasets, and their basic information are shown in the first three columns of Table 1.

Algorithm 3 Index(·)

Input: social network: G = (V, E); OL set Lt ; internal opinion vector st; SDD matrix: T -1 t ; error parameter: ϵ;

Output: index of the node offering maximal approximate marginal decrease onH(Lt ): i;

• 1: ˜∆← 0, δ ← ϵ/(36n2 );
• 2: for i from 1 to n do
• 3: if vi ∈ Lt then continue;
• 4: p← Solve(T -1 t , ei, δ), q ← Solve(T -1 t , st, δ);
• 5: ˜ c1 ← 1⊤p, ˜ c2 ←a⊤i q, ˜ c3 ←a⊤i p, ˜ c4 ← (1 + a⊤i p)-1 ;
• 6: ˜∆i ← si˜ c1(1 - ˜ c3˜ c4) + ˜ c1˜ c2˜ c4;
• 7: end for
• 8: i ← argmaxi ˜∆i;
• 9: return i.

Algorithm 4 DDEA

Input: social network: G = (V, E); number of OLs: k; internal opinion vector s; error parameter ϵ;

Output: OL set: Lk ;

• 1: L0 ← ∅, s0 ← s, T -1 0 ← I +L;
• 2: for t from 0 to k -1 do
• 3: Get the index of the node offering maximal approximate marginal decrease on H(Lt ):

i ← Index(G, Lt , st, T -1

• 4: Lt+1 ←Lt ∪ {vi}, st+1 ← st - siei, T -1 t+1 ← T -1 t +eia⊤i +aie⊤i ;
• 5: end for
• 6: return Lk .

t , ϵ);

All these datasets are available in public network libraries including KONECT [Kunegis, 2013] and Network Repository [Rossi and Ahmed, 2015].

To assess BES and DDEA, we select GA, a state-of-the-art metaheuristic OM method MACOM [Liu et al., 2025b], and three state-of-the-art heuristic methods for identifying influential nodes (Improved Local and Global Centrality (ILGC) [Guo et al., 2025], Electric Potential Centrality (EPC) [Ullah et al., 2024], and DomiRank Centrality (DRC) [Engsig et al., 2024]) as our baselines. The parameters of these baselines strictly follow their original publication specifications.

Basic settings. Followingmany related studies, the internal opinions of social members are randomly sampled from [0,1]. To ensure the theoretical performances of DDEA, we set ϵ to 1/200k (i.e., 2kϵ = 10-2 ). Since the test datasets have different scales, we use ¯ F = F(L)/n and ¯H = H(L)/n to evaluate algorithmic effectiveness, and the average runtime across 10 independent runs are used to evaluate algorithmic efficiency [Liu et al., 2022; Liu et al., 2025a].

All experiments are conducted on a PC with a 3.0 GHz Intel Core i7 processor, and all algorithms are implemented by the Julia language 1 . Besides, the source code of the SDDM solver is publicly available 2 .

1 https://julialang.org/

2 https://github.com/danspielman/Laplacians.jl

Effectiveness of BES. We first demonstrate the effectiveness of BES. As shown in Table 1, when evaluating a random OL set with k = 100, BES significantly reduces the runtime while exhibiting excellent scalability. For example, on G8, which contains more than one million nodes and edges, its runtime does not exceed three seconds. In contrast, the runtime of EC on G5 with about 42 thousands nodes and 126 thousands edges has already exceeded half an hour. To further illustrate that BES can improve the efficiency of iterative algorithms, we next conduct experimental analyses using GA and MACOM as examples. As shown in Table 2, with the assistance of BES, the performance of GA and MACOM is not significantly affected, yet their runtime is notably reduced. Moreover, compared with GA, BES brings a more pronounced efficiency improvement to MACOM, which is mainly because MACOM requires fewer evaluations of the objective function. In summary, the experimental results align closely with our theoretical analysis, strongly demonstrating the superiority of BES.

Effectiveness of DDEA. We next demonstrate the efficiency of DDEA. As shown in Figure 2 and Figure 3, on G3, DDEA and GA+BES achieve identical optimal performance across all settings of k, while the runtime of DDEA is two orders of magnitude lower than that of GA+BES. This is mainly because DDEA and GA+BES share similar greedy principles and error estimation strategies, yet the O(kmn) time complexity of DDEA significantly reduces its runtime. When applied to the larger-scale G4, DDEA not only maintains optimal performance but also achieves the shortest runtime. This is largely because MACOM, ILGC, and EPC all involve the computation of graph-related distance matrices, while DRC requires calculating the smallest eigenvalue of the adjacency matrix, leading to their higher time complexities. In summary, the experimental results strongly confirm that DDEA possesses not only theoretical superiority but also outstanding practical efficiency.

8 Conclusion

This paper has provided an inverse optimization perspective on the OM problem by reformulating it as the OMin problem. By showing that the objective function of OMin could be expressed in a succinct form while still preserving monotonicity and modularity, we have first proposed BES to achieve efficient calculation for its objective function, which could provide bounded error in ˜O(kn +m) expected time. Then, we have specifically designed DDEA with a near (1 - 1/e) approximation ratio for OMin in ˜O(kmn) expected time. Extensive experimental results have demonstrated that BES could significantly enhance the efficiency of iterative algorithms to address OMin, while DDEA has not only theoretical advantage but also practical efficiency superiority. We believe this work could inspire more efforts on opinion optimization in social networks.

Acknowledgments

This work was supported in part by the Research Grants Council of the Hong Kong SAR, China, under Grant CityU11215622, and in part by the Natural Science Foundation of China under Grant 62276223.