# Non-Hermitian Physics-Inspired Voltage-Controlled Oscillators with Resistive
Tuning

Weidong Caoa, Hua Wangb, and Xuan Zhanga aWashington University in St. Louis,
Saint Louis, MO, USA; bETH Zürich, Zürich, Switzerland

###### Abstract

This paper presents a non-Hermitian physics-inspired voltage-controlled
oscillator (VCO) topology, which is termed parity-time-symmetric topology. The
VCO consists of two coupled inductor-capacitor (LC) cores with a balanced gain
and loss profile. Due to the interplay between the gain/loss and their
coupling, an extra degree of freedom is enabled via resistive tuning, which
can enhance the frequency tuning range (FTR) beyond the bounds of conventional
capacitive or inductive tuning. A silicon prototype is implemented in a
standard $130$ nm bulk CMOS process with a core area of $0.15\text{mm}^{2}$.
Experimental results show that it achieves a $3.1\times$ FTR improvement and
$30\%$ phase noise reduction of the baseline VCO with the same amount of
capacitive tuning ability.

###### Index Terms:

Non-Hermitian physics, voltage-controlled oscillator, PT-symmetry, resistive
tuning, frequency tuning range.

##  I Introduction

Inductor-capacitor (LC) voltage-controlled oscillators (VCOs) are the key
building blocks in many communication systems [1, 2, 3]. Such local
oscillators need to cover a wide frequency tuning range (FTR) and maintain
good phase noise (PN) performance. Existing methods mainly rely on aggressive
inductive tuning (e.g., negative inductance/switched-inductors) [4, 5] or
capacitive tuning (e.g., varactors/switched-capacitors) [6] to reach a wide
FTR. However, they often suffer from degenerated PN performance due to the
excessive noise sources introduced by the tuning mechanisms. Some techniques
have been proposed to tackle the stringent design trade-off between FTR and
PN. For example, multi-core and multi-mode VCOs implemented with two or more
coupled LC cores can reduce PN and extend the FTR, but bear the cost of
excessive design complexity in VCO cores [7, 8]. On the other hand, leveraging
multiple separated LC VCOs can extend the FTR, but induces large area overhead
and high multiplexing complexity [9]. Therefore, developing more effective
approaches to improving the FTR without hurting the PN performance is highly
desirable.

Toward the goal, a gain-loss coupled dual-core VCO topology based on non-
Hermitian physics is shown in this paper, which is originally proposed in our
prior work [10]. From the perspective of non-Hermitian physics, the
eigenfrequency of a physical system built upon two coupled units with a
balanced gain and loss distribution can evolve in a wide range by tuning the
gain/loss contrast [11, 10]. Inspired by this physical principle, we build
this gain-loss coupled dual-core VCO. It not only inherits the superior PN
performance from the coupled structure of multi-core VCOs but also achieves an
enlarged FTR beyond the bounds of conventional capacitive/inductive tuning
with extra resistive tuning. The proposed topology can be combined with
existing optimization approaches to further advance VCO performance. Section
II introduces the theoretical model of non-Hermitian quantum physical systems
composed of two coupled units with a balanced gain and loss profile. Circuit
design and analysis are presented in Section III. Comprehensive measurement
results are shown in Section IV before the conclusion in Section V.

##  II Background

Figure 1: (a) Illustration of an open non-Hermitian quantum system that can be
modeled as a gain (G) or a loss (L) unit. (b) Illustration of a non-Hermitian
quantum system with a coupled gain and loss profile. $\omega_{1,2}$ is the
resonant frequency of the unit. $-g$ and $l$ represents gain and loss amount
respectively.

###  II-A Non-Hermitian Quantum Mechanics

In quantum mechanics, an open system can be generally modeled as a gain (or
loss) unit with a resonant frequency as shown in Fig. 1(a). Such systems are
described by non-Hermitian Hamiltonians which preserve complex eigenvalues,
i.e., $\omega_{1}-ig$ or $\omega_{2}+il$. However, non-Hermitian quantum
systems built upon two coupled units, one with gain and the other one with
loss as shown in Fig. 1(b), possess purely real eigenfrequencies in certain
regimes as derived below. Note that such systems are also specifically termed
parity-time-symmetric (PT-symmetric) systems [10]. The system dynamics in Fig.
1(b) is expressed as

$\dfrac{d}{dt}\left[\begin{array}[]{c}a_{\text{G}}\\\ a_{\text{L}}\\\
\end{array}\right]=\left[\begin{array}[]{cc}i{\omega_{1}}+g&\kappa\\\
\kappa&i{\omega_{2}}-l\\\
\end{array}\right]\cdot\left[\begin{array}[]{c}a_{\text{G}}\\\ a_{\text{L}}\\\
\end{array}\right],$ (1)

where the subscript G (or L) refers to the gain (or loss) unit and
$a_{\text{G,L}}$ is the field amplitude defined such that
$|a_{\text{G,L}}|^{2}$ represents the energy stored in each unit. $g$ (or $l$)
presents the gain (or loss) of the unit. $\kappa$ indicates the coupling
strength between the two units and $\omega_{1,2}$ represents the resonant
frequency of each unit. To find the eigenfrequencies, we let
$a_{\text{G,L}}\propto{\exp^{i\omega t}}$ and obtain the characteristic
equation as

$\big{(}i(\omega_{1}-\omega)+g\big{)}\cdot\big{(}i(\omega_{2}-\omega)-l\big{)}+{\kappa}^{2}=0.$
(2)

For a balanced system where the gain is equal to the loss, i.e., $g=l$, the
solutions are then given by the following expression:

$\omega=\omega_{0}\pm\sqrt{{\kappa}^{2}-g^{2}},~{}\omega_{0}=(\omega_{1}+\omega_{2})/2.$
(3)

Eq. (3) shows that when the coupling strength $\kappa$ is stronger than a
threshold determined by the gain-loss contrast $g$, i.e., $\kappa>g=l$, the
system has a pair of real eigenfrequencies. Particularly, these
eigenfrequencies could evolve with gain-loss contrast in a wide range as long
as $g=l\in(0,\kappa)$. This simple analysis suggests that the interplay
between gain/loss and their coupling provides a new degree of tuning freedom,
i.e., gain/loss tuning freedom, to modulate the behaviors of a system. In the
next section, we discuss how this physical principle (i.e., PT-symmetric
topology) can be applied to design VCOs.

Figure 2: Structure comparisons between (a) conventional single-core VCOs, (b)
multi-core VCOs, and (c) proposed VCOs. (d) Numerical comparisons of frequency
tuning between the three types of VCOs.

###  II-B Non-Hermitian Quantum Mechanics for VCO Design

Before introducing the proposed VCO topology, Fig. 2 first re-examines
conventional single-core and multi-core VCOs. A single-core VCO can be
simplified into an active LC resonator shown in Fig. 2(a). It consists of a
gain ($-R$) and an LC core with an intrinsic loss ($R_{0}$). A multi-core VCO
(e.g., dual-core) is built upon two coupled single-core VCOs with a fixed
coupling strength $\kappa$, each of which is simplified into an active LC
resonator. For both VCOs, at the start-up phase, the gain is set to be
slightly higher than the inherent loss to produce an oscillation with
exponentially-growing amplitude. As the amplitude grows, the gain saturates
and equates the loss in the large-signal domain due to nonlinearity. The
oscillation then becomes stable, and the frequency (i.e.,
$\omega_{\text{S}}/\omega_{\text{M}}$ in Fig. 2(a)/(b)) can only be adjusted
via $\omega_{0}$ by tuning the core’s capacitance or inductance. In
particular, the multi-core VCO has two frequency modes as shown by
$\omega_{\text{M}}$ in Fig. 2(b).

This re-examination shows that in the conventional VCOs, the gain-loss
distribution plays only a trivial role in the transient behavior of
oscillators, i.e., the gain is used to compensate for the undesired loss to
establish the start-up condition for the exponential growth of oscillation
amplitude. Fortunately, based on the non-Hermitian quantum mechanics
introduced before, the loss is useful if the gain-loss distribution in a
system is properly manipulated. Inspired by this physical principle, our
method explores the interplay between the gain/loss distribution and their
coupling to enhance the frequency tuning bandwidth of VCOs. Fig. 2(c) exhibits
the simplified topology of the proposed VCO. It is built upon two coupled LC
cores, one active with a negative resistance $-g$ and the other one
dissipative with an equal amount of loss $l$, and the two cores have the same
capacitance and inductance. The proposed VCO exhibits two frequency modes as
shown by $\omega_{\text{P}}$ in Fig. 2(c) and an extra resistive tuning
freedom (i.e., $g$) that is orthogonal with the typical capacitive/inductive
tuning freedoms of $\omega_{0}$. Fig. 2(d) numerically compares the frequency
tuning of these three types of VCOs. Both the single-core VCO and multi-core
VCO have only individual frequency points (i.e., blue circle and red
asterisks), which are independent of $g$. However, the proposed VCO has a very
wide FTR enabled by $g$. The comparison shows that the proposed VCO with the
resistive tuning freedom can achieve a wider FTR than conventional VCOs given
the same capacitive/inductive tuning ability preserved by $\omega_{0}$.

##  III Gain-Loss Coupled Dual-Core VCO Topology

Figure 3: The circuit schematic of the proposed VCO.

###  III-A Circuit Design

Fig. 3 shows the proposed VCO circuit. The gain side has a tunable gain rate
generated by cross-coupled differential pairs (XDPs) and an inherent loss rate
$R_{\text{G0}}$, leading to the total gain of
$-R_{\text{G}}=(-1/G_{m})\verb||||R_{\text{G0}}$;
$G_{m}={(g_{\text{mn}}+g_{\text{mp}})/{2}}$, where $g_{\text{mn}}$ and
$g_{\text{mp}}$ are the small signal transconductance of NMOS and PMOS XDP.
The loss side has an intrinsic loss rate $R_{\text{L0}}$ and a variable loss
rate $R_{\text{L1}}$, giving the total loss of
$R_{\text{L}}=R_{\text{L0}}\verb||||R_{\text{L1}}$. To make loss adjustable, a
variable resistor based on stacked transistors is parallelly connected to the
loss side. The subset in Fig. 3 shows the schematic of the variable resistor
$R_{\text{L1}}$. All the gates of MOSFETs are connected together. By tuning
the gate voltage $V_{\text{BIASL}}$, the resistance can be continuously
adjusted in a wide range. The capacitor $C_{\text{G}}$ ($C_{\text{L}}$) in
each LC core is composed of a parasitic capacitance $C_{\text{G0}}$
($C_{\text{L0}}$), a fixed Metal-Insulator-Metal (MIM) capacitor
$C_{\text{G1}}$ ($C_{\text{L1}}$) with high-quality factor (high-Q) and an
adjustable varactor $C_{\text{G2}}$ ($C_{\text{L2}}$). The varactor takes up a
small proportion of the total capacitance and is mainly used to compensate for
the fabrication mismatch of the fixed MIM capacitors on each side. The
coupling capacitance ($C_{\text{C}}$) is realized by two equal MIM capacitors
($C_{\text{C1}}$ and $C_{\text{C2}}$) which are serially connected through an
on-chip switch (SW). The inductance ($L_{\text{G}}/L_{\text{L}}$) in both
cores comes from the high-Q symmetrical parallel inductor (symindp) of the
technology. A center tap connection is provided such that both cores share the
same common mode voltage by connecting the center taps of the inductors. The
balanced condition is satisfied by setting $R_{\text{G}}\approx
R_{\text{L}}=R$, $L_{\text{G}}\approx L_{\text{L}}=L$, and
$C_{\text{G}}\approx C_{\text{L}}=C$.

