# Weighing matrices and optical quantum computing

Steven T. Flammia1 and Simone Severini2 1Perimeter Institute for Theoretical
Physics, 31 Caroline St. N, Waterloo, Ontario, N2L 2Y5 Canada  2Institute for
Quantum Computing and Department of Combinatorics & Optimization, University
of Waterloo, 200 University Ave. W, Waterloo, Ontario, N2L 3G1 Canada
<EMAIL_ADDRESS><EMAIL_ADDRESS>,

###### Abstract

Quantum computation in the one-way model requires the preparation of certain
resource states known as cluster states. We describe how the construction of
continuous-variable cluster states for optical quantum computing relate to the
existence of certain families of matrices. The relevant matrices are known as
weighing matrices, with a few additional constraints. We prove some results
regarding the structure of these matrices, and their associated graphs.

###### pacs:

02.10.Ox, 03.67.Lx, 42.50.Ex

##  1 Introduction

In the standard model of quantum computing [1], the computation proceeds by
coherently performing unitary dynamics on a simple initial state of a quantum
system before being read out by a sequence of local measurements. By contrast,
the one-way model of quantum computing [2] eliminates the need for coherent
quantum evolution, substituting instead a highly entangled, but easily
prepared initial state as the resource for the computation. The typical
resource state used is the cluster state [3], whose preparation consists of,
for example, coupling a system of qubits with a nearest-neighbor Ising
interaction. The computation proceeds by a sequence of local measurements on
the cluster state and the basis chosen at each step determines the
computation. In this way, a cluster state is like a quantum breadboard on
which the quantum circuit is inscribed via measurements.

Although cluster states were originally defined using qubits, they generalize
to $d$-level quantum systems [4] and continuous variables [5, 6]. Recently,
Ref. [7] proposed a method for efficiently generating continuous-variable
cluster states (CVCS). The method relies on pumping an optical cavity
containing a special nonlinear medium at certain carefully chosen frequencies.
The resulting CVCS is encoded in the quadratures of the photons that emerge
from the cavity.

The method of CVCS generation proposed in [7] required, on grounds of
experimental and theoretical tractability, the existence of certain families
of matrices. The required matrices are weighing matrices, defined as matrices
$W$ whose entries are in $\\{0,\pm 1\\}$ and satisfy $WW^{T}=kI$, where $k$ is
called the _weight_. The weighing matrices were obliged to have _Hankel_ form,
meaning that the skew-diagonals of the matrix were all constant, and any skew-
diagonal with support on the main diagonal must be identically 0. A matrix
with vanishing main diagonal is said to be _hollow_. As we show later, when
viewing the matrices as adjacency matrices for an associated graph, this is
implied when the graph is connected and bipartite.

In this article, we investigate the mathematical structure behind the
construction in [7] and begin to classify the associated matrices. The
discussion is organized as follows. In section 2 we give a brief glimpse of
the physics which motivates the restrictions given in the previous paragraph.
We begin the mathematical discussion in section 3, where we discuss
anticirculant graphs, and section 4, where we discuss anticirculant weighing
matrices, a special case of the Hankel weighing matrices. In section 5, we
complete the rather trivial classification of the case of weight 2, while
section 6 provides several examples about the case of weight 4. We discuss a
number of open problems in section 7, and conclude in section 8.

##  2 Quantum computing in the frequency comb

In this section we outline the physics that naturally leads us to consider
Hankel hollow weighing matrices. For a more detailed discussion of the
physics, see [7, 8, 9, 10].

The resonant frequencies of an optical cavity are defined classically as the
modes which constructively interfere inside the cavity. Because they are
evenly spaced, they form a so-called a frequency comb. By placing a nonlinear
medium inside the cavity, pump photons with frequency $\omega_{p}$ can
downconvert into an entangled pair of photons, so long as the new photons’
frequencies satisfy an energy conservation constraint,

$\omega_{p}=\omega_{m}+\omega_{n}\,,$ (1)

where $\omega_{m}$ and $\omega_{n}$ are the $m^{\rm th}$ and $n^{\rm th}$
resonant frequencies of the cavity. The range over which the downconversion
can occur is limited by the phasematching bandwidth of the cavity.

More generally, multiple frequencies can be simultaneously phasematched inside
the cavity, and upconversion is allowed as well as downconversion. The total
Hamiltonian is then idealized by the following

$\mathcal{H}=i\hbar\kappa\sum_{p\in P}\
\sum_{m+n=p}\\!M_{mn}(\hat{a}^{\dagger}_{m}\hat{a}^{\dagger}_{n}-\hat{a}^{\phantom{{\dagger}}}_{m}\hat{a}^{\phantom{{\dagger}}}_{n}),$
(2)

where $P$ is the (discrete) spectrum of the polychromatic pump, $\kappa$ is a
global coupling strength, $\hat{a}^{\dagger}_{n}$ is the creation operator for
the $n^{\rm th}$ mode, and $M_{mn}$ are matrix elements of a symmetric matrix.
In units of the fundamental frequency of the cavity, the restriction of the
inner sum to terms with $m+n=p$ enforces photon energy conservation, and the
magnitude of $M_{mn}$ determines the strength of the coupling in units of
$\hbar\kappa$, while the sign determines whether the photons are upconverted
or downconverted. If all of the coupling strengths are equal, then $M$ is a
Hankel matrix whose elements are either $0$ or $\pm c$, where $c$ is a
constant. Experimental simplicity further demands that there is no single-mode
squeezing and hence we require that the elements along the main diagonal of
$M$ are all zero, i.e. $M$ must be a hollow matrix.

The Hamiltonian (2) can be used to create continuous-variable cluster states,
defined as Gaussian states satisfying the relation

$\mathbf{p}-A\mathbf{q}\rightarrow\mathbf{0}\;,$ (3)

where $\mathbf{p}$ and $\mathbf{q}$ are vectors of amplitude and phase
quadratures for the $k^{\rm th}$ cavity mode,
$q_{k}=\hat{a}^{\dagger}_{k}+\hat{a}^{\phantom{{\dagger}}}_{k}$ and
$p_{k}=i(\hat{a}_{k}^{\dagger}-\hat{a}^{\phantom{{\dagger}}}_{k})$, $A$ is the
symmetric weighted adjacency matrix of the graph of the CVCS, and the arrow
denotes the limit of large squeezing. Reference [8] first proved a nonunique
relationship between the adjacency matrix $A$, which describes the cluster
state, and the adjacency matrix $M$, which describes the coupling between the
modes inside the cavity. The general relationship is somewhat complicated, so
references [9, 7, 10] introduced the simplifying ansatz that

$AA^{T}=A^{2}=1,$ (4)

from which it follows [9, 10] that (up to a trivial relabeling)

$M=A.$ (5)

In short, assuming $A$ is an orthogonal matrix implies the graph describing
the couplings between photons in the cavity ($M$) is _identical_ to the graph
describing the cluster state ($A$), which is a vast simplification over the
general relationship. The derivation requires that $M$ be the adjacency matrix
of a bipartite graph, but as we will see, one can derive this from the Hankel
and hollow constraints.

We now see how the twin demands of experimental and theoretical simplicity for
creating CVCS in an optical cavity naturally lead us to consider Hankel hollow
orthogonal matrices, all of whose non-zero elements are either $\pm c$, for
some constant $c$. We can of course consider renormalized matrices instead by
dividing out $c$, so that all entries are $\pm 1$; after finding these
renormalized matrices, we can then reintroduce the constant afterwards so that
(4) holds. Thus, we see that finding and classifying Hankel hollow weighing
matrices is our primary interest.

For completeness, we mention one further elaboration that is possible for this
scheme. If the photons’ polarization, transverse, or spatial degrees of
freedom are taken into account, then the Hamiltonian (2) can be modified by
adding additional indices for these modes. If these additional modes are all
frequency-degenerate, then an additional sum over these degenerate modes
appears in (2), which allows for the symmetric intercoupling between the
degenerate degrees of freedom. If such an interaction could be simultaneously
phasematched by the nonlinear medium inside the cavity, then one is naturally
lead to consider _block_ -Hankel matrices, where the size of the blocks is
equal to the number of degenerate degrees of freedom. We leave the
consideration of block-Hankel hollow weighing matrices to future work.

##  3 Anticirculant graphs

In this section we introduce the definition of anticirculant graphs and study
some of their first properties. For the sake of self-containedness, we will
define here all the graph-theoretic concepts we require. For further
background on theory of graphs the interested reader is referred to the book
by Diestel [11]. Our reference about permutations and finite groups is Cameron
[12].

We will work with simple graphs. A (simple) _graph_ $G=(V,E)$ is an ordered
pair of sets defined as follows: $V(G)$ is a non-empty set, whose elements are
called _vertices_ ; $E(G)$ is a non-empty set of unordered pairs of vertices,
whose elements are called _edges_. An edge of the form $\\{i,i\\}$ is called a
_loop_. Two vertices $i$ and $j$ are said to be _adjacent_ if $\\{i,j\\}\in
E(G)$. Often, this is simply denoted by writing $ij$. A graph is _loopless_ if
it is has no loops. The _adjacency matrix_ of a graph $G$ is denoted by $A(G)$
and defined by