###  III-B Phase Noise Analysis

We perform a qualitative analysis on the phase noise (PN) of the proposed VCO.
It is well-established in the classic VCO theory that a multi-core VCO built
upon a coupled structure can lead to PN reduction as compared to a single-core
VCO. By taking a two-core VCO as an example, the improved PN can be
intuitively understood as that the equivalent current noise of each LC core
experiences twice the capacitance, and therefore its PN contribution is
reduced by $6$ dB. Two noise contributions from the two cores are uncorrelated
and can be summed up, ideally leading to a $3$ dB reduction of the total PN.
Generally, for an $N$-core VCO built upon a coupled structure, its PN is lower
than a single-core VCO by $10\log_{10}N$ dB. Thanks to the coupled structure,
the proposed VCO topology also inherits the PN advantage of conventional
multi-core VCOs. On the other hand, the gain-loss tuning physically realized
by active devices, although it does not generate more inherent losses, does
contribute additional noise to the system. However, this is not a big issue as
the unique gain-loss tuning also increases the carrier amplitude which
suppresses the effect of noise. It can be shown as follows. For the proposed
VCO, the gain not only compensates the inherent loss in the active core but
also offsets the tunable loss in the coupled lossy core. Assuming the ratio
between the tunable gain $-G_{m}$ generated by XDPs and the inherent loss
$R_{0}$ is $\beta$ ($\beta>1$), the PN of the active core in our proposed VCO
can be obtained based on the well-known PN model of single-core VCOs as below:

$\begin{split}&\ \mathcal{L}_{\text{P}}(\triangle\omega)=\\\ &\
10\log_{10}\Bigg{(}(1+\beta
m)\cdot\frac{4kTR_{0}}{({\beta}^{2}V_{\text{osc}})^{2}}\cdot\Big{(}\frac{\omega}{2Q_{S}\triangle\omega}\Big{)}^{2}\Bigg{)}\\\
&\
=\underset{\mathcal{L}_{\text{S}}(\triangle\omega)}{\underbrace{10\log_{10}\Bigg{(}(1+m)\cdot\frac{4kTR_{0}}{(V_{\text{osc}})^{2}}\cdot\Big{(}\frac{\omega}{2Q_{S}\triangle\omega}\Big{)}^{2}\Bigg{)}}}\\\
&\
-\underset{>0}{\underbrace{10\log_{10}\Big{(}\dfrac{{\beta}^{4}(1+m)}{(1+\beta
m)}\Big{)}}}<\mathcal{L}_{\text{S}}(\triangle\omega),\end{split}$ (4)

where $k$ is the Boltzmann constant; $T$ is the absolute temperature; $R_{0}$
is the inherent resonator loss; $m$ ($m>1$) is a constant noise factor of
active elements; $V_{\text{osc}}$ is the amplitude of the carrier; $Q_{S}$ is
the quality factor of the LC core; $\mathcal{L}_{\text{S}}(\triangle\omega)$
is PN of a conventional single-core VCO. Compared to the PN of conventional
single-core VCOs, both the noise factor $m$ of active devices and the
amplitude $V_{\text{osc}}$ of carrier increase in the PN formula of the active
core of the proposed VCO. But the carrier amplitude increases to
$\beta^{2}\times$ of the conventional one because the current flowing into the
core is quadratically proportional to the gain when XDPs operate in the
saturation region. Therefore, the proposed VCO topology shows better PN
performance than conventional single-core VCOs.

##  IV Experimental Evaluations

To experimentally verify the advantages of the proposed VCO, a prototype
design is implemented in a standard $130$ nm bulk CMOS process with a core
area of $0.15$ $\text{mm}^{2}$ as shown in Fig. 4. The two LC cores can be
coupled (decoupled) by turning on (off) the switch SW. A single-core VCO,
i.e., the active LC core in our design, is used as the baseline to directly
compare with ours on the same monolithic chip. The baseline only has
capacitive tuning freedom. Additionally, since it inherently comes from our
proposed VCO with the same non-ideal parasitic effects, thereby serving as a
fair candidate for comparison to show the enhanced performance solely due to
the contribution of the extra resistive tuning freedom.

Figure 4: Die micrograph of the proposed VCO. Figure 5: Frequency tuning of
the two VCOs. (a), The baseline VCO. (b), The proposed VCO. Theory:
theoretical predictions; Exp: experimental results. TABLE I: Comparisons
between the proposed VCO and state-of-the-art VCOs.

Reference |  JSSC ’13 [6] |  TCAS-I ’12 [4] |  ISSCC ’19 [12] |  ISSCC ’19 [7] |  JSSC ’17 [8] | This work
---|---|---|---|---|---|---
VCO types | Single-core | Single-core | Single-core | Dual-core | Quad-core | Dual-core
Optimization technique |  | Suppression of
---
flicker noise
| Switched-coupled inductor,
---
aggressive capacitive tuning
| Narrowband
---
resonance at $2f_{\text{osc}}$
| Aggressive
---
capacitive tuning
Multi-core |  | No
---
optimization
Technology |  $65$ nm CMOS |  $90$ nm CMOS |  $22$ nm FDSOI |  $65$ nm CMOS |  $55$ nm BiCMOS | $130$ nm CMOS
Power supply (V) | $1.2$ | $1.2$ | $0.15$ | $0.65$ | $1.2$ | $1.2$
Power (mW) | $0.72$ | $1.06$ | $0.91\sim 1.22$ | $17.5\sim 21.6$ | $50$ | $2\sim 4.31$
Area ($\text{mm}^{2})$ | $0.0806$ | $0.5$ | $0.272$ | $0.08$ | $0.6$ | $0.15$
Tuning bandwidth (GHz) | $3.0\sim 3.6$ | $1.13\sim 1.9$ | $4.15\sim 4.97$ | $25\sim 38$ | $17.4\sim 20.3$ | $2.63\sim 3.20$
FTR (%) | $18.2\%$ | $50.8\%$ | $18\%$ | $41.2\%$ | $15.3\%$ | $20.2\%$
Resistive tuning | ✗ | ✗ | ✗ | ✗ | ✗ | ✓
PN (dBc/Hz) (Average) |  $-112$@$1$MHz |  $-117.2$@$1$MHz |  $-141$@$10$MHz |  $-116$@$3$MHz |  $-106.5$@$1$MHz | $-$$120.3$@$1$MHz
FoM (dB)a (Average) |  $183$@$1$MHz |  $177.3$@$1$MHz |  $193$@$10$MHz |  $183$@$3$MHz |  $187.5$@$1$MHz | $184$@$1$MHz
$\text{FoM}_{\text{T}}$ (dB)b (Average) |  $188.2$@$1$MHz |  $191$@$1$MHz |  $198$@$10$MHz |  $195$@$3$MHz |  $191$@$1$MHz | $190.1$@$1$MHz

  * a

$\text{FoM}=|{\text{PN}}|+20{\log}_{10}(f_{\text{osc}}/\triangle
f)-10\log_{10}(P_{\text{DC}}/1\text{mW})$.

  * b

$\text{FoM}_{\text{T}}=\text{FoM}+20\log_{10}({\text{FTR}}/10\%)$.

Fig. 5 shows the frequency tuning curves of the two VCOs. The baseline yielded
a $0.20$ GHz ($3.03\sim 3.23$ GHz, $6.4\%$ FTR) bandwidth tuning as
demonstrated in Fig. 5(a) by adjusting the control voltage of varactors. Such
a tuning range corresponds to a capacitive tuning ability of $[1.30,1.50]$ pF.
We then set the core capacitance to be $1.35$ pF and $1.45$ pF respectively.
Fig. 5(b) exhibits the tuning curves corresponding to each capacitance value.
At $C=1.35$ pF ($C=1.45$ pF), the proposed VCO achieves a tuning bandwidth of
$[2.77,3.20]$ GHz ($[2.63,2.98]$ GHz) with the extra resistive tuning freedom.
The results show that even with a slightly reduced amount of the capacitive
tuning ability, the proposed VCO can realize a wider bandwidth tuning of
$0.57$ GHz ($2.63\sim 3.20$ GHz, $20.2\%$ FTR) by including the resistive
tuning freedom, enabling a $3.1\times$ FTR of the baseline. Note that this
prototype only a small range of capacitive tuning ability (i.e., $[1.30,1.50]$
pF) is included in this prototype, thereby achieving an FTR of $20\%$. By
slightly increasing the capacitive tuning ability, the proposed VCO can
readily realize a wider FTR.

Figure 6: PN comparisons of two VCOs across different oscillation frequencies.

We then show the PN of both VCOs. Particularly, we measure the PN at three
frequency points for each VCO in its tuning bandwidth. For the proposed VCO,
we choose such frequencies to be $2.84$ GHz (low), $3.04$ GHz (medium), and
$3.22$ GHz (high). While for the baseline VCO, we choose them to be $3.05$ GHz
(low), $3.12$ GHz (medium), and $3.22$ GHz (high). Fig. 6 shows the measured
PN at $1$ MHz offset frequency for the two VCOs. We observed that the PN of
the proposed VCO is generally $1.5$ dB better than the baseline across the
different oscillation frequencies. Due to the parasitics of the switch
connecting the two LC cores, the PN improvement is not as much as the ideal
case discussed in Section III-B. However, these observations generally match
well with the previous qualitative characterizations. Our results show that
manipulating the gain-loss profile and their coupling provides a new method to
extend the frequency tuning dimension beyond conventional capacitive/inductive
tuning without compromising the PN performance for VCO design.

Additionally, we compare the proposed VCO with other conventional VCOs, i.e.,
single-core VCOs, two-core VCOs, and quad-core VCOs that employ different
tuning manners or coupling structures, as summarized in Table I. These
conventional VCOs exploit different optimization techniques, such as
aggressive capacitive tuning to reach wide FTR (TCAS-I ’12 [4]), narrow band
resonance at $2f_{\text{osc}}$ to boost PN performance (ISSCC ’19 [12])), and
multi cores to enhance PN performance (JSSC ’17 [8]). However, our proposed
VCO only includes a resistive tuning into design without any other
optimization techniques. The comparison still shows its comparable FTR, PN,
and figure-of-merit (FoM) with these prior arts. In summary, the resistive
tuning of our proposed VCO topology is orthogonal with other
capacitive/inductive tuning dimensions to enhance the performance of VCOs with
diverse conventional topologies and optimization techniques.