$[A(G)]_{i,j}:=\left\\{\begin{tabular}[]{ll}$1,$&if $ij\in E(G);$\\\ $0,$&if
$ij\notin E(G).$\end{tabular}\right.$

An adjacency matrix of a loopless graph is said to be _hollow_. The _degree_
of a vertex $i$ in a graph $G$ is the number of edges incident with the
vertex, that is, $\\#\\{j:ij\in E(G)\\}$. A graph is _regular_ if each of its
vertices has the same degree. We say $d$_-regular_ to specify that each vertex
has degree $d$. A square matrix is _Hankel_ if it has constant skew-diagonals.
These are diagonals that traverse the matrix from North-East to South-West.
(For this reason, these are also called _antidiagonals_). Notice that an
$n\times n$ matrix has $2n-1$ skew-diagonals. An $n\times n$ Hankel matrix is
said to be _anticirculant_(or, equivalently, _skew-circulant_ or
_backcirculant_) if the $i$-th and $(i+n)$-th skew diagonals are equal. A
_permutation_ of _length_ $n$ is a bijection $\pi:[n]\longrightarrow[n]$,
where $[n]=\\{1,2,...,n\\}$. A _permutation matrix_ of _dimension_ $n$ is a
$n\times n$ matrix $P$ with the following two properties:
$[P]_{i,j}\in\\{0,1\\}$ for every $i,j$; $P$ has a unique $1$ in each row and
in each column. A permutation $\pi$ is said to _induce_ a permutation matrix
$P$ if $[P]_{i,\pi(i)}=1$ for every $i$.

Two graphs $G$ and $H$ are _isomorphic_ if there is a permutation matrix $P$
such that $A(G)=PA(H)P^{-1}$. We write $G\cong H$ to denote that graphs $G$
and $H$ are isomorphic. A graph $G$ is _bipartite_ if there is a permutation
matrix $P$ such that

$PA(G)P^{-1}=\left(\begin{array}[]{cc}0&M\\\ M^{T}&0\end{array}\right),$ (6)

for some matrix $M$. If $M=J_{n}$, where $J_{n}$ is the all-ones matrix of
size $n$, then $G\cong K_{n,n}$, the _complete bipartite graph_. A graph is
said to be _anticirculant_ if it is isomorphic to a graph whose adjacency
matrix is anticirculant. Let us denote by $\mathcal{L}_{n,d}$ and by
$\mathcal{L}_{n}$ the set of all $d$-regular anticirculant graphs on $n$
vertices and the set of anticirculant graphs on $n$ vertices, respectively.
Notice that $\\#\mathcal{L}_{n,d}={n\choose d}$. Therefore,

$\\#\mathcal{L}_{n}=\sum\nolimits_{d=1}^{n-1}\\#\mathcal{L}_{n,d}=\sum\nolimits_{d=1}^{n-1}{n\choose
d}=2^{n}-2.$

Given $G\in\mathcal{L}_{n}$, the ordered set $S(G)=(s:[A(G)]_{1,s}=1)$ is said
to be the _symbol_ of $G$, in analogy with the terminology used for circulant
graphs. Indeed, $S(G)$ specifies $G$ completely. In cycle notation, each
element $s\in S(G)$ is associated to a permutation of the form

$\pi_{s}=(1,s)(2,s-1)\cdots(s+1,n)(s+2,n-1)\cdots,$ (7)

where the subtraction is modulo $n$. In line notation,
$\pi_{s}=(s)(s-1)(s-2)\cdots(n)(n-1)\cdots(s+1)$. On the basis of the
definitions, we can collect the facts below:

###### Proposition 1

Let $G\in\mathcal{L}_{n}$ be a graph. The following statements hold true:

  1. 1.

The graph $G$ is $d$-regular with $d=\\#S(G)$.

  2. 2.

If $G$ is loopless then $n$ is even.

  3. 3.

If $G$ is loopless then each $s\in S(G)$ is even.

  4. 4.

The graph $G$ is bipartite.

Proof. In order:

  1. 1.

Let $\pi_{s}$ be the permutation associated to the element $s\in S(G)$. Then
$\pi_{s}$ induces a symmetric permutation matrix $P_{s}$. Since each $P_{s}$
is defined by $s$, we have $[P_{s}]_{i,j}=1$ if and only if $[P_{t}]_{i,j}=0$
for all $t\not=s$. Consequently, $A(G)=\sum_{s\in S(G)}P_{s}$, and $G$ is a
regular graph with degree $d=\\#S$.

  2. 2.

If the size of $P_{s}$ is odd, then $[P_{s}]_{i,i}=1$ for some $i$. This is
because $\pi_{s}$ is necessarily an involution of odd length, and for this
reason it has at least one fixed point. (Recall that an _involution_ is a
permutation that is its own inverse.)

  3. 3.

Suppose on the contrary that $s=2k+1$, for some $k\geq 1$. Then,
$[A(G)]_{1,s}=[A(G)]_{1,2k+1}=[A(G)]_{k+1,k+1}=1$, contradicting the
hypothesis of $G$ being loopless.

  4. 4.

By the form of each $\pi_{s}$ (see Eq. 7), it is sufficient to observe that
vertices labeled by odd numbers are adjacent only to vertices labeled by even
numbers and _viz_.

At this stage, we are ready to prove that the members of $\mathcal{L}_{n}$ are
Cayley graphs. The _Cayley graph_ $G=G(\Gamma,T)$ of a group $\Gamma$ _w.r.t._
the set $T\subseteq\Gamma$ is the graph in which $V(G)=\\{\Gamma\\}$ and
$\\{g,h\\}\in E(G)$, if there is $s\in T$ such that $gs=h$. The dihedral group
$D_{2k}$ of order $2k$ is the group of symmetries of a regular $k$-gon. The
dihedral group $D_{2k}$ is nonabelian and presented as

$D_{2k}=\langle s,t:t^{k}=e,s^{2}=e,sts=t^{-1}\rangle,$

where $t$ is a rotation and $s$ is a reflection. The elements of $D_{2k}$ are
$k$ rotations $t^{0},t,t^{2},...,t^{k-1}$ and $k$ reflections
$s,st,st^{2},...,st^{k-1}$. A graph $G$ is said to be _connected_ if there is
no permutation matrix $P$ such that $PA(G)P^{-1}=\bigoplus_{i}M_{i}$, for some
matrices $M_{i}$. If a Cayley graph of a group $\Gamma$ is not connected then
it is the disjoint union of isomorphic Cayley graphs of a subgroup of
$\Gamma$, with each isomorphic component corresponding to a coset of the
subgroup.

###### Proposition 2

Let $G$ be a loopless anticirculant graph. Then $G$ is a Cayley graph of the
dihedral group with respect to a set of reflections.

Proof. The adjacency matrix of a Cayley graph $G=G(\Gamma,T)$ can be written
as $A(G)=\sum_{t\in T}\rho_{\rm{reg}}(t)$, where $\rho_{\rm{reg}}$ is the
regular permutation representation of $\Gamma$. When the order of $\Gamma$ is
$n$, this is an homomorphism of the form
$\rho_{\rm{reg}}:\Gamma\longrightarrow\Sigma_{n}$, where $\Sigma_{n}$ is the
set of all $n\times n$ permutation matrices. Each $\rho_{\rm{reg}}(t)$
describes the action of the group element $t$ on the set $\\{1,2,...,n\\}$.
Let $G\in\mathcal{L}_{n}$ be a loopless graph. By Proposition 1, we need to
take $n=2k$. Let us label the lines (rows and columns) of $A(G)$ with the
group elements of $D_{n}$, of order $n=2k$, in the following order:

$\begin{tabular}[]{lllllllll}$t^{0}=e$&$s$&$t$&$st$&$t^{2}$&$st^{2}$&$\cdots$&$t^{k-1}$&$st^{k-1}$\end{tabular},$

where $e$ is the identity element of the group. Consider
$\rho_{\rm{reg}}(st^{l})$, where $1\leq l\leq k$. By applying the generating
relations of $D_{n}$, it is straighforward to verify that
$\rho_{\rm{reg}}(s)=P_{2}$, and $\rho_{\rm{reg}}(st^{l})=P_{2+2l}$, when
$1\leq l\leq k-1$. The elements of $S(G)$ are then associated to reflections
in $D_{2k}$:

$\begin{tabular}[]{lllll}$2\longrightarrow s$&$4\longrightarrow
st$&$6\longrightarrow st^{2}$&$\cdots$&$2k\longrightarrow
st^{k-1}$\end{tabular}.$

This concludes the proof of the proposition.

An example is useful to clarify this result. Let $\mathbb{Z}_{n}$ be the
additive group of integers modulo $n$. The Cayley graph
$X(\mathbb{Z}_{n},\\{1,n-1\\})$ is also called the $n$_-cycle_. This is the
unique connected $2$-regular graph up to isomorphism. Let
$G\in\mathcal{L}_{6,2}$ be the graph with adjacency matrix

$A(G)=\rho_{\rm{reg}}(s)+\rho_{\rm{reg}}(st)=\left(\begin{array}[]{cccccc}0&1&0&1&0&0\\\
1&0&1&0&0&0\\\ 0&1&0&0&0&1\\\ 1&0&0&0&1&0\\\ 0&0&0&1&0&1\\\
0&0&1&0&1&0\end{array}\right).$

where $s=(1,2)(3,6)(4,5)$ and $t=(1,4)(2,3)(5,6)$. Then $s^{2}=st^{2}=e$ and
$\langle s,st\rangle=D_{6}$. Additionally, it is immediate to see that $G\cong
X(\mathbb{Z}_{6},\\{1,5\\})$.

##  4 Anticirculant weighing matrices

In this section we will highlight the interplay between weighing matrices and
anticirculant graphs supporting orthogonal matrices.

A Weighing matrix $W$ of _order_ $n$ and _weight_ $k$, denoted by $W(n,k)$, is
a square $n\times n$ matrix with entries $[W]_{i,j}\in\\{-1,0,1\\}$,
satisfying $WW^{T}=kI$, where $I$ is the identity matrix. When $k=n$, then
$W(n,k)$ is said to be a _Hadamard matrix._ It is generally recognized that
weighing matrices were first discussed by Frank Yates in 1935 [13], while
Hadamard matrices were introduced by James Sylvester and Jacques Hadamard
during the second half of the nineteenth century (see [14]). Geramita and
Seberry [15], and Koukouvinos and Seberry [16] are general surveys on this
topic, as well as applications.

We are specifically interested in circulant weighing matrices. A _circulant
weighing matrix_ of order $n$ and weight $k$ is a $W(n,k)$ which is also a
circulant matrix. In analogy with the previous section, we define the ordered
set $T(W(n,k))=\\{s:[A(CW(n,k))]_{i,s}=1\\}$ to be the symbol of $CW(n,k)$.
Arasu and Seberry overview the subject in [17].

We shall give particular importance to graphs associated to weighing matrices.
The _graph of a_(real symmetric) _matrix_ $M$, denoted by $G(M)$, is the graph
defined by

$[A(G(M))]_{i,j}:=\left\\{\begin{tabular}[]{ll}$1,$&if $[M]_{i,j}\neq 0;$\\\
$0,$&if $[M]_{i,j}=0.$\end{tabular}\right.$

The graph $G(CW(n,k))$ is a Cayley graph of the cyclic group $\mathbb{Z}_{n}$
with respect to the set $T(W(n,k))$. For instance, let us look at the matrix

$CW(6,4)=\left(\begin{array}[]{rrrrrr}0&1&1&0&1&-1\\\ -1&0&1&1&0&1\\\
1&-1&0&1&1&0\\\ 0&1&-1&0&1&1\\\ 1&0&1&-1&0&1\\\
1&1&0&1&-1&0\end{array}\right)$ (8)

The graph $G(CW(6,4))$ is the Cayley graph of $\mathbb{Z}_{6}$ with respect to
the set $\\{1,2,4,5\\}$. This is illustrated in Figure 1.

Figure 1: The Cayley graph $X(\mathbb{Z}_{6},\\{1,2,4,5\\})$.

The following statement is one of the main tools in our discussion. For the
purposes of this paper, it is sufficient to focus on matrices of even order.

###### Proposition 3

For each circulant weighing matrix $M=CW(n,k)$ of order $n=2l$, with $l\geq
1$, there is a weighing matrix $U$ such that $G(U)\in\mathcal{L}_{n,k}$. The
graph $G(U)$ is loopless if each element of $T(W(n,k))$ is odd.

Proof. Consider the permutation

$\pi=\left(1,n\right),(2,n-1),...,(l,l+1)$ (9)

on a set $[n]$. Let $P_{\pi}$ be the permutation matrix induced by $\pi$.
Labeling the rows and the columns of $P_{\pi}$ with the elements of $[n]$ in
the lexicographic order, we can write

$P_{\pi}=\left(\begin{array}[]{cccc}0&\cdots&0&1\\\ \vdots&0&1&0\\\
0&&\ddots&\vdots\\\ 1&0&\cdots&0\end{array}\right).$

Now let $U=MP_{\pi}$. Since $P_{\pi}$ and $M$ are orthogonal matrices, $U$ is
also orthogonal. By the action of the permutation $\pi$ and the fact that $M$
is circulant, the graph $G(U)\in\mathcal{L}_{n,k}$ and
$S(G(U))=\\{s=n-[A(CW(n,k))]_{i,t}+1\\}$, where $t\in T(W(n,k))$. Notice that
$G(U)$ can have self-loops if we do not impose further restrictions. On the
other hand $G(U)$ is loopless if each $s\in S(G(U))$ is even (Proposition 1).
Such a property is satisfied only if each element of $T(W(n,k))$ is odd.

It is important to remark that $P_{\pi}$ acts on columns and hence it does not
generally preserve isomorphism of graphs. Proposition 3 prompts us to some
definitions. An _anticirculant weighing_ _matrix_ of order $n$ and weight $k$,
denoted by $AW(n,k)$, is a $W(n,k)$ which is also anticirculant. A matrix
$AW(n,k)$ is a special kind of Hankel weighing matrix. A _Hankel weighing_
_matrix_ of order $n$ and weight $k$, denoted by $M=HW(n,k)$, is a $W(n,k)$
such that $G(M)$ is anticirculant. While it is obvious that there exists an
$AW(n,k)$ if and only if there exists a $CW(n,k)$, we need to take into
account the following counterexample:

###### Proposition 4

Not every $HW(n,k)$ is an $AW(n,k)$.

Proof. Let $P_{\pi}$ be the permutation matrix as in the proof of Proposition
3. The matrix

$U=\left(\begin{array}[]{cc}P_{\pi}&P_{\pi}\\\
P_{\pi}&-P_{\pi}\end{array}\right)$ (10)

is a $HW(n,2)$, for every $n$, since

$UU^{T}=U^{2}=\left(\begin{array}[]{cc}2P_{\pi}^{2}&0\\\
0&2P_{\pi}^{2}\end{array}\right)=\left(\begin{array}[]{cc}2I&0\\\
0&2I\end{array}\right),$

because $P_{\pi}=P_{\pi}^{T}$.

Proposition 4 seems to indicate that classification theorems for circulant
weighing matrices help only partially when attempting to classify Hankel
weighing matrices.

In the next two sections, our classification begins by considering graphs of
small degree. This corresponds physically to the number of pump beams required
to build a given CVCS. If a graph is $r$-regular, it requires $2r-1$ different
pump beams to build the associated CVCS, since each of the $2r-1$ bands of the
adjacency matrix requires a different pump frequency. Thus, we are primarily
interested in graphs that have an interesting topology, but also have small
values of $r$, since greater values would have greater experimental
complexity. Cases of small $r$ are also more tractable theoretically, which is
another reason to focus on them.

##  5 2-regular graphs

The unique – up to isomorphism – connected $2$-regular graph on $n$ vertices
is the $n$_-cycle_ , $C_{n}$. A graph $G$ is said to be the _disjoint union_
of graphs $H_{1},...,H_{l}$ if there is a permutation matrix $P$ such that
$PA(G)P^{-1}=\bigoplus_{i=1}^{l}A(H_{i})$. In such a case, we write
$G\cong\biguplus\nolimits_{i=1}^{l}H_{i}$. Equivalently, let $G$ and $H$ be
graph such that $V(G)\cap V(H)=\emptyset$. The set of vertices of $G\uplus H$
is $V(G)\cup V(H)$ and the set of edges, $E(G)\cup E(G)$. All useful
information about graphs of matrices $HW(n,2)$ is stated as follows:

###### Proposition 5

Let $D_{n}$ be the dihedral group of order $n=2k$. Let
$T=\\{st^{i},st^{j}\\}\subset D_{n}$, where $1\leq i,j\leq k$, be a set of
reflections. There is a unitary matrix $U$ such that $X(D_{n},T)\cong G(U)$ if
and only if $(i-j)\bmod k=(j-i)\bmod k$. Moreover, if this is the case then
$k$ is even and therefore $n$ is a multiple of $4$. It follows that the graph
$G\in\mathcal{L}_{n,2}$ and $G$ is the disjoint union of $k/2$ copies of
$C_{4}$.

Proof. It is known that given a group $\Gamma$ and a set
$T=\\{g,h\\}\subset\Gamma$, there is a unitary matrix $U$ such that
$A(X(\Gamma,T))=A(G(U))$ if and only if $gh^{-1}=g^{-1}h$ (see, _e.g._ , [18,
19]). From this, $st^{i}(st^{j})^{-1}=(st^{i})^{-1}st^{j}$. Since $st^{l}$ is
a reflection, for every $1\leq l\leq k$, we can write $(st^{l})^{-1}=st^{l}$.
Thus $st^{i}st^{j}=st^{j}st^{i}$, that is, $st^{i}$ and $st^{j}$ commute.
Since $st^{l}s=t^{k-l}$, for every $1\leq l\leq k$, it follows that
$t^{(k-i+j)\bmod k}=t^{(k-j+i)\bmod k}$. This proves that $(i-j)\bmod
k=(j-i)\bmod k$, for $st^{i}$ and $st^{j}$. Now, without loss of generality,
assume that $j>i$. Note that $(i-j)\bmod k=k-j+i$. So, we need that
$j-i=k-j+i,$ which implies $j-i=k/2$. It follows that $U$ has the form
described in Eq. (10), up to isomorphism.

Figure 2 illustrates the graph $X(D_{8},\\{st,st^{3}\\})$ associated to the
matrix $HW(8,2)$. Since in general only a disjoint union of squares can be
achieved with 2-regular graphs, and these graphs have only limited interest
from a quantum computing perspective, we need to consider larger graphs. A
proposal for creating such graphs was given in Ref. [9].

Figure 2: The graph $X(D_{8},\\{st,st^{3}\\})\cong C_{4}\uplus C_{4}$.

##  6 4-regular graphs

In this section we consider several constructions of 4-regular graphs of
anticirculant weighing matrices. Unfortunately, we are unable to prove that
this set of examples is exhaustive, so a complete characterization of the
degree 4 case remains open.

The CVCS graphs in this section can all be implemented with an experimental
setup requiring no more than 7 pump beams.

###  6.1 Graphs from $AW(4,4)$

The matrix

$M_{4,4}=AW(4,4)=\left(\begin{array}[]{rrrr}1&1&1&-1\\\ 1&1&-1&1\\\
1&-1&1&1\\\ -1&1&1&1\end{array}\right)$

is a Hadamard matrix of order $4$. Since the entries of a Hadamard matrix are
all nonzero, $G(M_{4,4})\cong K_{4}^{+}$, where $K_{n}^{+}$ denotes the
complete graph on $n$ vertices with a self-loop at each vertex. We can
construct other anticirculant weighing matrices of higher order from
$M_{4,4}$. Given that we are interested in anticirculant matrices whose graph
is without self-loops, the first row of these matrices must have nonzero
entries only at even positions. Let $\mathcal{M}_{4,4}$ be a family of
matrices obtained from $M_{4,4}$ be adding new lines (_i.e._ , rows and
columns) between the rows and the columns of $M_{4,4}$. If we add the same
number of lines between each column (resp. row), we obtain matrices of order
$4k$, for $k\geq 1$. For small orders, the first rows of these matrices are

$\begin{tabular}[]{l}$0,1,0,1,0,1,0,-1$\\\ $0,0,1,0,0,1,0,0,1,0,0,-1$\\\
$0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,-1$\\\
$0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,-1$\end{tabular}.$

Clearly, for each matrix $M$ constructed in this way, we have $G(M)\in L_{n}$.
When $n=4k$, with $k$ odd, the graph $G(M)$ has self-loops. For this reason,
we consider only the case $n=4k$, with $k$ even. In other words, we consider
the case $n=8l$, for any $l\geq 1$. Let $S(M)=\\{s_{1},s_{2},s_{3},s_{4}\\}$.
By the above construction $s_{i+1}-s_{i}=d+1$ for $i=1,2,3$, and
$n-s_{4}+2s_{1}=s_{2}$. This last condition provides that the number of
columns between $s_{4}$ and $s_{1}$ is the same as one between $s_{2}$ and
$s_{1}$ when looking at the matrix as wrapped on a torus, by gluing together
the first and the last column. In this way, we can define a unitary matrix $U$
such that $G(U)\cong G(M)$. Let us denote by $U_{1},...,U_{n}$ the rows of
$U$. The nonzero entries in $U_{1}$ are exactly
$U_{1,s_{1}},U_{1,s_{2}},U_{1,s_{3}}$ and $U_{1,s_{4}}$. In particular,
$U_{1,s_{1}}=U_{1,s_{2}}=U_{1,s_{3}}=1$ and $U_{1,s_{4}}=-1$. Suppose
$s_{i+1}-s_{i}-1=d$ for all $i=1,2,3$ and $n-s_{4}+2s_{1}=s_{2}$. Thus the
inner product between the rows $U_{1}$ and $U_{s_{2}-s_{1}}$ is

$\displaystyle\langle U_{1},U_{s_{2}-s_{1}}\rangle$ $\displaystyle=$
$\displaystyle
U_{1,s_{1}}U_{l,s_{1}}+U_{1,s_{2}}U_{l,s_{2}}+U_{1,s_{3}}U_{l,s_{3}}+U_{1,s_{1}}U_{l,s_{4}}$
$\displaystyle=$ $\displaystyle
U_{1,s_{1}}U_{1,s_{2}}+U_{1,s_{2}}U_{1,s_{3}}+U_{1,s_{3}}U_{1,s_{4}}+U_{1,s_{4}}U_{1,s_{1}}$
$\displaystyle=$ $\displaystyle 1+1-1-1$ $\displaystyle=$ $\displaystyle 0.$

The _distance_ $d$ guarantees that each row (resp. column) of $U$ has exactly
$4$ nonzero entries contributing to the zero inner product with other $3$ rows
(resp. columns). Orthogonality is guaranteed since no nonzero entries
contribute to the inner product with all remaining rows (resp. columns). The
numbers $s_{1},...,s_{4}$ must be even and $d=(n-4)/4$ must be odd, since
$n=8l=\left(4d+4\right)$. The matrices of order $8l$ constructed in with this
method will be denoted by $M_{4,4,l}$. Essentially, orthogonality arises since
we _interlace_ $M_{4,4}$ with itself $d+1$ times. This can be seen directly in
the matrix

$\displaystyle M_{4,4,1}=AW(8,4)=$
$\displaystyle\left(\begin{array}[]{rrrrrrrr}0&1&0&1&0&1&0&-1\\\
\framebox{$1$}&0&\framebox{$1$}&0&\framebox{$1$}&0&\framebox{$-1$}&0\\\
0&1&0&1&0&-1&0&1\\\
\framebox{$1$}&0&\framebox{$1$}&0&\framebox{$-1$}&0&\framebox{$1$}&0\\\
0&1&0&-1&0&1&0&1\\\
\framebox{$1$}&0&\framebox{$-1$}&0&\framebox{$1$}&0&\framebox{$1$}&0\\\
0&-1&0&1&0&1&0&1\\\
\framebox{$-1$}&0&\framebox{$1$}&0&\framebox{$1$}&0&\framebox{$1$}&0\end{array}\right),$
(19)

which is constructed by interlacing two copies of $M_{4,4}$. The boxed numbers
are the nonzero entries in one of the two copies. At this stage, we can ask
information about the graphs of matrices in $\mathcal{M}_{4,4}$. It is
sufficient to observe that $M_{4,4,l}=M_{4,4}\otimes F_{l+1}$, where the
matrix

$F_{n}=\left(\begin{array}[]{cccc}0&\cdots&0&1\\\ \vdots&&1&0\\\ 0&&&\vdots\\\
1&0&\cdots&0\end{array}\right),$

is $n\times n$. Note that this is just the matrix $P_{\pi}$ from Proposition
3, but we have changed notation to make the dependence on the size of the
matrix explicit. The matrix $F_{n}$ is the adjacency matrix of the disjoint
union of $n/2$ graphs $K_{2}$, if $n$ is even and the disjoin union of
$(n-1)/2$ graphs $K_{2}$ and a single vertex with a self-loop, if $n$ is odd.
The _tensor product_ $G\otimes H$ of graphs $G$ and $H$ is the graph such that
$A(G\otimes H)=A(G)\otimes A(H)$. The set of vertices of $G\otimes H$ is the
Cartesian product $V(G)\times V(H)$ and two vertices $\\{u,u^{\prime}\\}$ and
$\\{v,v^{\prime}\\}$ are adjacent in $G\otimes H$ if and only if $\\{u,v\\}\in
E(G)$ and $\\{u^{\prime},v^{\prime}\\}\in E(H)$. The graph $G\otimes H$ is
connected if and only if both factors are connected and at least one factor is
nonbipartite. Here, $K_{2}$ and $K_{4}$ are both connected and $K_{2}$ is
bipartite. When $l>1$, one of the factors is not connected. Therefore
$G(M_{4,4,l})$ is connected only if $l=1$. In fact
$G(M_{4,4,l})\cong\biguplus\nolimits_{\\#l}K_{4,4}$, where $K_{n,n}$ denotes
the complete bipartite graph on $2n$ vertices. In Figure 3 is illustrated
$G(M_{4,4,1})$; in Figure 4, $G(M_{4,4,4})$.

Figure 3: The graph $G(M_{4,4,1})\cong K_{4,4}$ Figure 4: The graph
$G(M_{4,4,4})\cong K_{4,4}\uplus K_{4,4}$.

The graph $G(M_{4,4,l})$ is made of $l$ connected components. Can we find two
permutation matrices $P$ and $Q$ such that $G(PM_{4,4,l}Q)\ncong G(M_{4,4,l})$
and it is connected? In particular, for the moment, we consider only
permutation matrices that preserves the distance $d$ between the elements of
$S(M)$. From $M_{4,4,l}$, we can construct exactly $l-1$ further matrices, by
permutation the lines under this constraint. For example, when $n=24=8\cdot
3$, the possible first rows are

$\begin{tabular}[]{l}$0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,-1$\\\
$0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,-1,0,0$\\\
$0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,-1,0,0,0,0$\end{tabular}.$

The position of the entry $-1$ does not matter, because we are interested in
the graph $G(M_{4,4,l})$. Given $s_{1},...,s_{4}$, in matrices of the form
$M_{4,4,l}$, when $l>1$,

$\gcd(\\{s_{i}-s_{j}:\mbox{for all }i,j\mbox{ such that }j>i\\}\cup 8l)>2.$

This implies that $G(PM_{4,4,l}Q)\cong\biguplus\nolimits_{\\#l}K_{4,4}$, for
any two permutations $P$ and $Q$ preserving the distance $d$.

###  6.2 Graphs from $AW(6,4)$

It is natural to analyse the construction in the previous section, but
replacing the matrix $AW(4,4)$ with some other anticirculant weighing matrix.
Recalling that there is no $AW(5,4)$, the smallest available matrix of order
$n>4$ is $AW(6,4)$:

$M_{6,4}=AW(6,4)=\left(\begin{array}[]{rrrrrr}-1&1&0&1&1&0\\\ 1&0&1&1&0&-1\\\
0&1&1&0&-1&1\\\ 1&1&0&-1&1&0\\\ 1&0&-1&1&0&1\\\
0&-1&1&0&1&1\end{array}\right).$

This is obtained from the $CW(6,4)$ in (8). The graph $G(M_{6,4})$,
illustrated in Figure 5, has $4$ self-loops.

Figure 5: The graph $G(M_{6,4})$.

The graph $G(M_{6,4,l})$, if loopless, is on $12l$ vertices, with $l\geq 1$.
The graph $G(M_{6,4,1})\cong G(M_{6,4})\otimes K_{2}$ is connected since
$K_{2}$ and $G(M_{6,4})$ are connected and $G(M_{6,4})$ is nonbipartite. (The
chromatic number of $G(M_{6,4})$ is $3$.) A drawing of $G(M_{6,4,1})$ is in
Figure 6.

Figure 6: The graph $G(M_{6,4,1})\cong G(M_{6,4})\otimes K_{2}$.

In general, $M_{6,4,l}=M_{6,4}\otimes F_{l+1}$. If we avoid self-loops,

$G(M_{6,4,l})=\biguplus\nolimits_{l}G(M_{6,4,1}).$

By permuting the lines of $M_{6,4}$ (_shifting to the right_ the columns), we
have the matrix

$M_{6,4}^{1}=AW(4,4)_{1}=\left(\begin{array}[]{cccccc}0&-1&1&0&1&1\\\
-1&1&0&1&1&0\\\ 1&0&1&1&0&-1\\\ 0&1&1&0&-1&1\\\ 1&1&0&-1&1&0\\\
1&0&-1&1&0&1\end{array}\right).$

Apply our construction to $M_{6,4}^{1}$, we obtain graphs on $6k$ vertices,
with $k$ odd. However, since $G(M_{6,4,1})\cong G(M_{6,4,1}^{1})$, these
graphs will be a disjoint union of copies of $G(M_{6,4,1})$. So the
permutation is of no use if our intention is to get different graphs from
$M_{6,4}$. On the other side, the structure of $M_{6,4}^{1}$ suggests a
different construction, which will allow us to obtain matrices of the form
$AW(4m,4)$, whose graph is loopless and connected for every $m\geq 3$. Notice
that

$M_{6,4}=\left(\begin{array}[]{cc}A&B\\\ B&A\end{array}\right),$

where

$A=\left(\begin{array}[]{rrr}0&-1&1\\\ -1&1&0\\\ 1&0&1\end{array}\right)$ |  | $B=\left(\begin{array}[]{rrr}0&1&1\\\ 1&1&0\\\ 1&0&-1\end{array}\right).$
---|---|---

Then $2AB=0$ and $A^{2}+B^{2}=4I$ and indeed

$M_{6,4}M_{6,4}=\left(M_{6,4}\right)^{2}=\left(\begin{array}[]{cc}A^{2}+B^{2}&2AB\\\
2AB&A^{2}+B^{2}\end{array}\right)=4I.$

We can add an even number of extra lines to $M_{6,4}$ and still preserve its
block structure. For example, the matrices

$A^{\prime}=\left(\begin{array}[]{rrrrrr}0&-1&0&1&0&0\\\ -1&0&1&0&0&0\\\
0&1&0&0&0&1\\\ 1&0&0&0&1&0\\\ 0&0&0&1&0&1\\\ 0&0&1&0&1&0\end{array}\right)\ ,\
B^{\prime}=\left(\begin{array}[]{cccccc}0&1&0&1&0&0\\\ 1&0&1&0&0&0\\\
0&1&0&0&0&-1\\\ 1&0&0&0&-1&0\\\ 0&0&0&-1&0&1\\\
0&0&-1&0&1&0\end{array}\right)$

satisfy the above conditions. Hence the matrix

$M_{12,4}=\left(\begin{array}[]{cc}A^{\prime}&B^{\prime}\\\
B^{\prime}&A^{\prime}\end{array}\right)$

is an $AW(12,4)$. In general, let $\mathcal{M}_{6,4}$ be the family of
matrices obtained with this construction. If $M\in\mathcal{M}_{6,4}$ then
$s_{1}=2$, $s_{2}=4$, $s_{3}=n/2+2$ and $s_{4}=n/2+4$, where
$S(M)=\\{s_{1},s_{2},s_{3},s_{4}\\}$. These are $AW(4k,4)$ when
$s_{3}-s_{2}=\left(n-6\right)/2$ is an odd number. The construction gives also
matrices of order $2l\geq 6$, for any $l$. Yet the associated graphs will have
loops when $l$ is odd. This is the reason for taking multiples of $4$. If
$M\in\mathcal{M}_{6,4}$ then $G(M)$ is connected, in virtue of the fact that
$s_{2}-s_{1}=4-2=2$ and then $\gcd(\\{s_{i}-s_{j}:$ for all $i,j$ such that
$j>i\\}\cup 4k\\}=2$.

The graphs of matrices in the set $\mathcal{M}_{6,4}$, with order $4m$, are
the direct product of $C_{2m}$ with the graph $K_{2}^{+}$. (Recall that
$K_{n}^{+}$ is the complete graph on $n$ vertices with self-loops; these are
the graphs with adjacency matrix $J_{n}$.) The _direct product_ $G\times H$ of
graphs $G$ and $H$ has set of vertices $V(G\times H)=V(G)\times V(H)$ and two
vertices $\\{u,u^{\prime}\\}$ and $\\{v,v^{\prime}\\}$ are adjacent in
$G\times H$ when $\\{u,v\\}\in E(G)$ and $\\{u^{\prime},v^{\prime}\\}\in
E(H)$. By the definition, $A(G\times H)=A(G)\otimes A(H)$. For this reason
$G\times H$ is sometimes called the _Kronecker product of graphs_ (see Imrich
and Klavžar [20], Ch. 5). If $G\in\mathcal{M}_{6,4}$ then $G\cong
K_{2}^{+}\times C_{2m}$ and $M(G)=J_{2}\otimes A(C_{2m})$.

###  6.3 Graphs from $AW(7,4)$

Let us consider the matrix

$M_{7,4}=AW(7,4)=\left(\begin{array}[]{rrrrrrr}0&1&0&1&1&-1&0\\\
1&0&1&1&-1&0&0\\\ 0&1&1&-1&0&0&1\\\ 1&1&-1&0&0&1&0\\\ 1&-1&0&0&1&0&1\\\
-1&0&0&1&0&1&1\\\ 0&0&1&0&1&1&-1\end{array}\right).$

The graph of $M_{7,4}$ is in Figure 7.

Figure 7: The graph $G(M_{7,4})$. Figure 8: The graph $G(M_{7,4,1})$.

Interlacing $M_{7,4}$ with itself, by the same method used for $M_{4,4}$ (see
section 6.1, Eq. (19)), we obtain the matrix

$M_{7,4,1}=AW(14,4)=AW(7,4)\otimes F_{2}$ (20)

The graph of $M_{7,4,1}$ is in Figure 8.

This is on $14$ vertices, $4$-regular and connected. At a first analysis,
$G(M_{7,4,1})$ does not seem to be a direct product of graphs. It is
nontrivial to extend $G(M_{7,4,1})$ to an infinite family of connected regular
graphs, as we did by taking $M_{6,4}$. Examples show that graphs obtained by
$M_{7,4}$ are not connected, but $G(M_{7,4,1})$.

##  7 Open problems

  * •

Study the structure of the graph $G(M_{7,4,1})$. Determine if it belongs to a
family of connected graphs arising from $AW(7,4)$, having an infinite number
of members, as it is for the graphs arising from $AW(6,4)$.

  * •

Since there is no general classification of weighing matrices, characterizing
graphs of Hankel weighing matrices seems to be out of reach. This could be
however done for graphs of degree $4$ and $9$, on the basis of present
knowledge on $CW(n,4)$ and $CW(n,9)$ (see [17]).

  * •

We have seen that there are examples of Hankel weighing matrices which are not
anticirculant. A way to study the relation between these matrices and
anticirculant ones, would be to prove that the graphs of Hankel weighing
matrices are always isomorphic to graphs of $AW(n,d)$, except for some special
cases which will include the examples in proposition 4.

Figure 9: Hamiltonian cycles in graphs of matrices $AW(12,4)$ and $AW(14,4)$.

  * •

A _Hamiltonian cycle_ in a graph is an ordered set of sequentially adjacent
vertices, in which every vertex of the graph appears exactly once. Graphs with
Hamiltonian cycles are said to be _Hamiltonian_. Alspach and Zhang [21]
conjectured that a connected Cayley graph $G(D_{n},T)$ is Hamiltonian whenever
$T$ is a set of reflections. According to this conjecture, any connected
anticirculant graph is Hamiltonian whenever it is loopless. Additionally,
Gutin _et al._ [22] conjectured that graphs of unitary matrices are
Hamiltonian if connected. According to these conjectures the graphs of Hankel
weighing matrices are Hamiltonian if connected. This is the case for the
graphs considered here. In Figure 9 are drawn the graphs $K_{2}^{+}\times
C_{8}$ and $G(M_{7,4,1})$. The highlighted edges represent Hamiltonian cycles.
Perhaps the physical picture that motivates our study could provide some
insight toward proving these conjectures.

  * •

We have seen that graphs of the form $K_{2}^{+}\times C_{2m}$ are graphs of
unitary matrices. The quantum dynamics induced by these matrices is trivial
because of symmetry. However symmetry can be broken with the action of a
diagonal matrix without altering the zero pattern of the unitary. This
suggests the possibility of constructing unitaries with a nontrivial dynamics
whose graph is a undirected Cayley graph of the dihedral group.

  * •

Sections 5 and 6 make extensive use of the following trick. Begin with a
circulant weighing matrix, then reverse the columns. If the resulting graph
has loops, one can create a loopless graph by the “interlacing” trick. In fact
the interlaced graph will again be connected if the original graph was
connected but not bipartite. Can one classify the Hankel and anticirculant
weighing matrices which cannot be obtained by this trick?

##  8 Conclusion

We have demonstrated connections between an approach to quantum computation
with optical modes and the existence of certain weighing matrices with Hankel
structure. Because the degree of the graph associated to a matrix corresponds
to the experimental resources required to implement the graph as a CVCS, it is
important to characterize which graphs with small degree have adjacency
matrices with Hankel structure. We proved some general theorems about such
matrices, classified completely the case of degree 2, and provided some
examples with degree 4. We also raised some interesting open problems that
might help shed some light on which graphs can be implemented in a single OPO
using the scheme in Ref. [7, 10].

## Acknowledgments

STF was supported by the Perimeter Institute for Theoretical Physics. Research
at Perimeter is supported by the Government of Canada through Industry Canada
and by the Province of Ontario through the Ministry of Research & Innovation.
SS was supported by the Institute for Quantum Computing. Research at the
Institute for Quantum Computing is supported by DTOARO, ORDCF, CFI, CIFAR, and
MITACS.

## References

## References

  * [1] M. A. Nielsen and I. L. Chuang.  Quantum Computation and Quantum Information.  Cambridge University Press, Cambridge, 2000.
  * [2] R. Raussendorf and H. J. Briegel.  A one-way quantum computer.  Phys. Rev. Lett., 86(22):5188–5191, 2001.
  * [3] H. J. Briegel and R. Raussendorf.  Persistent entanglement in arrays of interacting particles.  Phys. Rev. Lett., 86(5):910–913, Jan 2001.
  * [4] D. L. Zhou, B. Zeng, Z. Xu, and C. P. Sun.  Quantum computation based on d-level cluster states.  Phys. Rev. A, 68:062303, 2003.
  * [5] J. Zhang and S. L. Braunstein.  Continuous-variable gaussian analog of cluster states.  Phys. Rev. A, 73(3):32318, 2006.
  * [6] N. C. Menicucci, P. van Loock, M. Gu, C. Weedbrook, T. C. Ralph, and M. A. Nielsen.  Universal quantum computation with continuous-variable cluster states.  Phys. Rev. Lett., 97(11):110501, 2006.
  * [7] N. C. Menicucci, S. T. Flammia, and O. Pfister.  One-way quantum computing in the optical frequency comb.  Phys. Rev. Lett., 101:130501, 2008.
  * [8] N. C. Menicucci, S. T. Flammia, H. Zaidi, and O. Pfister.  Ultracompact generation of continuous-variable cluster states.  Phys. Rev. A, 76(1):010302, Jul 2007.
  * [9] H. Zaidi, N. C. Menicucci, S. T. Flammia, R. Bloomer, M. Pysher, and O. Pfister.  Entangling the optical frequency comb: simultaneous generation of multiple 2x2 and 2x3 continuous-variable cluster states in a single optical parametric oscillator.  Laser Phys., 18(5):659, May 2008.
  * [10] S. T. Flammia, N. C. Menicucci, and O. Pfister.  The optical frequency comb as a one-way quantum computer.  arXiv: 0811.2799 [quant-ph], 2008.
  * [11] R. Diestel.  Graph theory.  Graduate Texts in Mathematics. Springer-Verlag, New York, 2nd edition, 2000.
  * [12] P. J. Cameron.  Permutation groups.  Number 45 in London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 1999.
  * [13] F. Yates.  Complex experiments.  J. Roy. Statist. Soc. (Suppl)., 2:181–247, 1935.
  * [14] K. J. Horadam.  Hadamard matrices and their applications.  Princeton University Press, Princeton, NJ, 2007.
  * [15] A. V. Geramita and J. Seberry.  Orthogonal designs, Quadratic forms and Hadamard matrices.  Number 45 in Lecture Notes in Pure and Applied Mathematics. Marcel Dekker, Inc., New York, 1979.
  * [16] C. Koukouvinos and J. Seberry.  Weighing matrices and their applications.  J. Statist. Plann. Inference, 62(1):91–101, 1997.
  * [17] K. T. Arasu and J. Seberry.  On circulant weighing matrices.  Australas. J. Combin., 17:21–37, 1998.
  * [18] S. Severini.  On the digraph of a unitary matrix.  SIAM J. Matrix Anal. Appl. (SIMAX), 25(1):295–300, 2003.
  * [19] S. Severini.  Graphs of unitary matrices.  Ars Combin., 89, Oct 2008.
  * [20] W. Imrich and S. Klavžar.  Product graphs. Structure and recognition.  Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.
  * [21] B. Alspach and C.-Q. Zhang.  Hamilton cycles in cubic cayley graphs on dihedral groups.  Ars Combin., 28:101–108, 1989.
  * [22] G. Gutin, A. Rafiey, S. Severini, and A. Yeo.  Hamilton cycles in digraphs of unitary matrices.  Discrete Appl. Math., 173(1-3):67–78, 2006.


11institutetext: Department of Computer Science and Engineering,
National Institute of Technology, Silchar-788010, Assam, India
11email<EMAIL_ADDRESS>
11email<EMAIL_ADDRESS>
11email<EMAIL_ADDRESS>
# Beyond Information Exchange: An Approach to Deploy Network Properties for
Information Diffusion

Soumita Das  0000-0002-2412-9525 Anupam Biswas  0000-0003-0756-6026 Ravi
Kishore Devarapalli  0000-0001-5988-7476

###### Abstract

Information diffusion in Online Social Networks is a new and crucial problem
in social network analysis field and requires significant research attention.
Efficient diffusion of information are of critical importance in diverse
situations such as; pandemic prevention, advertising, marketing etc. Although
several mathematical models have been developed till date, but previous works
lacked systematic analysis and exploration of the influence of neighborhood
for information diffusion. In this paper, we have proposed Common Neighborhood
Strategy (CNS) algorithm for information diffusion that demonstrates the role
of common neighborhood in information propagation throughout the network. The
performance of CNS algorithm is evaluated on several real-world datasets in
terms of diffusion speed and diffusion outspread and compared with several
widely used information diffusion models. Empirical results show CNS algorithm
enables better information diffusion both in terms of diffusion speed and
diffusion outspread.

###### Keywords:

Information diffusion Common neighborhood Diffusion speed Diffusion outspread.

##  1 Introduction

Online Social Networks (OSNs) plays a key functional role in modern
information sharing. Hence, it is used extensively in information diffusion
research to examine real-world information diffusion process. As information
sharing in such networks occurs through social contacts, hence the underlying
network properties plays a significant role in information diffusion.
Recently, extensive research has been conducted to understand the role of
network properties on the dynamics of information diffusion in OSNs [1, 2, 3,
4]. In particular, the propagation of information across these OSNs provides
indications of diverse events and situational awareness, such as; marketing
prediction, social consciousness, terrorist activities [5]. It is important to
understand how the information will spread throughout the network in the
future. Hence, various information diffusion models have been developed to
understand the information diffusion behavior in real-world. The information
diffusion models are broadly classified into two categories: predictive models
and epidemic models. Predictive models considers the network structure to
analyze dispersion. For instance, popularity of a book among a population can
be predicted by using this model. Whereas, epidemic models considers influence
to model epidemiological processes. In particular, the spread of malware are
modelled by epidemic models. Several variants of predictive models and
epidemic models have been introduced till date. For example, Independent
Cascade (IC) Model, Linear Threshold (LT) model and Game Theory (GT) model are
sender-centric, receiver-centric and profit-centric based predictive models
respectively. Whereas, SI (Susceptible Infected) model, SIR (Susceptible
Infected Removed) model, SIS (Susceptible Infected Susceptible) model and SIRS
(Susceptible Infected Removed Susceptible) model are epidemic models [6, 7, 8,
9].

Overall, prior work on information diffusion research has either focused on
wideness of information diffusion i.e. total number of infected nodes in each
iteration or the efficiency of information diffusion i.e. total time required
to reach steady state. But the balance between these two important aspects has
been underexplored. A good understanding of the information diffusion
outspread is important in situations where information needs to be propagated
among a wider section of population. For example, Wider spread is required in
marketing a product. Whereas, diffusion speed is important in applications
where rate of information flow is to be prioritized. For instance, on election
day, a get-out-the-vote campaign is dependent on diffusion speed. In light of
these significant applications of information diffusion on real lives, we have
proposed CNS algorithm.

###  1.1 Basic Idea

In Online Social Networks (OSNs), individuals share hundreds or even thousands
of connections which associates the individuals to friends, colleagues, family
etc. However, all of these connections are not equally strong. Studies suggest
that strong connections reside within densely connected nodes [10, 1, 11, 12].
So, identification of these strong connections for information diffusion
facilitates initiating information exchange between strongly connected
individuals which also triggers exchange of information between the
corresponding densely connected neighbors. As information propagation in OSNs
expands through social contacts, thus exposure to these multiple sources
facilitates rapid diffusion of information throughout the social network. For
example, friendship relationship in OSNs may influence a group of users to
download an App or a software that is compatible to his/ her friends to stay
in touch. Therefore, investigating and deploying strong connections/
relationships for information diffusion between densely connected neighbors in
OSNs is important to analyze it’s effectiveness in information propagation
throughout the network.

###  1.2 Contributions

In this paper, a novel network property based information diffusion algorithm
has been presented. The contributions of this paper are as follows:

  * •

Utilization of network properties in the diffusion of information throughout
the network have been addressed. It demonstrates the importance common
neighborhood in information propagation.

  * •

Illustrates the efficiency of network properties in faster and wider
information propagation by evaluating and comparing the proposed algorithm
with several popular information diffusion models based on diffusion speed and
diffusion outspread.

##  2 Method

In this section, we have discussed about our proposed information diffusion
algorithm called, Common Neighborhood Strategy (CNS). Information diffusion in
social networks spreads through social contacts which indicates that the
underlying network structure plays a significant role in the information
diffusion pattern. We have considered network property namely, common
neighborhood to examine it’s effect on the dynamics of information diffusion.
Before proceeding further, let us first formalize some of the mostly used
terms. Suppose, we have a graph $G(V,E)$ where $V$ indicates set of nodes, $E$
indicates set of edges. For any connected node pair $(v,u)\in V$, an edge
$e_{v,u}$ indicates connection from node $v$ to node $u$, set of neighbors of
node $v$ is represented by $\Gamma(v)$.

###  2.1 Common Neighborhood

For a connected node pair say $(v,u)$, the common neighborhood $\rho_{v,u}$ is
defined in terms of neighbors between nodes $u$ and $v$. Higher common
neighborhood score indicates greater interaction frequency and hence, higher
similarity. Depending on the number of common neighbors shared by connected
node pairs, common neighborhood $\rho_{v,u}$ is computed by considering
following cases:

Case a. Nodes $v$ and $u$ do not share any common neighbor i.e.
$|\Gamma(v)\cap\Gamma(u)|=\phi$, then common neighborhood of connected node
pair $(v,u)$ is defined by,

$\rho_{v,u}=\left\\{\begin{matrix}1,&if~{}\mid\Gamma_{v}\mid~{}=1~{}or~{}\mid\Gamma_{u}\mid=1\\\
0,&if~{}\mid\Gamma_{v}\mid>1~{}or~{}\mid\Gamma_{u}\mid>1\end{matrix}\right.$
(1)

In equation 1, $\rho_{v,u}=1$ if either $\Gamma_{v}=1$ or $\Gamma_{u}=1$
because in this case, $v\leftrightarrow u$ is the only available path for
information exchange. Hence, this path will have maximum interaction frequency
for any kind of interaction between nodes $v$ and $u$.

Case b. Nodes $v$ and $u$ shares greater than or equal to one common neighbor
i.e. if $|\Gamma(v)\cap\Gamma(u)|>=1$, then common neighborhood of connected
node pair $(v,u)$ is defined by,

$\rho_{v,u}=|\Gamma(v)\cap\Gamma(u)|+|\Gamma(v)\cap\Gamma(z)|+|\Gamma(u)\cap\Gamma(z)|+|\sigma_{vu}|+|\Gamma(w)\cap\Gamma(z)|,~{}~{}\forall(w,z)\in(\Gamma(v)\cap\Gamma(u))~{}if~{}e_{w,z}\in
E,~{}w\neq z.$

(2)

There are five terms in Equation 2. First term
$\mid\Gamma(v)\cap\Gamma(u)\mid$ indicates number of common neighbors shared
by nodes $v$ and $u$, second term $\mid\Gamma(v)\cap\Gamma(z)\mid$ and third
term $\mid\Gamma(u)\cap\Gamma(z)\mid$ indicates number of common neighbors
shared by nodes $v$ and $u$ with common neighbor of $v$ and $u$ respectively,
forth term $\mid\sigma_{vu}\mid$ indicates number of connections shared by
common neighbors of $v$ and $u$, fifth term $\mid\Gamma(w)\cap\Gamma(z)\mid$
indicates number of common neighbors shared by common neighbors of $v$ and
$u$.

Neighborhood Density: For a connected node pair $(v,u)$, neighborhood density
is used to compute the density of it’s closely connected neighbors. This
density score is utilized to measure the tie strength of a connected node
pair. Greater tie strength score indicates higher proximity. For any connected
node pair $(v,u)$, neighborhood density/ tie strength is computed by using
common neighborhood $\rho_{v,u}$ and is defined by,

$\Phi_{v,u}=\frac{\rho_{v,u}}{max_{u\in\Gamma_{v}}\rho_{v,u}}$ (3)

In equation 3, the term in the denominator indicates maximum common
neighborhood score shared by $v$ with it’s neighboring node. The denominator
term makes tie strength $\Phi_{v,u}$ asymmetric. If $\Phi_{v,u}=1$, it
indicates that the tie strength shared by nodes $v$ and $u$ is maximum.
Whereas, if $\rho_{v,u}=0$, then $\Phi_{v,u}=0$, which means that if the
common neighborhood of a node pair is 0, then the tie strength is 0. In this
context, a tie between node pair $(v,u)$ is represented by edge $e_{v,u}\in E$
indicating connection from node $v$ to node $u$. $\mathscr{U}$ contains list
of edges in graph $G$ having maximum tie strength score.

###  2.2 Common Neighborhood Strategy

Here, we present the Common Neighborhood Strategy (CNS) algorithm. This
algorithm has been developed to investigate the effectiveness of common
neighborhood for information diffusion. The proposed CNS algorithm comprises
of three aspects. Let us consider that the diffusion process starts from a
node $v\in V$. The first aspect is to identify the adjacent node/ nodes of $v$
with which it shares maximum tie strength i.e. if $\Phi_{v,u}=1$, it indicates
that node $v$ shares maximum tie strength with node $u$. Then, information
diffusion is initiated from node $v$ to node $u$ and is defined by,

$\tau_{1}=\sum_{\begin{subarray}{c}u\in\Gamma(v),~{}e_{v,u}\in\mathscr{U}\end{subarray}}\phi_{v\rightarrow
u}$ (4)

Equation 4 indicates that node $v$ exchanges information with neighboring
node/ nodes, where $\Phi_{v,u}=1$, $\forall u\in\Gamma(v)$. Here,
$\phi_{v\rightarrow u}$ indicates that information exchange takes place from
node $v$ to node $u$. After identification of node $u$, which shares maximum
tie strength with $v$, the second aspect is to exchange information with nodes
contributing in the common neighborhood $\rho_{v,u}$ of connected node pair
$(v,u)$. Let us assume that $\mathscr{F}$ contains list of nodes contributing
in the common neighborhood of node pair $(v,u)$. Then, the second aspect is
defined by,

$\tau_{2}=\sum_{\begin{subarray}{c}i,j\in\mathscr{F},~{}i,j\in V,\\\
i\in\Gamma(v),j\in\Gamma(u)\end{subarray}}(\phi_{v\rightarrow
i}+\phi_{u\rightarrow j})$ (5)

Nodes $v$ and $u$ exchanges information with it’s neighbors which contributes
in the common neighborhood of connected node pair $(v,u)$ and is indicated by
terms $\phi_{v\rightarrow i}$ and $\phi_{u\rightarrow j}$ respectively in
equation 5. Then, the third aspect is to identify those neighboring nodes of
$v$ which have not yet participated in the information diffusion process and
which shares maximum tie strength with $v$ i.e. $e_{v,z}\notin\mathscr{U}$ but
$e_{z,v}\in\mathscr{U}$ where $z\in\Gamma(v)$ and is defined by,

$\tau_{3}=\phi_{v\rightarrow z},\forall z\in\Gamma(v),e_{z,v}\in\mathscr{U}$
(6)

Equation 6 indicates that node $z$ shares maximum tie strength score with node
$v$, if node $z$ have not participated in information exchange before, then
node $v$ exchanges information with node $z$. Ultimately, combination of the
first three aspects presented in equation 4, equation 5 and equation 6 gives
the information diffusion score adopted by CNS algorithm. Information
diffusion from node $v$ as defined by CNS algorithm is given by,

$\mathscr{I}_{v}=\tau_{1}+\tau_{2}+\tau_{3}$ (7)

Equation 7 indicates that information diffusion from node $v$ is a combination
of $\tau_{1},\tau_{2}$ and $\tau_{3}$. The proposed information diffusion
based CNS algorithm is designed considering common neighborhood concept. Step-
by-step illustration of the diffusion process of CNS algorithm is presented in
Fig. 1. Let us assume that node 2 initiates the diffusion process. In Step 1,
node 2 identifies the adjacent edge having maximum tie strength score. Here,
node 2 shares maximum tie strength with node 1 indicated by blue arc in
subfigure (a). Then, in Step 2, node 2 activates node 1. In Step 3, all the
nodes contributing to the maximum tie strength score of node pair (2,1) are
targeted for activation. At the end of iteration one, nodes 1 and 9 identifies
the adjacent edges having maximum tie strength score i.e. arcs (1,5) and
(9,33) respectively. Thereafter, in iteration two and three all the steps
followed in iteration one are repeated for activating inactive neighbors and
ultimately, the diffusion pattern obtained by incorporation of CNS algorithm
is shown in subfigure (l) of 1 by peach arcs. Pseudocode of CNS method is
shown in Algorithm 1.

(a) Step 1: Iteration one

(b) Step 2: Iteration one

(c) Step 3: Iteration one

(d) Step 4: Iteration one

(e) Step 5: Iteration two

(f) Step 6: Iteration two

(g) Step 7: Iteration two

(h) Step 8: Iteration two

(i) Step 9: Iteration three

(j) Step 10: Iteration three

(k) Step 11: Iteration three

(l) Step 12: Iteration three

Figure 1: Demonstration of CNS algorithm using Karate network. Red colored
nodes indicate active nodes, while grey colored nodes indicate inactive nodes,
blue arcs refers to strong ties, red arcs represents connections where
activated nodes try to activate their inactive neighbors, peach arcs represent
edges propagated once and peach nodes indicate nodes already participated in
information diffusion.

0: Social Network, $G=(V,E)$

0: // List of activated nodes $\mathscr{A}$

1: CNS (G)

2: for each node $v$ in $G$ do

3: if $e_{v,u}$ in $\mathscr{U}$ then

4: // Compute Information Diffusion using equation (7)

5: end if

6: end for

7: return $\mathscr{A}$

Algorithm 1 CNS

##  3 Experimental Analysis

Evaluation of information diffusion result is necessary to determine the
performance of information diffusion models/ algorithms. In this section, we
brief the evaluation strategies such as, information diffusion models along
with their parameters, diffusion speed evaluation, diffusion outspread
evaluation and datasets. We have considered Independent Cascade (IC) model
with edge threshold set as 1 and Susceptible Infected (SI) model with
infection probability set as 0.50 for comparative analysis purpose. IC model
has been utilized to examine the role of tie strength in information diffusion
behavior. Next, SI model have been considered to investigate the role of
influence in information propagation in OSNs. These two models are selected
for comparative analysis because tie strength and influence are positively
correlated and hence, crucial for examining diffusion performance.

Table 1: Real-world datasets used in the experiments, $K$ indicates average degree. Name |  $\mid V\mid$ |  $\mid E\mid$ |  $K$ |  Network Description
---|---|---|---|---
Karate |  34 |  78 |  4.59 |  Zachary’s Karate Club[13]
Les Misérables |  77 |  254 |  6.60 |  Les Misérables network[14]
Jazz |  198 |  2742 |  27.70 |  Jazz musician network [15]
Polblogs |  1224 |  16718 |  27.31 |  Polblogs network [16]
KarateLes
MisérablesJazzPolblogs$0$$2$$4$$6$$8$$10$$3$$3$$4$$4$$3$$4$$5$$6$$5$$5$$6$$10$Number
of IterationsCNSICSI Figure 2:  Number of iterations required by each of the
algorithms for information diffusion.

$1$$2$$3$$4$$5$$0.2$$0.4$$0.6$$0.8$$1$IterationsFraction of nodes
coveredKarateCNSICSI

$1$$2$$3$$4$$5$$0.2$$0.4$$0.6$$0.8$$1$IterationsFraction of nodes coveredLes
MisérablesCNSICSI

$1$$2$$3$$4$$5$$6$$0.2$$0.4$$0.6$$0.8$$1$IterationsFraction of nodes
coveredJazzCNSICSI

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0.2$$0.4$$0.6$$0.8$$1$IterationsFraction of
nodes coveredPolblogsCNSICSI

Figure 3: Fraction of nodes covered per iteration.

$1$$2$$3$$4$$5$$1$$2$$3$$4$$5$IterationsDiameterKarateCNSICSI

$1$$2$$3$$4$$5$$1$$2$$3$$4$$5$IterationsDiameterLes MisérablesCNSICSI

$1$$2$$3$$4$$5$$6$$1$$2$$3$$4$$5$IterationsDiameterJazzCNSICSI

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$1$$2$$3$$4$$5$$6$$7$$8$IterationsDiameterPolblogsCNSICSI

Figure 4:  Diameter of diffusion horizon per iteration.

$1$$2$$3$$4$$5$$1$$1.25$$1.5$$1.75$$2$$2.25$$2.5$IterationsAverage
DistanceKarateCNSICSI

$1$$2$$3$$4$$5$$1$$1.25$$1.5$$1.75$$2$$2.25$$2.5$$3$IterationsAverage
DistanceLes MisérablesCNSICSI

$1$$2$$3$$4$$5$$6$$1$$1.25$$1.5$$1.75$$2$$2.25$$2.5$IterationsAverage
DistanceJazzCNSICSI

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$1$$1.25$$1.5$$1.75$$2$$2.25$$2.5$$3$IterationsAverage
DistancePolblogsCNSICSI

Figure 5:  Average distance within diffusion horizon per iteration.

$1$$2$$3$$4$$5$$0.1$$0.15$$0.2$$0.25$$0.3$$0.35$$0.4$$0.45$$0.5$IterationsDensityKarateCNSICSI

$1$$2$$3$$4$$5$$0.1$$0.2$$0.3$$0.4$$0.5$$0.6$$0.7$$0.8$$0.9$$1$IterationsDensityLes
MisérablesCNSICSI

$1$$2$$3$$4$$5$$6$$0.1$$0.2$$0.3$$0.4$$0.5$$0.6$$0.7$$0.8$IterationsDensityJazzCNSICSI

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0.1$$0.2$$0.3$$0.4$$0.5$$0.6$$0.7$$0.8$$0.9$IterationsDensityPolblogsCNSICSI

Figure 6: Density within diffusion horizon per iteration.

The comparative analysis of representative diffusion models with CNS algorithm
is conducted considering diffusion speed and diffusion outspread. In this
context, diffusion speed refers to ‘how fast the dispersion occurs’. Whereas,
diffusion outspread indicates ‘how widely information propagates’. For
evaluation of diffusion speed, we have examined the number of iterations
required to reach steady state and fraction of nodes covered per iteration.
Furthermore, to evaluate diffusion outspread, we have utilized graph
properties such as, density, diameter, average distance, average degree.
Comparative graphical results based on diffusion speed and diffusion outspread
obtained by incorporation of CNS algorithm and representative information
diffusion models on real-world datasets such as Karate, Les Misérables, Jazz
and Polblogs obtained from SNAP [17] repository are presented in this section.
The details about these datasets are listed in Table 1. It is to be mentioned
here that all the results presented here by incorporation of CNS algorithm, IC
model and SI model assumes a common source/ infected node to initiate the
diffusion process to maintain uniformity of our analysis.

###  3.1 Result Analysis

The graphical results presented in Fig. 2 and Fig. 3 is related to diffusion
speed. Here, Fig. 2 refers to the total number of iterations taken to complete
diffusion process and Fig. 3 refers to the fraction of nodes covered in each
iteration. Less number of total iterations and maximum fraction of node
coverage per iteration is expected for faster diffusion. As can be seen from
Fig. 2, SI model takes maximum number of iterations to complete diffusion
process for all the representative datasets. Therefore, CNS algorithm is
definitely better than SI model. Next, we need to compare the performance of
CNS algorithm and IC model. From Fig. 2, it is observed that CNS algorithm and
IC model gives almost similar performance in terms of total number of
iterations in small dataset such as Karate, but the difference in their
performance can be identified in larger dataset as shown by Polblogs. As CNS
algorithm takes least number of iterations as compared to IC model in large
datasets, therefore it is inferred that CNS algorithm is better than IC model
in terms of total number of iterations taken to complete diffusion process.
Next, considering Fig. 3, the half lines indicate that the respective
information diffusion model/ algorithm completes in less number of iterations
as compared to the SI model for all the representative datasets. Clearly, SI
model covers least fraction of nodes per iteration. So, CNS algorithm is
certainly better than SI model in terms of fraction of nodes covered per
iteration. Additionally, it can be observed that CNS algorithm completes the
diffusion process in three to four iterations for all the datasets and it
covers maximum fraction of nodes in the first two iterations itself as
compared to IC model. In particular, if we consider Polblogs dataset, it is
clearly visible that CNS algorithm covers maximum fraction of nodes in the
first two iterations in comparison to IC model. As CNS algorithm gives best
performance in comparison to IC model and SI model based on total number of
iterations required to complete diffusion process and fraction of nodes
covered per iteration, therefore, CNS algorithm is better than representative
diffusion models in terms of diffusion speed.

We perform a comparative analysis of CNS algorithm and representative
information diffusion models in terms of diffusion horizon. In this context,
diffusion horizon refers to the area covered by the diffusion process and this
is measured per iteration. It is examined to determine the diffusion
outspread. The results shown in Fig. 4, Fig. 5, Fig. 6 and Fig. 7 is related
to diffusion horizon. Fig. 4 shows the diameter of diffusion horizon per
iteration. Higher diameter of diffusion horizon indicates maximum eccentricity
from all nodes and hence, larger diffusion outspread. First of all, it is
clearly visible from the subfigures of Fig. 4 that SI model gives least
diameter of diffusion horizon in all the iterations for all the representative
datasets. Therefore, CNS algorithm is certainly better than SI model in terms
of diameter of diffusion horizon per iteration. Next, comparing CNS algorithm
and IC model, both of these approaches gives almost similar performance for
small datasets. But if we consider large dataset such as Polblogs, it can be
seen that CNS algorithm gives maximum diameter of diffusion horizon per
iteration compared to IC model. Therefore, CNS algorithm is better than the
representative diffusion models in terms of diameter of diffusion horizon per
iteration. Next, Fig. 5 is used to evaluate average distance within diffusion
horizon. Higher average distance covered per iteration indicates larger
average shortest path distance and hence, wider diffusion outspread. Similar
to diameter of diffusion horizon results, the performance of SI model is poor
in terms of average distance within diffusion horizon. Whereas, comparison of
CNS algorithm and IC model indicates that CNS algorithm covers maximum average
distance in first two iterations as compared to IC model and it results in
faster diffusion speed also. Therefore, CNS algorithm excels in performance in
comparison to the representative diffusion models in terms of average distance
within diffusion horizon. Next, Fig. 6 represents the density within diffusion
horizon per iteration. Density is defined by $2m/n(n-1)$, where $m$ indicates
number of edges and $n$ indicates number of nodes. It is used to measure the
portion of potential connections in a network that are actual connections. It
is expected that density decreases with increase in number of iterations for
wider diffusion outspread because fraction of nodes covered in the initial
iterations is expected to be high. As fraction of nodes covered per iteration
is maximum for CNS algorithm, so the performance of CNS algorithm is best
compared to SI model and IC model in terms of density within diffusion
horizon. Fig. 7 indicates average degree of nodes within diffusion horizon per
iteration. The criteria for a faster and wider diffusion is to target the
maximum degree nodes first and hence, average degree is expected to rise and
then fall with increase in number of iterations. As can be seen from Fig. 7,
CNS algorithm gives maximum average degree in the first two iterations for all
the datasets compared to IC model and SI model which indicates best diffusion
outspread of CNS algorithm in terms of average degree of nodes within
diffusion horizon per iteration. Therefore, from these results, it is
concluded that CNS algorithm gives best performance than representative
diffusion models in terms of diffusion speed and diffusion outspread.

##  4 Conclusion

$1$$2$$3$$4$$5$$1$$2$$3$$4$$0$$5$IterationsAverage DegreeKarateCNSICSI

$1$$2$$3$$4$$5$$1$$2$$3$$4$$5$$6$$7$IterationsAverage DegreeLes
MisérablesCNSICSI

$1$$2$$3$$4$$5$$6$$10$$15$$20$$25$$30$$35$IterationsAverage DegreeJazzCNSICSI

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$10$$15$$20$$25$$30$$35$$40$$45$IterationsAverage
DegreePolblogsCNSICSI

Figure 7: Average degree of nodes within diffusion horizon per iteration.

In this paper, we developed a network property based information diffusion
algorithm called CNS considering both dense and sparse networks. It utilizes
common neighborhood information to compute tie strength score. It is based on
the concept that strong ties reside within densely connected nodes. Extensive
experiments on several real-world datasets show that CNS algorithm achieves
best diffusion speed and diffusion outspread among IC model and SI model.
Therefore, it is inferred that network property plays a significant role in
the dynamics of information diffusion. In future, we will deploy social
aspects in combination with network property aspects to design information
diffusion method and examine it’s significance.

## References

  * [1] J. Goldenberg, B. Libai, and E. Muller, “Talk of the network: A complex systems look at the underlying process of word-of-mouth,”Marketing letters, vol. 12, no. 3, pp. 211–223, Aug. 2001.
  * [2] D. J. Watts, “A simple model of global cascades on random networks,”in The Structure and Dynamics of Networks. Princeton University Press, 2011, pp. 497–502.
  * [3] A. Galstyan and P. Cohen, “Cascading dynamics in modular networks,”Physical Review E, vol. 75, no. 3, p. 036109, 2007.
  * [4] H. Peng, A. Nematzadeh, D. M. Romero, and E. Ferrara, “Network modularity controls the speed of information diffusion,”Physical Review E, vol. 102, no. 5, p. 052316, 2020.
  * [5] E. Bakshy, I. Rosenn, C. Marlow, and L. Adamic, “The role of social networks in information diffusion,” in Proceedings of the 21st international conference on World Wide Web, Lyon, France, Apr. 16–20, 2012, pp. 519–528.
  * [6] S. Das and A. Biswas, “Deployment of information diffusion for community detection in online social networks: A comprehensive review,”IEEE Transactions on Computational Social Systems, vol. 8, no. 5, pp. 1083–1107, 2021.
  * [7] M. Li, X. Wang, K. Gao, and S. Zhang, “A survey on information diffusion in online social networks: Models and methods,” Information, vol. 8, no. 4, p. 118, Sep. 29, 2017.
  * [8] Z. Chen and K. Taylor, “Modeling the spread of influence for in-dependent cascade diffusion process in social networks,” in 2017 IEEE 37th International Conference on Distributed Computing Systems Workshops (ICDCSW). Atlanta, GA, USA: IEEE, Jun. 5–8, 2017, pp.151–156.
  * [9] S. Bhattacharya and D. Sarkar, “Study on information diffusion in online social network,” in Proceedings of International Conference on Frontiers in Computing and Systems, Jalpaiguri Government Engineering College, West Bengal, India, Nov. 24, 2021, pp. 279–288.
  * [10] M. S. Granovetter, “The strength of weak ties,”American journal of sociology, vol. 78, no. 6, pp. 1360–1380, 1973.
  * [11] D. Centola and M. Macy, “Complex contagions and the weakness of long ties,”American journal of Sociology, vol. 113, no. 3, pp. 702–734,2007.
  * [12] J. P. Onnela, J. Saramäki, J. Hyvönen, G. Szabó, D. Lazer, K. Kaski,J. Kertész, and A.-L. Barabási, “Structure and tie strengths in mobile communication networks,”Proceedings of the national academy of sciences, vol. 104, no. 18, pp. 7332–7336, 2007.
  * [13] W. W. Zachary, “An information flow model for conflict and fission in small groups,”Journal of anthropological research, vol. 33, no. 4, pp.452–473, 1977.
  * [14] D. E. Knuth, “The stanford graph base: a platform for combinatorial algorithms,” in SODA, Austin Texas USA, Jan. 25–27, 1993, pp. 41–43.
  * [15] P. M. Gleiser and L. Danon, “Community structure in jazz,”Advances in complex systems, vol. 6, no. 04, pp. 565–573, 2003.
  * [16] L. A. Adamic and N. Glance, “The political blogosphere and the 2004us election: divided they blog,” in Proceedings of the 3rd international workshop on Link discovery, Chicago Illinois, Aug. 21–25, 2005, pp.36–43.
  * [17] SNAP Datasets: Stanford large network dataset collection,” http://snap.stanford.edu/data, Accessed October 21, 2021.