##  V Conclusion

A non-Hermitian physics-inspired topology of VCO is shown in this paper. The
new topology enhances the FTR of existing VCOs with extra resistive tuning
freedom. A prototype is implemented in a standard $130$ nm CMOS process to
demonstrate its advantages. The comparisons show that the resistive tuning of
our proposed VCO topology is orthogonal with other capacitive/inductive tuning
dimensions to enhance the performance of VCOs with diverse conventional
topologies and optimization techniques. Future explorations can be performed
by cascading multiple such VCOs in a one-dimensional chain similar to the one
shown in prior work [13], which may also achieve topological oscillators.

## References

  * [1] F. Lv, X. Zheng, F. Zhao, J. Wang, S. Yue, Z. Wang, W. Cao, Y. He, C. Zhang, H. Jiang, and Z. Wang, “A power scalable 2-10FIX ME!!!!Gb/s PI-based clock data recovery for multilane applications,” _Microelectronics Journal_ , vol. 82, pp. 36–45, 2018.
  * [2] N. Zhou, L. Wu, Z. Wang, X. Zheng, W. Cao, C. Zhang, F. Li, and Z. Wang, “A 28-Gb/s transmitter with 3-tap FFE and T-coil enhanced terminal in 65-nm CMOS technology,” in _2016 14th IEEE International New Circuits and Systems Conference (NEWCAS)_ , 2016, pp. 1–4.
  * [3] W. Cao, Z. Wang, D. Li, X. Zheng, K. Huang, S. Yuan, F. Li, and Z. Wang, “A 40Gb/s 27mW 3-tap closed-loop decision feedback equalizer in 65nm CMOS,” in _2015 IEEE 13th International New Circuits and Systems Conference (NEWCAS)_. IEEE, 2015, pp. 1–4.
  * [4] A. I. et al, “A 1-mW 1.13–1.9 GHz CMOS LC VCO Using Shunt-Connected Switched-Coupled Inductors,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 59, no. 6, pp. 1145–1155, 2012.
  * [5] Tanabe, Akira et al, “A 5–20GHz tunable LC-VCO using variable bridge inductor,” in _2010 Symposium on VLSI Circuits_ , 2010, pp. 47–48.
  * [6] F. Pepe, A. Bonfanti, S. Levantino, C. Samori, and A. L. Lacaita, “Suppression of Flicker Noise Up-Conversion in a 65-nm CMOS VCO in the 3.0-to-3.6 GHz Band,” _IEEE Journal of Solid-State Circuits_ , vol. 48, no. 10, pp. 2375–2389, 2013.
  * [7] A. Bhat and N. Krishnapura, “26.3 A 25-to-38GHz, 195dB $\text{FoM}_{\text{T}}$ LC QVCO in 65nm LP CMOS Using a 4-Port Dual-Mode Resonator for 5G Radios,” in _2019 IEEE International Solid- State Circuits Conference - (ISSCC)_ , 2019, pp. 412–414.
  * [8] L. Iotti, A. Mazzanti, and F. Svelto, “Insights Into Phase-Noise Scaling in Switch-Coupled Multi-Core LC VCOs for E-Band Adaptive Modulation Links,” _IEEE Journal of Solid-State Circuits_ , vol. 52, no. 7, pp. 1703–1718, 2017\.
  * [9] W. Deng, H. Jia, R. Wu, S. Sun, C. Li, Z. Wang, and B. Chi, “An 8.2-to-21.5 ghz dual-core quad-mode orthogonal-coupled vco with concurrently dual-output using parallel 8-shaped resonator,” in _2021 IEEE Custom Integrated Circuits Conference (CICC)_ , 2021, pp. 1–2.
  * [10] W. Cao, C. Wang, W. Chen, S. Hu, H. Wang, L. Yang, and X. Zhang, “Fully integrated parity–time-symmetric electronics,” _Nature nanotechnology_ , vol. 17, no. 3, pp. 262–268, 2022.
  * [11] Ş. K. Özdemir, S. Rotter, F. Nori, and L. Yang, “Parity–time symmetry and exceptional points in photonics,” _Nature Materials_ , vol. 18, no. 8, pp. 783–798, Aug 2019.
  * [12] O. El-Aassar and G. M. Rebeiz, “26.5 A 0.1-to-0.2V Transformer-Based Switched-Mode Folded DCO in 22nm FDSOI With Active Step-Down Impedance Achieving 197dBc/Hz Peak FoM and 40MHz/V Frequency Pushing,” in _2019 IEEE International Solid- State Circuits Conference - (ISSCC)_ , 2019, pp. 416–418.
  * [13] Y. Liu, W. Cao, W. Chen, H. Wang, L. Yang, and X. Zhang, “Fully integrated topological electronics,” _Scientific reports_ , vol. 12, no. 1, p. 13410, 2022.


Targeted influence maximization

R.Zhang et al.

mode = title]Targeted influence maximization in complex networks

1]Renquan Zhang[style=chinese,

Designed this study, Wrote the code and first draft of the manuscript

[1]School of Mathematical Sciences, Dalian University of Technology,Dalian,116024,China

1]Xiaolin Wang[style=chinese]

Wrote the code, ran simulations and performed the analysis

2]Sen Pei[style=chinese,

[1]

Designed this study, reviewed and edited the manuscript

[2]Department of Environmental Health Sciences, Mailman School of Public Health, Columbia University,New York,10032,NY,USA

[cor1]Corresponding author

Many real-world applications based on spreading processes in complex networks aim to deliver information to specific target nodes. However, it remains challenging to optimally select a set of spreaders to initiate the spreading process. In this paper, we study the targeted influence maximization problem using a susceptible-infected-recovered (SIR) model as an example. Formulated as a combinatorial optimization, the objective is to identify a given number of spreaders that can maximize the influence over target nodes while minimize the influence over non-target nodes. To find a practical solution to this optimization problem, we develop a theoretical framework based on a message passing process and perform a stability analysis on the equilibrium solution using non-backtracking (NB) matrices. We propose that the spreaders can be selected by imposing optimal perturbation on the equilibrium solution for the subgraph consisting of the target nodes and their multi-step nearest neighbors while avoiding such perturbation on the complement graph that excludes target nodes from the original network. We further introduce a metric, termed targeted collective influence, for each node to identify influential spreaders for targeted spreading processes. The proposed method, validated in both synthetic and real-world networks, outperforms other competing heuristic approaches. Our results provide a framework for analyzing the targeted influence maximization problem and a practical method to identify spreaders in real-world applications.

* We developed a theoretical framework to analyze targeted influence maximization using a message passing process.

* We proposed a metric based on non-backtracking matrix to select influential spreaders.

* We validated the proposed metric in both synthetic and real-world networks.

Influential Spreaders Targeted Influence Maximization Spreading Dynamics Targeted Spreading Non-backtracking Matrix Optimal Perturbation

§ INTRODUCTION

Spreading processes in complex networks can describe a wide variety of real-world phenomena, ranging over epidemic outbreaks [Pastor-Satorras et al., 2015, Newman, 2002, Pastor-Satorras and Vespignani, 2001], online information diffusion [Zhang et al., 2016, Watts and Dodds, 2007, Goel et al., 2016, Zhou et al., 2020], behavior adoption [Centola, 2010, Granovetter, 1978, Aral and Walker, 2011], and viral marketing[Domingos and Richardson, 2001, Leskovec et al., 2007]. Due to the structural heterogeneity of networks, a small set of nodes play a disproportionate role in shaping the outcome of spreading dynamics. Identifying such pivotal nodes, or influencers, is a critical question in network science. Over the last decades, a plethora of studies developed methods to locate influential spreaders in networks [Kitsak et al., 2010, Aral and Walker, 2012, Pei et al., 2018, Lü et al., 2016], either a single node initiating the spreading process or multiple spreaders considering their collective influence [Kempe et al., 2003, Chen et al., 2009, Morone and Makse, 2015, Pei et al., 2014, Aral and Dhillon, 2018, Teng et al., 2016, Leskovec et al., 2007, Braunstein et al., 2016, Pei and Makse, 2013, Clusella et al., 2016, Radicchi and Castellano, 2016, Ren et al., 2019]. A review on recent advances in this area can be found in Ref [Pei et al., 2020].

Many real-world applications aim to deliver information to certain target nodes while avoiding reaching non-target nodes. For instance, in advertising, it is desirable to promote products to potential customers and minimize the coverage among other users for precise marketing; in an election campaign, it is more cost-effective to disseminate information to swing voters and save the resources spent on decided voters. Studies on targeted spreading and control have attracted much attention in recent years [Gao et al., 2014, Cornelius et al., 2013, Song et al., 2016, Li et al., 2015, Caliò et al., 2018, Caliò and Tagarelli, 2021, Ke et al., 2018, Su et al., 2018, Sun et al., 2016]. A number of heuristic methods were developed to identify influencers for targeted spreading processes. For instance, a greedy algorithm was proposed to select seeds in a spreading process with several constrains [Song et al., 2016]; a heuristic method based on local path counting was used to identify single spreaders in a targeted spreading process [Sun et al., 2016]; and real-time targeted online advertisement informed by key words was also tested [Li et al., 2015]. While these approaches were demonstrated effective in different settings, a general framework for analyzing the targeted influence maximization problem is lacking.

In this study, we focus on the influence maximization problem for a general targeted spreading process. Specifically, we aim to identify a given number of spreaders that maximize the influence over target nodes and minimize the influence over non-target nodes in a susceptible-infected-recovered (SIR) model. To solve this optimization problem, we first develop a mathematical framework to formulate the system as a message passing process, and then perform a stability analysis on the equilibrium solution using the non-backtracking (NB) matrix of the system [Hashimoto, 1989]. We argue that the spreaders can be selected by imposing optimal perturbation on the equilibrium solution for the subgraph consisting of the target nodes and their multi-step nearest neighbors while avoiding such perturbation on the complement graph that excludes target nodes from the original network. Our analysis leads to a theoretically based metric, termed targeted collective influence, to quantify the targeted influence of each node, which allows the selection of multiple influencers in the targeted spreading process. We validate the proposed method in both synthetic and real-world networks and demonstrate that it outperforms commonly used heuristic approaches. Our analysis provides a theoretical framework for analyzing the targeted influence maximization problem and a practical method to identify spreaders in real-world applications.

§ MODEL

We use a susceptible-infectious-recovered (SIR) agent-based model to simulate the spreading process in networks. Considering a network composed of $N$ nodes and $M$ undirected edges, denote $\{a_{ij}\}_{N\times N}$ as the binary adjacency matrix ($a_{ij}=1$ if node $i$ is connected to node $j$, and $a_{ij}=0$ otherwise). The binary variables $S_i(t)$, $I_i(t)$ and $R_i(t)$ represent that node $i$'s state is susceptible, infectious and recovered at time $t$, respectively. We denote the probability that an infectious node will infect its susceptible neighbor as $\beta$, and define $\gamma$ as the infectious period (without loss of generality, $\gamma=1$). At each time step $t$, a susceptible node $i$ ($S_i(t)=1$) can be infected by its neighbor $j$ in the infectious state ($I_j(t)=1$) with probability $\beta$. Meanwhile, nodes in the infectious state will transit to the recovered state after $\gamma$ steps and can never be infected again. The spreading process can be described as follows:

\begin{align}
&\frac{d S_i(t)}{dt}=-S_i(t)\big[1-\prod_{j}(1-\beta a_{ij}I_j(t))\big],\label{sir1}\\
&\frac{d I_i(t)}{dt}=S_i(t)\big[1-\prod_{j}(1-\beta a_{ij}I_j(t))\big]-\frac{I_i(t)}{\gamma}, \label{sir2}\\
&\frac{d R_i(t)}{dt}=\frac{I_i(t)}{\gamma}. \label{sir3}
\end{align}

Here we focus on a combinatorial optimization problem - how to select a given number of initial infected nodes, or seeds, to maximize infection among a specific group of nodes and minimize infection among others? Specifically, denote $V=V^T\bigcup V^{NT}$ as the set of nodes, where $V^T$ represents the set of target nodes and $V^{NT}$ the set of non-target ones. The seeds can be only selected from $V^{NT}$ and the number of seeds is denoted as $n^*$. Based on the SIR dynamics, the number of nodes that have been infected is equal to the number of the recovered nodes at the end of the spreading process. For a given network, the influence over the target and non-target nodes are defined as

\begin{align}
&f(s_{n^*})=\lim_{t\to\infty}\sum_{i\in V^T} R_i(t), \label{goal1} \\
&g(s_{n^*})=\lim_{t\to\infty}\sum_{i\in V^{NT}} R_i(t), \label{goal2}
\end{align}

where $s_{n^*}$ denotes the set of seeds with the size $n^*$. As the topological structure of the network plays a significant role in the spreading process, different combinations of seeds with the same size $n^*$ could lead to contrasting outcomes. We aim to find the optimal set of seeds such that $g(s_{n^*})/f(s_{n^*})$ is minimized for $f(s_{n^*})>0$.

§ METHOD

§.§ Message passing equations

We first formulate the propagation as a message passing process. Compared to the master equations defined using the adjacency matrix, the message passing process can better represent the SIR dynamics. Specifically, in the SIR model, backtracking infections ($i\to j\to i$) are not allowed as the transmission is irreversible. The adjacency matrix allows backtracking infections, which can introduce excessive dynamical resonance between pairs of connected nodes. In contract, the message passing process excludes backtracking spreading and was found superior in analyzing a number of dynamical models in complex networks [Morone and Makse, 2015, Pei et al., 2017, Karrer et al., 2014, Hamilton and Pryadko, 2014, Wang et al., 2018, Aleja et al., 2019, Zhang and Pei, 2018, Wang et al., 2019, Martin et al., 2014, Zhang et al., 2020, Kawamoto, 2016, Bordenave et al., 2015].

To study the impact of a node $j$ on its neighbor node $i$, we investigate the probability of node $i$ being infected if node $j$ is assumed to be absent from the network. For a link from $i$ to $j$ ($i\to j$, even if the link is undirected), suppose node $j$ is "virtually" removed from the network (i.e., creating a "cavity" at node $j$) and calculate the probability of node $i$ being infected in the absence of node $j$ at time $t$, which is represented as $S_{i\to j}(t)$. We apply the same procedure for $I$ and $R$. For sparse networks without too many short loops, the message passing process can be described by

\begin{align}
&S_{i\to j}(t+1)=S_{i\to j}(t)\prod_{k\backslash j}\left(1-\beta a_{ik}I_{k\to i}(t)\right), \label{mp1}\\
&I_{i\to j}(t+1)=S_{i\to j}(t)\big[1-\prod_{k\backslash j}\left(1-\beta a_{ik}I_{k\to i}(t)\right)\big]+I_{i\to j}(t)(1-\frac{1}{\gamma}), \label{mp2}\\
&R_{i\to j}(t+1)=R_{i\to j}(t)+\frac{I_{i\to j}(t)}{\gamma}. \label{mp3}
\end{align}

Here $k\backslash j$ means $k$ runs over all nodes except $j$. Denote $\lim\limits_{t\to \infty} S_{i\to j}(t)=S_{i\to j}$, $\lim\limits_{t\to \infty} I_{i\to j}(t)=I_{i\to j}$ and $\lim\limits_{t\to \infty} R_{i\to j}(t)=R_{i\to j}$. Note that Eq. (<ref>) is redundant. The steady state of the nonlinear dynamical system can be obtained by solving the following self-satisfying equations:

\begin{align}
&S_{i\to j}=S_{i\to j}\prod_{k\backslash j}\left(1-\beta a_{ik}I_{k\to i}\right), \label{steady1}\\
&I_{i\to j}=\gamma S_{i\to j}\big[1-\prod_{k\backslash j}\left(1-\beta a_{ik}I_{k\to i}\right)\big]. \label{steady2}
\end{align}

Illustration of the subgraph $G_s$ and $G_c$. a, The original network with $N=20$ and 5 target nodes highlighted in red. b, The subgraph $G_s$ with $L=2$. c, The subgraph $G_c$. The candidate seeds are the black nodes in b.

§.§ Stability analysis

To maximize influence over the target nodes and minimize influence over the non-target nodes, we consider two subgraphs of the original network: 1) a subgraph $G_s$ consisting of the target nodes and their nearest neighbors within $L$ steps, and 2) a subgraph $G_c$ that excludes the target nodes from the original network. We create $G_s$ using a breadth-first-search algorithm starting from the target nodes. An illustration for $G_s$ ($L=2$) and $G_c$ is shown in Fig. <ref>. As seeds can be only selected from the non-target nodes, we define the set of candidate seeds as the non-target nodes in $G_s$ (i.e., nodes in $G_s$ excluding the target nodes).

For both $G_s$ and $G_c$, a trivial equilibrium solution exists: $(S_{i\to j}^*,I_{i\to j}^*)^T=(\mathbf{1},\mathbf{0})^T$, corresponding to the state that all nodes are susceptible. The stability of the trivial solution is controlled by the largest eigenvalue of the Jacobian matrix ($\mathbf{J}$) at this solution. Now we derive the Jacobian matrix at the solution $(\mathbf{1},\mathbf{0})^T$ for $G_s$ and $G_c$. For a given network, we take the partial derivatives of Eq. (<ref>). For the  directed links $k\to l$ and $i\to j$, we have

\begin{equation}\label{p-ss}
\frac{\partial S_{i\to j}}{\partial S_{k\to l}}=\prod_{k\backslash j}\left(1-\beta a_{ik}I_{k\to i}(t)\right)\big\vert_{(\mathbf{1},\mathbf{0})}=\left\{
\begin{aligned}
&1 &  &\mbox{if}\; k=i\;\mbox{and}\; l=j\\
&0      &  &\mbox{otherwise}
\end{aligned}
\right.
\end{equation}

\begin{equation}\label{p-si}
\frac{\partial S_{i\to j}}{\partial I_{k\to l}}=-\beta S_{i\to j}(t)\prod_{k^{'}\backslash j,k}\left(1-\beta a_{ik^{'}}I_{k^{'}\to i}(t)\right)\bigg\vert_{(\mathbf{1},\mathbf{0})}=\left\{
\begin{aligned}
&-\beta &  &\mbox{if}\; l=i \;\mbox{and}\; k\neq j\\
&0      &  &\mbox{otherwise}
\end{aligned}
\right.
\end{equation}

The same analysis on Eq. (<ref>) yields:

\begin{align}\label{p-is}
\frac{\partial I_{i\to j}}{\partial S_{k\to l}}=\gamma\big[1-\prod_{k\backslash j}(1-\beta a_{ik}I_{k\to i}(t))\big]\big\vert_{(\mathbf{1},\mathbf{0})}=0
\end{align}

\begin{equation}\label{p-ii}
\frac{\partial I_{i\to j}}{\partial I_{k\to l}}=\beta\gamma S_{i\to j}(t)\big[\prod_{k^{'}\backslash j,k}(1-\beta a_{ik^{'}}I_{k^{'}\to i}(t))\big]\bigg\vert_{(\mathbf{1},\mathbf{0})}=\left\{
\begin{aligned}
&\beta\gamma &  &\mbox{if}\; l=i \;\mbox{and}\; k\neq j\\
&0     &  &\mbox{otherwise}
\end{aligned}
\right.
\end{equation}

So the Jacobian matrix at the solution $(\mathbf{1},\mathbf{0})^T$ is given by:

\begin{equation}\label{jacpbi}
\mathbf{J}\bigg\vert_{(\mathbf{1},\mathbf{0})}=\left(
\begin{aligned}
\mathbf{I}&   &\mathbf{A} \\
\mathbf{0}&   &\mathbf{B}
\end{aligned}
\right).
\end{equation}

Here $\mathbf{I}$ is the identity matrix, $\mathbf{A}=\left\{ \frac{\partial S_{i\to j}}{\partial I_{k\to l}}\right\}_{2M\times 2M}$ and $\mathbf{B}=\left\{ \frac{\partial I_{i\to j}}{\partial I_{k\to l}}\right\}_{2M\times 2M}$, where $M$ is the number of links. The stability of $I_{i\to j}^*$ is determined by the largest eigenvalue of the matrix $\mathbf{B}$, denoted by $\lambda_{B}$. The trivial solution is stable if $\lambda_{B}<1$ and unstable if $\lambda_{B}>1$. The matrix $\mathbf{B}$ is a generalization of the non-backtracking (NB) matrix of the network $\mathbf{W}$, which was found important for a range of dynamical processes in complex networks. Precisely, $\mathbf{B}=\beta\gamma\mathbf{W}$, where

\begin{equation}\label{NB}
\mathbf{W}_{k\to l,i\to j}=\left\{
\begin{aligned}
&1     &  &\mbox{if}\; l=i \;\mbox{and}\; k\neq j,\\
&0     &  &\mbox{otherwise.}
\end{aligned}
\right.
\end{equation}

§.§ Optimal perturbation

Selecting seeds to initiate a spreading process acts as a perturbation on the equilibrium solution. Define $\mathbf{I}_\to(0)=(\cdots,I_{i\to j}(0),\cdots)^T$ as the initial state. For the equilibrium solution, we have $\mathbf{I}_\to(0)=\mathbf{0}^T$. If node $i$ is chosen as a seed, we set the elements $I_{i\to j}(0)=1$ for all $j\in\partial i$, where $\partial i$ represents the set of neighbors of node $i$. To select a given number of $n^*$ seeds, there exist a total of $C^N_{n^*}$ possible combinations. In order to maximize influence over the target nodes, we can impose the optimal perturbation along the leading eigenvector of the NB matrix $\mathbf{W}$ for $G_s$ so that more nodes are infected in this subgraph. Meanwhile, we should avoid the perturbation in $G_c$ along the leading eigenvector of its NB matrix to minimize infections among non-target nodes. Similar approaches have been used in numerical weather prediction [Palmer, 2000, Toth and Kalnay, 1993, Toth and Kalnay, 1997] and infectious disease forecasting [Pei et al., 2019, Pei and Shaman, 2017, Pei et al., 2021].

Denote the leading eigenvector of $\mathbf{W}$ as $\mathbf{v}$ such that $\mathbf{Wv}=\lambda\mathbf{v}$, where $\lambda$ is the largest eigenvalue of $\mathbf{W}$. Computing the leading eigenvector for $\mathbf{W}$ can be challenging for large-scale networks due to the high dimensionality of the NB matrix. For a network with $M$ edges, $\mathbf{W}$ has a dimension of $2M\times 2M$. An effective method to compute the largest eigenvalue and the leading eigenvector is the power iteration. Starting from an initial vector $\mathbf{y}_0=\mathbf{1}^T$, we multiple $\mathbf{W}$ from the left ($\mathbf{y}_{t+1}=\mathbf{Wy}_t$) repeatedly until the ratio $\|\mathbf{y}_{t+1}\|/\|\mathbf{y}_t\|$ is stabilized. The largest eigenvalue is $\lambda=\lim_{t\to\infty}\|\mathbf{y}_{t+1}\|/\|\mathbf{y}_t\|$ and the normalized leading eigenvector is $\mathbf{v}=\lim_{t\to\infty}\mathbf{y}_t/\|\mathbf{y}_t\|$.

To approximate the leading eigenvector using the power iteration, we multiple $\mathbf{W}$ from the left on $\mathbf{y}_0=\mathbf{1}^T$ for $\ell$ times. We denote the approximated influence of node $i$ for $\ell$ as $CI_\ell(i)=\sum_{j\in\partial i}y_{\ell, i\to j}^2$, where $y_{\ell, i\to j}$ is the entry of $\mathbf{y}_\ell$ corresponding to the link $i\to j$. Following the method in Ref. [Morone and Makse, 2015], we derive that $CI_\ell(i)$ for node $i$ in a network is given by

\begin{align}
CI_{\ell}(i)=\left(k_{i}-1\right)\sum_{j\in \partial Ball(i,2\ell-1)}\left(k_{j}-1\right), \label{ci}
\end{align}

where $\ell$ is the iteration time and $\partial Ball(i,2\ell-1)$ is the set of nodes whose shortest distance to node $i$ is $2\ell-1$. In order to find spreaders for the targeted spreading process, we define the targeted collective influence for node $i$ at level $\ell$ as

\begin{align}
\Delta CI_{\ell}(i)=CI_{\ell}^{G_{s}}(i)-CI_{\ell}^{G_{c}}(i). \label{VS}
\end{align}

Here $CI_{\ell}^{G_{s}}(i)$ and $CI_{\ell}^{G_{c}}(i)$ are calculated on the subgraph $G_{s}$ and $G_{c}$. For the targeted influence maximization problem, we select top $n^{*}$ nodes from the candidates with the highest $\Delta CI_{\ell}$ score as the seed set $s_{n^*}$. Nodes with higher $\Delta CI_{\ell}$ scores tend to have higher $CI_{\ell}^{G_{s}}$ and lower $CI_{\ell}^{G_{c}}$.

§ NUMERICAL VALIDATION

In order to test the performance of the proposed targeted collective influence, we first run numerical simulations on synthetic networks. We consider the case that target nodes are connected in a local cluster. In experiments, we first randomly select a target node and then apply a breadth-first search to assign other target nodes until the predefined number of target nodes is reached. Without loss of generality, here we set 10 target nodes in each cluster. Once the target node set $V^{T}$ is assigned, we select spreaders using different methods. Starting from the selected seeds, we perform 100 independent realizations of the SIR model. Results are evaluated using the average of the 100 simulations.

To compute the targeted collective influence $\Delta CI_\ell$, we define $G_s$ as the subgraph consisting of the target nodes and their nearest neighbors within $L=7$ steps. Other values of $L$ were tested. We find that $L=7$ is enough to capture potential optimal spreaders and increasing $L$ does not improve the performance. In model simulations, we consider $\ell=1$ and $\ell=2$ to calculate $\Delta CI_\ell$. We compare the targeted collective influence $\Delta CI_1$ and $\Delta CI_2$ with several other competing methods, including (1) dynamical importance defined based on the eigenvector of the adjacency matrix of the original network $G$ (Eig) [Restrepo et al., 2006]; (2) the dynamical importance defined based on the eigenvector of the adjacency matrix of the subgraph $G_s$ (Eigs); (3) the degree centrality of $G$ (HD); (4) the degree centrality of $G_s$ (HDs); (5) the collective influence $CI_\ell$ of $G$ for $\ell=1$ in Eq. (<ref>) ($CI_1$); and (6) the collective influence $CI_\ell$ of $G$ for $\ell=2$ in Eq. (<ref>) ($CI_2$). More details of the competing methods are provided in Appendix <ref>. For each metric, we select the top $n^*$ nodes with the highest values as the initial seeds. For reference, we also test a random selection method (Rand) that chooses seeds randomly from $G$.

The probability that at least one target node is infected in Erdös-Rényi (ER) networks with size $N=10,000$ or $20,000$ and mean degree $\left<k\right>=3$ or $4$. We use different methods (including Rand, Eig, Eigs, HD, HDs, CI and $\Delta CI$ with $\ell=1$ and $\ell=2$) to select seeds for different size $n^{*}=2,\cdots,6$. The results are averaged over 100 independent realizations.

The ratio of $g(s_{n^*})$ to $f(s_{n^*})$ for Erdös-Rényi (ER) networks with size $N=10,000$ and mean degree $\left<k\right>=3$ or $4$. We compare the performance of different methods including Eigs, HDs, CI and $\Delta CI$ with $\ell=1$ and $\ell=2$. The results are averaged over 100 independent realizations.

§.§ Random networks

We first test on homogeneous Erdös-Rényi (ER) random networks with 10 target nodes. We generate undirected ER networks with size $N$ and average degree $\left<k\right>$ by randomly connecting any possible pairs of nodes with a probability $p=\left<k\right>/N$. We use networks with $N=10,000$ or $20,000$ and $\left<k\right>=3$ or $4$ in simulations shown in Figs. <ref> and <ref>. To ensure the connectivity of the graph, all simulations are only applied on the giant connected component. We vary the transmission rate $\beta\in \left[0.1,0.4\right]$ for $\left<k\right>=3$ and $\beta\in \left[0.1,0.3\right]$ for $\left<k\right>=4$. We don't consider higher transmission rate $\beta$ as it will lead to large-scale outbreaks that infect almost the entire network. We test the number of seeds $n^*=2,\cdots,6$ and set $\gamma=1$.

In Fig. <ref>, we show the probability that at least one target node is infected, $P_t$. As all target nodes are locally connected (as shown in Fig. <ref>a), $P_t$ measures the chance that the spreading process reaches the small cluster of target nodes in a large-scale network. The targeted collective influence $\Delta CI_{\ell}$ consistently outperforms other competing methods. However, $\Delta CI_1$ and $\Delta CI_2$ have similar results. As the transmission rate $\beta$ increases, $P_t$ increases for all methods. For $\beta<\langle k\rangle/(\langle k^2\rangle-\langle k\rangle)$, seeds selected by Rand, Eig, and HD can hardly infect any target nodes. For $\beta>\langle k\rangle/(\langle k^2\rangle-\langle k\rangle)$, all methods except Rand can almost always reach target nodes. Metrics defined on the subgraph $G_s$ performs better than their counterparts defined on the original network $G$. We examine the fraction of infected target nodes for all methods and find that the targeted collective influence performs best as well (see Appendix <ref>).

We evaluate the ratio of infected non-target node to infected target node ($g(s_{n^*})/f(s_{n^*})$) in Fig. <ref>. A lower ratio indicates a better performance of the method. Here we only compare Eigs, HDs, CI and $\Delta CI$ as other methods rarely infect target nodes. Again, we find that the targeted collective influence outperforms other competing approaches and $\Delta CI_2$ performs better than $\Delta CI_1$.

The probability that at least one target node is infected in scale-free (SF) networks with size $N=10,000$ or $20,000$ and degree distribution $P(k)\sim k^{-3}$. We use different methods (including Rand, Eig, Eigs, HD, HDs, CI and $\Delta CI$ with $\ell=1$ and $\ell=2$) to select the seeds for different size $n^{*}=2,\cdots,6$. The results are averaged over 100 independent realizations.

The ratio of $g(s_{n^*})$ to $f(s_{n^*})$ for scale-free (SF) networks with size $N=10,000$ or $20,000$. We compare the performances of different methods including Eigs, HDs, CI and $\Delta CI$ with $\ell=1$ and $\ell=2$. The results are averaged over 100 independent realizations.

The probability that at least one target node is infected in four real networks for 10 target nodes. The inset in each panel shows the ratio of $g(s_{n^*})$ to $f(s_{n^*})$. We use different methods (including Rand, Eig, Eigs, HD, HDs, CI and $\Delta CI$ with $\ell=1$ and $\ell=2$) to select the seeds for size $n^{*}=4$. a, The co-authorship network of scientists with $N=379$ and $M=914$. b, The US power Grid network with $N=4.9K$ and $M=6.6K$. c, The web graph network with $N=16.1K$ and $M=25.6K$. d, The recommendation network of Amazon with $N=91.8K$ and $M=125.7K$.

§.§ Scale-free networks

We perform the same analysis on scale-free (SF) networks with 10 target nodes. The SF networks have power-law degree distributions. We generate undirected SF networks with $N=10,000$ or $20,000$ using the preferential attachment model [Barabási and Albert, 1999]. Simulation results are shown in Figs. (<ref>) and (<ref>). We find that the targeted collective influence performs better than competing methods. Interestingly, for SF networks, $\Delta CI_1$ outperforms $\Delta CI_2$. This is possibly due to the existence of highly connected hubs. $\Delta CI_2$ may select global hubs that have both high $CI^{G_s}$ and $CI^{G_c}$ but are far from target nodes. In contrast, $\Delta CI_1$ can potentially select local hubs that are close to target nodes. Further analyses are needed to test this hypothesis in future works.

§.§ Real-world networks

We finally validate the proposed method in several real-world networks [Rossi and Ahmed, 2015]. Four real networks of distinct types are selected, including a co-authorship network ($N=379$ and $M=914$), the US power grid network ($N=4.9K$ and $M=6.6K$), a web graph network (links between webpages) ($N=16.1K$ and $M=25.6K$), and a recommendation network of Amazon ($N=91.8K$ and $M=125.7K$). Data sources and statistics of the networks are reported in Appendix <ref>.

In the first set of experiments, we assign 10 target nodes in one cluster and aim to find $n^*=4$ seeds. Experiment results are shown in Fig. (<ref>). Consistent with simulations on synthetic networks, the targeted collective influence performs best. A same method can have different performance in the four real-world networks depending on the network structure. For instance, HD performs much worse in the US power grid network and the Amazon recommendation network. However, the good performance of $\Delta CI_1$ and $\Delta CI_2$ is robust across all tested networks. $\Delta CI_1$ is generally better than $\Delta CI_2$ in the four networks. For the more heterogeneous web graph network (the maximum degree is 1.7K and the average degree is 3), the advantage of $\Delta CI_1$ over $\Delta CI_2$ is more prominent, which agrees with the results in SF networks.

We further consider the case that target nodes are located in several clusters that spread across the network. Specifically, we select two clusters of target nodes, each cluster with 10 target nodes. This optimization problem is more challenging as target nodes are not located in one place. Results shown in Fig. (<ref>) indicate that $\Delta CI_1$ and $\Delta CI_2$ still outperform competing methods. The advantage of $\Delta CI_1$ and $\Delta CI_2$ is more prominent in sparse networks with lower average degrees (e.g., the recommendation network of Amazon and the US power grid). We additionally test the case with 30 target nodes in three clusters. Results in Fig. (<ref>) demonstrate the consistent better performance of $\Delta CI_1$ and $\Delta CI_2$.

§ CONCLUSION

Targeted influence maximization has broad applications in real-world problems. In this study, we formulated the SIR model using a message passing process, which can better represent the transmission dynamics, and further developed a theoretical framework to analyze the targeted influence maximization problem based on stability analysis and optimal perturbation. Our analysis led to the a metric, termed targeted collective influence, that was used to identify influential spreaders in targeted spreading process. We validated the proposed method in both synthetic and real-world networks, demonstrating its robust performance that out-competes commonly used approaches. Our study provides a theoretically based metric that was shown effective in a range of network structures.

§ COMPETING METHODS

We compare the targeted collective influence with several heuristic metrics that are widely used to rank the spreading capability of nodes. In numerical simulations, all nodes are ranked by each method and then the top $n^{*}$ nodes with highest scores are selected as the set of seeds $S_{n^{*}}$.

* Eigenvector-based ranking. The dynamical importance of nodes can be quantified using the eigenvector corresponding to the largest eigenvalue of the adjacency matrix [Restrepo et al., 2006]. Using a perturbation analysis on the largest eigenvalue, the dynamical importance of a node $i$ is calculated as

\begin{equation}\label{eig}
I_{i}=\frac{v_i u_i}{\mathbf{v}^T \mathbf{u}},
\end{equation}

where $\mathbf{v}$ and $\mathbf{u}$ denote the right and left eigenvectors of the adjacency matrix $\{a_{ij}\}_{N\times N}$. In simulations, we use two versions of this method - Eig (for the original network) and Eigs (for the subgraph $G_{s}$).

* Degree-based ranking. In high degree (HD) ranking, the score of each node $i$ is determined by the number of its connections: $K^{HD}_{i}=\sum_{j\in\partial i}a_{ij}$. We also compare with the HD ranking in the subgraph $G_{s}$ (HDs).

* Collective influence. The collective influence (CI) of each node is computed using power iteration that aims to estimate the largest eigenvalue of the NB matrix of the network [Morone and Makse, 2015]. Specifically, the CI score of node $i$ at level $\ell$ is $CI_{\ell}(i)=\left(k_{i}-1\right)\sum_{j\in \partial Ball(i,2\ell-1)}\left(k_{j}-1\right)$.

§ ADDITIONAL EXPERIMENTS

Figures (<ref>) and (<ref>) show the fraction of infected target nodes for all methods in Erdös-Rényi networks and scale-free networks respectively. Figures (<ref>) and (<ref>) show the results when target nodes are located in two and three clusters.

The fraction of infected target nodes in Erdös-Rényi (ER) networks with size $N=10,000$ or $20,000$ and mean degree $\left<k\right>=3$ or $4$. We use different methods (including Rand, Eig, Eigs, HD, HDs, CI and $\Delta CI$ with $\ell=1$ and $\ell=2$) to select seeds for different size $n^{*}=2,\cdots,6$. The results are averaged over 100 independent realizations.

The fraction of infected target nodes in scale-free (SF) networks with size $N=10,000$ or $20,000$ and degree distribution $P(k)\sim k^{-3}$. We use different methods (including Rand, Eig, Eigs, HD, HDs, CI and $\Delta CI$ with $\ell=1$ and $\ell=2$) to select the seeds for different size $n^{*}=2,\cdots,6$. The results are averaged over 100 independent realizations.

The probability that at least one target node is infected in four real networks with 20 target nodes. The inset in each panel shows the ratio of $g(s_{n^*})$ to $f(s_{n^*})$. We use different methods (including Rand, Eig, Eigs, HD, HDs, CI and $\Delta CI$ with $\ell=1$ and $\ell=2$) to select the seeds for size $n^{*}=4$. a, The co-authorship network of scientists with $N=379$ and $M=914$. b, The US power Grid network with $N=4.9K$ and $M=6.6K$. c, The web graph network with $N=16.1K$ and $M=25.6K$. d, The recommendation network of Amazon with $N=91.8K$ and $M=125.7K$.

The probability that at least one target node is infected in four real networks with 30 target nodes. The inset in each panel shows the ratio of $g(s_{n^*})$ to $f(s_{n^*})$. We use different methods (including Rand, Eig, Eigs, HD, HDs, CI and $\Delta CI$ with $\ell=1$ and $\ell=2$) to select the seeds for size $n^{*}=4$. a, The co-authorship network of scientists with $N=379$ and $M=914$. b, The US power Grid network with $N=4.9K$ and $M=6.6K$. c, The web graph network with $N=16.1K$ and $M=25.6K$. d, The recommendation network of Amazon with $N=91.8K$ and $M=125.7K$.

§ NETWORK DATA

Network data are downloaded from the following websites. (1) The co-authorship network of scientists (<https://networkrepository.com/ca-netscience.php>). (2) The US power Grid network (<https://networkrepository.com/USpowerGrid.php>). (3) The web graph network (<https://networkrepository.com/web-webbase-2001.php>). (4) The recommendation networks of Amazon (<https://networkrepository.com/rec-amazon.php>).

The properties of real-world networks used in this paper

Size $N$     Links $M$     $\left<k\right>$     Maximum Degree     Maximum k-core

Co-authorship     379     914     4     34     9

US power Grid     4.9K     6.6K     2     19     6

Web-web graph     16.1K     25.6K     3     1.7K     33

Rec-amazon     91.8K     125.7K     2     5     5

§ ACKNOWLEDGEMENTS

R.Zhang is supported by National Key Research and Development Program of China (Grant No.2021ZD0112400 and No.2020YFA0713702), National Natural Science Foundation of China (Grant No.11801058) and High-level Talents program of Dalian City (Grant No.2020RQ061).

[Pastor-Satorras et al., 2015]
authorR. Pastor-Satorras, authorC. Castellano,
authorP. Van Mieghem, authorA. Vespignani,
titleEpidemic processes in complex networks,
journalReviews of modern physics volume87
(year2015) pages925.

[Newman, 2002]
authorM. E. Newman,
titleSpread of epidemic disease on networks,
journalPhysical review E volume66
(year2002) pages016128.

[Pastor-Satorras and Vespignani, 2001]
authorR. Pastor-Satorras, authorA. Vespignani,
titleEpidemic spreading in scale-free networks,
journalPhysical review letters volume86
(year2001) pages3200.

[Zhang et al., 2016]
authorZ.-K. Zhang, authorC. Liu, authorX.-X.
Zhan, authorX. Lu, authorC.-X. Zhang,
authorY.-C. Zhang,
titleDynamics of information diffusion and its
applications on complex networks,
journalPhysics Reports volume651
(year2016) pages1–34.

[Watts and Dodds, 2007]
authorD. J. Watts, authorP. S. Dodds,
titleInfluentials, networks, and public opinion
journalJournal of consumer research volume34
(year2007) pages441–458.

[Goel et al., 2016]
authorS. Goel, authorA. Anderson,
authorJ. Hofman, authorD. J. Watts,
titleThe structural virality of online diffusion,
journalManagement Science volume62
(year2016) pages180–196.

[Zhou et al., 2020]
authorB. Zhou, authorS. Pei,
authorL. Muchnik, authorX. Meng,
authorX. Xu, authorA. Sela,
authorS. Havlin, authorH. E. Stanley,
titleRealistic modelling of information spread using
peer-to-peer diffusion patterns,
journalNature Human Behaviour volume4
(year2020) pages1198–1207.

[Centola, 2010]
authorD. Centola,
titleThe spread of behavior in an online social network
journalscience volume329
(year2010) pages1194–1197.

[Granovetter, 1978]
authorM. Granovetter,
titleThreshold models of collective behavior,
journalAmerican journal of sociology volume83
(year1978) pages1420–1443.

[Aral and Walker, 2011]
authorS. Aral, authorD. Walker,
titleCreating social contagion through viral product
design: A randomized trial of peer influence in networks,
journalManagement science volume57
(year2011) pages1623–1639.

[Domingos and Richardson, 2001]
authorP. Domingos, authorM. Richardson,
titleMining the network value of customers,
in: booktitleProceedings of the seventh ACM SIGKDD
international conference on Knowledge discovery and data mining,
year2001, pp. pages57–66.

[Leskovec et al., 2007]
authorJ. Leskovec, authorL. A. Adamic,
authorB. A. Huberman,
titleThe dynamics of viral marketing,
journalACM Transactions on the Web (TWEB)
volume1 (year2007) pages5–es.

[Kitsak et al., 2010]
authorM. Kitsak, authorL. K. Gallos,
authorS. Havlin, authorF. Liljeros,
authorL. Muchnik, authorH. E. Stanley,
authorH. A. Makse,
titleIdentification of influential spreaders in complex
journalNature physics volume6
(year2010) pages888–893.

[Aral and Walker, 2012]
authorS. Aral, authorD. Walker,
titleIdentifying influential and susceptible members of
social networks,
journalScience volume337
(year2012) pages337–341.

[Pei et al., 2018]
authorS. Pei, authorF. Morone, authorH. A.
titleTheories for influencer identification in complex
in: booktitleComplex spreading phenomena in social
systems, publisherSpringer, year2018, pp.

[Lü et al., 2016]
authorL. Lü, authorD. Chen, authorX.-L.
Ren, authorQ.-M. Zhang, authorY.-C. Zhang,
authorT. Zhou,
titleVital nodes identification in complex networks,
journalPhysics Reports volume650
(year2016) pages1–63.

[Kempe et al., 2003]
authorD. Kempe, authorJ. Kleinberg,
authorÉ. Tardos,
titleMaximizing the spread of influence through a social
in: booktitleProceedings of the ninth ACM SIGKDD
international conference on Knowledge discovery and data mining,
year2003, pp. pages137–146.

[Chen et al., 2009]
authorW. Chen, authorY. Wang,
authorS. Yang,
titleEfficient influence maximization in social networks,
in: booktitleProceedings of the 15th ACM SIGKDD
international conference on Knowledge discovery and data mining,
year2009, pp. pages199–208.

[Morone and Makse, 2015]
authorF. Morone, authorH. A. Makse,
titleInfluence maximization in complex networks through
optimal percolation,
journalNature volume524
(year2015) pages65–68.

[Pei et al., 2014]
authorS. Pei, authorL. Muchnik, authorJ. S.
Andrade Jr, authorZ. Zheng, authorH. A. Makse,
titleSearching for superspreaders of information in
real-world social media,
journalScientific reports volume4
(year2014) pages1–12.

[Aral and Dhillon, 2018]
authorS. Aral, authorP. S. Dhillon,
titleSocial influence maximization under empirical
influence models,
journalNature human behaviour volume2
(year2018) pages375–382.

[Teng et al., 2016]
authorX. Teng, authorS. Pei,
authorF. Morone, authorH. A. Makse,
titleCollective influence of multiple spreaders evaluated
by tracing real information flow in large-scale social networks,
journalScientific reports volume6
(year2016) pages1–11.

[Leskovec et al., 2007]
authorJ. Leskovec, authorA. Krause,
authorC. Guestrin, authorC. Faloutsos,
authorJ. VanBriesen, authorN. Glance,
titleCost-effective outbreak detection in networks,
in: booktitleProceedings of the 13th ACM SIGKDD
international conference on Knowledge discovery and data mining,
year2007, pp. pages420–429.

[Braunstein et al., 2016]
authorA. Braunstein, authorL. Dall’Asta,
authorG. Semerjian, authorL. Zdeborová,
titleNetwork dismantling,
journalProceedings of the National Academy of Sciences
volume113 (year2016) pages12368–12373.

[Pei and Makse, 2013]
authorS. Pei, authorH. A. Makse,
titleSpreading dynamics in complex networks,
journalJournal of Statistical Mechanics: Theory and
Experiment volume2013 (year2013)

[Clusella et al., 2016]
authorP. Clusella, authorP. Grassberger,
authorF. J. Pérez-Reche, authorA. Politi,
titleImmunization and targeted destruction of networks
using explosive percolation,
journalPhysical review letters volume117
(year2016) pages208301.

[Radicchi and Castellano, 2016]
authorF. Radicchi, authorC. Castellano,
titleLeveraging percolation theory to single out
influential spreaders in networks,
journalPhysical Review E volume93
(year2016) pages062314.

[Ren et al., 2019]
authorX.-L. Ren, authorN. Gleinig,
authorD. Helbing, authorN. Antulov-Fantulin,
titleGeneralized network dismantling,
journalProceedings of the national academy of sciences
volume116 (year2019) pages6554–6559.

[Pei et al., 2020]
authorS. Pei, authorJ. Wang,
authorF. Morone, authorH. A. Makse,
titleInfluencer identification in dynamical complex
journalJournal of Complex Networks volume8
(year2020) pagescnz029.

[Gao et al., 2014]
authorJ. Gao, authorY.-Y. Liu, authorR. M.
D'souza, authorA.-L. Barabási,
titleTarget control of complex networks,
journalNature communications volume5
(year2014) pages1–8.

[Cornelius et al., 2013]
authorS. P. Cornelius, authorW. L. Kath,
authorA. E. Motter,
titleRealistic control of network dynamics,
journalNature communications volume4
(year2013) pages1–9.

[Song et al., 2016]
authorC. Song, authorW. Hsu, authorM. L.
titleTargeted influence maximization in social networks,
in: booktitleProceedings of the 25th ACM International on
Conference on Information and Knowledge Management, year2016,
pp. pages1683–1692.

[Li et al., 2015]
authorY. Li, authorD. Zhang, authorK.-L.
titleReal-time targeted influence maximization for online
advertisements  (year2015).

[Caliò et al., 2018]
authorA. Caliò, authorR. Interdonato,
authorC. Pulice, authorA. Tagarelli,
titleTopology-driven diversity for targeted influence
maximization with application to user engagement in social networks,
journalIEEE Transactions on Knowledge and Data
Engineering volume30 (year2018)

[Caliò and Tagarelli, 2021]
authorA. Caliò, authorA. Tagarelli,
titleAttribute based diversification of seeds for targeted
influence maximization,
journalInformation Sciences volume546
(year2021) pages1273–1305.

[Ke et al., 2018]
authorX. Ke, authorA. Khan, authorG. Cong,
titleFinding seeds and relevant tags jointly: For targeted
influence maximization in social networks,
in: booktitleProceedings of the 2018 International
Conference on Management of Data, year2018, pp.

[Su et al., 2018]
authorS. Su, authorX. Li, authorX. Cheng,
authorC. Sun,
titleLocation-aware targeted influence maximization in
social networks,
journalJournal of the Association for Information Science
and Technology volume69 (year2018)

[Sun et al., 2016]
authorY. Sun, authorL. Ma, authorA. Zeng,
authorW.-X. Wang,
titleSpreading to localized targets in complex networks,
journalScientific reports volume6
(year2016) pages1–10.

[Hashimoto, 1989]
authorK.-i. Hashimoto,
titleZeta functions of finite graphs and representations
of p-adic groups,
in: booktitleAutomorphic forms and geometry of arithmetic
varieties, publisherElsevier, year1989, pp.

[Pei et al., 2017]
authorS. Pei, authorX. Teng,
authorJ. Shaman, authorF. Morone,
authorH. A. Makse,
titleEfficient collective influence maximization in
cascading processes with first-order transitions,
journalScientific reports volume7
(year2017) pages1–13.

[Karrer et al., 2014]
authorB. Karrer, authorM. E. Newman,
authorL. Zdeborová,
titlePercolation on sparse networks,
journalPhysical review letters volume113
(year2014) pages208702.

[Hamilton and Pryadko, 2014]
authorK. E. Hamilton, authorL. P. Pryadko,
titleTight lower bound for percolation threshold on an
infinite graph,
journalPhysical review letters volume113
(year2014) pages208701.

[Wang et al., 2018]
authorJ. Wang, authorS. Pei, authorW. Wei,
authorX. Feng, authorZ. Zheng,
titleOptimal stabilization of boolean networks through
collective influence,
journalPhysical Review E volume97
(year2018) pages032305.

[Aleja et al., 2019]
authorD. Aleja, authorR. Criado,
authorA. J. G. del Amo, authorÁ. Pérez,
authorM. Romance,
titleNon-backtracking pagerank: From the classic model to
hashimoto matrices,
journalChaos, Solitons & Fractals volume126
(year2019) pages283–291.

[Zhang and Pei, 2018]
authorR. Zhang, authorS. Pei,
titleDynamic range maximization in excitable networks,
journalChaos: An Interdisciplinary Journal of Nonlinear
Science volume28 (year2018) pages013103.

[Wang et al., 2019]
authorJ. Wang, authorR. Zhang,
authorW. Wei, authorS. Pei,
authorZ. Zheng,
titleOn the stability of multilayer boolean networks under
targeted immunization,
journalChaos: An Interdisciplinary Journal of Nonlinear
Science volume29 (year2019) pages013133.

[Martin et al., 2014]
authorT. Martin, authorX. Zhang, authorM. E.
titleLocalization and centrality in networks,
journalPhysical review E volume90
(year2014) pages052808.

[Zhang et al., 2020]
authorR. Zhang, authorG. Quan,
authorJ. Wang, authorS. Pei,
titleBacktracking activation impacts the criticality of
excitable networks,
journalNew Journal of Physics volume22
(year2020) pages013038.

[Kawamoto, 2016]
authorT. Kawamoto,
titleLocalized eigenvectors of the non-backtracking
journalJournal of Statistical Mechanics: Theory and
Experiment volume2016 (year2016)

[Bordenave et al., 2015]
authorC. Bordenave, authorM. Lelarge,
authorL. Massoulié,
titleNon-backtracking spectrum of random graphs: community
detection and non-regular ramanujan graphs,
in: booktitle2015 IEEE 56th Annual Symposium on
Foundations of Computer Science, organizationIEEE,
year2015, pp. pages1347–1357.

[Palmer, 2000]
authorT. N. Palmer,
titlePredicting uncertainty in forecasts of weather and
journalReports on Progress in Physics
volume63 (year2000) pages71–116.

[Toth and Kalnay, 1993]
authorZ. Toth, authorE. Kalnay,
titleEnsemble forecasting at nmc: The generation of
journalBulletin of the american meteorological society
volume74 (year1993) pages2317–2330.

[Toth and Kalnay, 1997]
authorZ. Toth, authorE. Kalnay,
titleEnsemble forecasting at ncep and the breeding
journalMonthly Weather Review volume125
(year1997) pages3297–3319.

[Pei et al., 2019]
authorS. Pei, authorM. A. Cane,
authorJ. Shaman,
titlePredictability in process-based ensemble forecast of
journalPLoS computational biology volume15
(year2019) pagese1006783.

[Pei and Shaman, 2017]
authorS. Pei, authorJ. Shaman,
titleCounteracting structural errors in ensemble forecast
of influenza outbreaks,
journalNature communications volume8
(year2017) pages1–10.

[Pei et al., 2021]
authorS. Pei, authorX. Teng,
authorP. Lewis, authorJ. Shaman,
titleOptimizing respiratory virus surveillance networks
using uncertainty propagation,
journalNature communications volume12
(year2021) pages1–10.

[Restrepo et al., 2006]
authorJ. G. Restrepo, authorE. Ott,
authorB. R. Hunt,
titleCharacterizing the dynamical importance of network
nodes and links,
journalPhysical review letters volume97
(year2006) pages094102.

[Barabási and Albert, 1999]
authorA.-L. Barabási, authorR. Albert,
titleEmergence of scaling in random networks,
journalScience volume286
(year1999) pages509–512.

[Rossi and Ahmed, 2015]
authorR. Rossi, authorN. Ahmed,
titleThe network data repository with interactive graph
analytics and visualization,
in: booktitleTwenty-ninth AAAI conference on artificial
intelligence, year2015.


# I’m in AGNi: A new standard for AGN pluralisation

Andrew D. Gow1, Peter Clark1 and Dan Rycanowski1
1Institute of Cosmology & Gravitation, University of Portsmouth, Dennis Sciama
Building, Burnaby Road, Portsmouth, PO1 3FX, United Kingdom E-mail:
<EMAIL_ADDRESS>
(Accepted 01 April 2024. Received 01 April 2024; in original form 01 April
2024)

###### Abstract

We present a new standard acronym for Active Galactic Nuclei, finally settling
the argument of AGN vs. AGNs. Our new standard is not only etymologically
superior (following the consensus set by SNe), but also boasts other
linguistic opportunities, connecting strongly with relevant theology and
streamlining descriptions of AGN properties.

###### keywords:

AGN – AGNs – AGNi – Active Galactic Nucleus – Active Galactic Nuclei

††pubyear: 2024††pagerange: I’m in AGNi: A new standard for AGN
pluralisation–I’m in AGNi: A new standard for AGN pluralisation

##  1 Introduction

The center of most galaxies hosts a supermassive black hole (SMBH) which can
display a wide range of accretion rates, from essentially zero to values up to
a solar mass per day (Wolf et al., 2024). The accretion of material onto a
SMBH via an accretion disk can produce high luminosities through frictional
heating of material generating high temperature blackbody emission, with this
emission in some cases approaching the Eddington Luminosity. The specific
threshold for when a galaxy’s SMBH, and thus nucleus, is considered to be
‘active’ is not concretely established though luminosity and central SMBH mass
cuts are used to divide these galaxies from their more sedate compatriots.
Such a nucleus is termed an Active Galactic Nucleus or AGN.

The presence of an AGN can dominate the spectral properties of the host
galaxy, with the accreting SMBH contributing more light than the stellar
population of the galaxy as a whole, despite occupying only a tiny portion of
its overall volume. The specifics of these effects are wide ranging with some
Active Galactic Nuclei displaying extremely broad spectroscopic emission
features, others showing only narrow (but strong) emission lines. A subset of
the population are very luminous in the radio (radio-loud) whilst others emit
only faintly in this regime (radio-quiet). This range in properties posed a
significant challenge in the the study of these objects, though these apparent
dichotomies have been resolved through the development of the unified model of
AGN physics. Detailed modeling revealed that the full range of displayed
properties can indeed be attributed to accretion onto SMBHs when the structure
of the local environment, line-of-sight effects from differential obscuration
and the presence (or absence) of jets are considered, see Netzer (2015) for a
recent detailed review.

Whilst the unified model of AGN physics is widely accepted, and can be seen as
as a beacon of unity within the astrophysics community, the choice of
initialism when referring to Active Galactic Nuclei in plurality is far less
harmonious. The two options currently in use are AGN (Arons et al., 1975;
Kauffmann et al., 2003; Svoboda et al., 2017; Mountrichas et al., 2024; Clark
et al., 2024a), where the singular versus plural cases are distinguished via
context, and AGNs (Yee, 1980; Kewley et al., 2001; Jiang et al., 2016;
Rałowski et al., 2024; Clark et al., 2024b), with many examples of both
appearing throughout the literature. This lack of standardisation is an
unnecessary waste of time, and can potentially cause confusion when reading
papers about Active Galactic Nuclei. Therefore, we believe a new standard is
required.

##  2 A new plural acronym

To avoid any future disagreement about the correct way to pluralise this
initialism, we introduce a new option which is superior to both previous
choices, which we believe should become the standard case used in all
literature. We suggest that the correct way to pluralise AGN is AGNi. This is
etymologically stronger than either of the other choices, connecting to the
Latin root of the word nucleus, and follows the consensus set by other similar
initialisms e.g. supernovae (SNe), (proto-)planetary nebulae ((P)PNe), and
pulsar wind nebulae (PWNe).

Not only is this choice etymologically superior, but it allows for an increase
in speed when discussing these objects. While AGN is an initialism, where the
letters are read out individually, AGNi can be promoted to a full acronym,
pronounced as a single word and thus boasting a significant 33.3 per cent
increase in speaking efficiency—a metric widely utilised in the yapping
community. This additionally provides many linguistic opportunities (puns)
frequently used by the astronomy community. The simplest of these is the
similarity to the word agony, as used in the title of this paper. This extends
to concepts such as an AGNi aunt (a galaxy that displayed AGN activity in a
past phase of evolution but is not currently active e.g., IC 2497 Lintott et
al. (2009)), and AGNiser (Bixby, 2024a, b) (bright AGNi that agonise
astronomers by saturating all of their images). Additionally, any notable
survey of AGNi led by a Swedish institution would of course be named AGNitha,
in honour of Agnetha Fältskog from ABBA.

This acronym also provides a convenient shorthand for discourse in the field.
For example the brightness across multiple AGNi would be simply the apparent
or absolute mAGNitude, and members of the community who are unsure of the
legitimate status of AGNi would be AGNistic. However, the benefits of this
acronym do not stop with the ability to make puns. There is also a strong
connection to theology through the Hindu god Agni (Olivelle, 1998; Lochtefeld,
2002; Jamison & Brereton, 2014) (see fig. 1). Agni is the god of fire (the
name is connected to the English word ignite), providing clear parallels with
the high energy nature of AGNi.

Figure 1: Illustration of the Hindu god Agni (Non, 2024).

However, for this acronym to be adopted, it is clear that there must be
significant support from the scientific community. To this end, we have
carried out an anonymous (pay no attention to any names in the
acknowledgements) survey of astronomers and cosmologists, the results of which
are displayed in table 1 and figs. 2 and 3. It is clear that the new option
AGNi is strongly favoured by the scientific community and would be rapidly
picked up by authors and then by journals. Therefore, we have no concerns that
this form of acronym for the plural would not survive in the literature.

Table 1: Results of the anonymous survey of acronym choice. AGN |  | AGNs |  | AGNi
---|---|---|---|---
5 |  | 5 |  | 22

Figure 2: Results of the anonymous survey of acronym choice. Figure 3: Results
of the anonymous survey of acronym choice.

##  3 Conclusion and future work

In this short note, we have introduced a new standard acronym for Active
Galactic Nuclei, namely AGNi. This acronym is superior in multiple ways,
connecting to the Latin roots and cosmological theology, and also opens up
linguistic opportunities in the discussion of AGNi, as well as new naming
conventions for surveys or collaborations.

Going beyond this work, we can apply the same logic to all astronomy acronyms
and initialisms that derive from Latin roots. Examples of this include
Transient Lunar Phenomena (TLPa rather than TLPs), and the InterStellar Media
etc. (ISMa, IGMa, ICMa rather than ISMs etc.). These forms could be included
in longer acronyms, such as Clumpy Hydrogen-$\alpha$-Rich InterStellar Media
(CH$\alpha$RISMa) and ENergetic InterGalactic Media (ENIGMa).

## Acknowledgements

The authors would like to thank Lisa Kelsey, Emily Wickens and Michael
Williams for informative discussions. We also thank Daniel Ballard, Molly
Burkmar, Joe Callow, Elena Colangeli, Nathan Cruickshank, Fox Davidson,
Wolfgang Enzi, Nathan Findlay, Bartolomeo Fiorini, Kieran Graham, Susanna
Green, Rafaela Gsponer, Rhiannon Harries, Sophie Hoyland, Joseph Jackson,
Shahab Joudaki, Lisa Kelsey, Sravan Kumar, Ricardo Landim, Konstantin Leyde,
Tian Li, Sophie Newman, Daniela Saadeh, Ana Sainz De Murieta Martinez-Zubiri,
Ashim Sen Gupta, Neel Shah, Sergi Sirera Lahoz, Han Wang, Luke Weisenbach,
Arthur Whyley, Emily Wickens, Michael Williams, and the PhD students and
postdocs at the Institute of Cosmology & Gravitation for contributing to the
anonymous survey.

## Data Availability

For the purpose of open access, the authors have applied a Creative Commons
Attribution (CC BY) licence to any Author Accepted Manuscript version arising.
Supporting research data are available on reasonable request from the
corresponding author, Andrew Gow.

## References

  * Arons et al. (1975) Arons J., Kulsrud R. M., Ostriker J. P., 1975, The Astrophysical Journal, 198, 687
  * Bixby (2024a) Bixby J., accessed 27/03/2024a, Agonizer, https://memory-alpha.fandom.com/wiki/Agonizer
  * Bixby (2024b) Bixby J., accessed 27/03/2024b, Mirror, Mirror (episode), https://memory-alpha.fandom.com/wiki/Mirror,_Mirror_(episode)
  * Clark et al. (2024a) Clark P., et al., 2024a, arXiv
  * Clark et al. (2024b) Clark P., et al., 2024b, Monthly Notices of the Royal Astronomical Society, 528, 7076
  * Jamison & Brereton (2014) Jamison S., Brereton J., 2014, The Rigveda: 3-Volume Set. Oxford University Press, https://books.google.co.uk/books/about/The_Rigveda_3_Volume_Set.html?id=fgzVAwAAQBAJ&redir_esc=y
  * Jiang et al. (2016) Jiang N., Wang H., Mo H., Dong X.-B., Wang T., Zhou H., 2016, The Astrophysical Journal, 832, 111
  * Kauffmann et al. (2003) Kauffmann G., et al., 2003, Monthly Notices of the Royal Astronomical Society, 346, 1055
  * Kewley et al. (2001) Kewley L. J., Dopita M. A., Sutherland R. S., Heisler C. A., Trevena J., 2001, The Astrophysical Journal, 556, 121
  * Lintott et al. (2009) Lintott C. J., et al., 2009, Monthly Notices of the Royal Astronomical Society, 399, 129
  * Lochtefeld (2002) Lochtefeld J., 2002, The Illustrated Encyclopedia of Hinduism. Rosen Publishing Group, https://books.google.co.uk/books/about/The_Illustrated_Encyclopedia_of_Hinduism.html?id=5kl0DYIjUPgC&redir_esc=y
  * Mountrichas et al. (2024) Mountrichas G., Viitanen A., Carrera F. J., Stiele H., Ruiz A., Georgantopoulos I., Mateos S., Corral A., 2024, Astronomy & Astrophysics, 683, A172
  * Netzer (2015) Netzer H., 2015, Annual Review of Astronomy and Astrophysics, 53, 365
  * Non (2024) Non A., accessed 27/03/2024, File:Agni 18th century miniature.jpg, https://commons.wikimedia.org/wiki/File:Agni_18th_century_miniature.jpg
  * Olivelle (1998) Olivelle P., 1998, The Early Upanishads: Annotated Text and Translation. Oxford University Press, https://books.google.co.uk/books/about/The_Early_Upanishads.html?id=Lsp18ZvstrcC&redir_esc=y
  * Rałowski et al. (2024) Rałowski M., Hryniewicz K., Pollo A., Stawarz Ł., 2024, Astronomy & Astrophysics, 682, A120
  * Svoboda et al. (2017) Svoboda J., Guainazzi M., Merloni A., 2017, Astronomy & Astrophysics, 603, A127
  * Wolf et al. (2024) Wolf C., Lai S., Onken C. A., Amrutha N., Bian F., Hon W. J., Tisserand P., Webster R. L., 2024, Nature Astronomy, 2024
  * Yee (1980) Yee H. K. C., 1980, The Astrophysical Journal, 241, 894