# The Dimension of the Moduli Space of Pointed Algebraic Curves of Low Genus

Jan Stevens  Department of Mathematical Sciences, Chalmers University of
Technology and University of Gothenburg. SE 412 96 Gothenburg, Sweden
<EMAIL_ADDRESS>
###### Abstract.

We explicitly compute the moduli space pointed algebraic curves with a given
numerical semigroup as Weierstrass semigroup for many cases of genus at most
seven and determine the dimension for all semigroups of genus seven.

###### Key words and phrases:

Weierstrass point; numerical semigroup; pointed curve; versal deformation

###### 2020 Mathematics Subject Classification:

14H55 14H45 14H10

## Introduction

On a smooth projective curve $C$ the pole orders of rational functions with
poles only at a given point $P$ form a numerical semigroup, the Weierstrass
semigroup. The space ${\mathcal{M}_{g,1}^{\Gamma}}$ parametrising pointed
smooth curves with Weierstrass semigroup at the marked point equal to $\Gamma$
is a locally closed subspace of the moduli space $\mathcal{M}_{g,1}$. In this
paper we compute the dimension of ${\mathcal{M}_{g,1}^{\Gamma}}$ for all
semigroups of genus at most seven.

By the famous result of Pinkham [21] the space ${\mathcal{M}_{g,1}^{\Gamma}}$
is closely related to the negative weight part of the versal deformation of
the monomial curve singularity $C_{\Gamma}$ with semigroup $\Gamma$. This
connection has been used in a series of papers by Nakano–Mori [18] and Nakano
[19, 20] to explicitly determine ${\mathcal{M}_{g,1}^{\Gamma}}$ for many
semigroups of genus at most six, using the Singular [6] package deform.lib
[17]. In all these cases ${\mathcal{M}_{g,1}^{\Gamma}}$ is irreducible and
rational. For the remaining cases (with two exceptions) irreduciblity and
stably rationality was shown by Bullock [2], with different methods.

We extend the computations of Nakano [19]. One quickly runs into the limits of
what can be computed in reasonable time. Therefore we also use other
approaches to compute deformations. One method is to use Hauser’s algorithm
[9]; the method of Contiero-Stöhr [3] to compute
${\mathcal{M}_{g,1}^{\Gamma}}$ is closely related. In this method one first
perturbs the equations in all possible ways, and takes care of flatness only
later. This means introducing may new variables, most of which can be
eliminated. In a number of cases this approach is succesful. In one case it is
more convenient to use the projection method developed by De Jong and Van
Straten [13], as applied to curves in [23].

We list the semigroups of genus at most 7 in Tables 1 and 2. For $g\leq 6$ we
follow the notation of [19]. The corresponding gap sequences are already
listed by Haure [8], in the first published paper containing the term
Weierstrass points. Haure also gives the number of moduli on which curves with
given Weierstrass semigroup depend. Our computations shows that his results
are correct except in one case. The non-emptiness of
${\mathcal{M}_{g,1}^{\Gamma}}$ for all semigroups with $g\leq 7$ was
established by Komeda [15].

Our tables also contain the structure of ${\mathcal{M}_{g,1}^{\Gamma}}$ in the
cases we have been able to determine it. In many cases, e.g. if the monomial
curve $C_{\Gamma}$ is a complete intersection, the space
${\mathcal{M}_{g,1}^{\Gamma}}$ is smooth. The next common case is that
${\mathcal{M}_{g,1}^{\Gamma}}$ is a weighted cone over the Segre embedding of
$\mathbb{P}^{1}\times\mathbb{P}^{3}$; the curve $C_{\Gamma}$ has then
codimension 3 and is given by 6 equations. For codimension 4 and 10 equations
the base space is typically given by 20 equations and the exact structure
depends on the curve. Except for the curve already studied in [23] these
equations are too complicated, with too many monomials, to be useful.

As to the dimension of ${\mathcal{M}_{g,1}^{\Gamma}}$, in general the
following bounds are known [22, 4]:

$2g-2+t-\dim\mathrm{T}^{1,+}\leq\dim{\mathcal{M}_{g,1}^{\Gamma}}\leq
2g-2+t\;.$

where $t$ is the rank of the highest syzygy module of the ideal of
$C_{\Gamma}$, and $\dim\mathrm{T}^{1,+}$ the number of deformations of
positive weight, both easily computable with Singular [6] or _Macaulay2_ [5].
The result of our computations is that for all semigroups with $g\leq 7$ the
dimension is given by the lower bound.

In the first section we recall the relation between the moduli space
${\mathcal{M}_{g,1}^{\Gamma}}$ and deformations of the monomial curve with
semigroup $\Gamma$. The next section describes the computation methods used in
this paper. The main part of the paper discusses the computation of the moduli
space or of its dimension for the different types of semigroup.

##  1\. The moduli space ${\mathcal{M}_{g,1}^{\Gamma}}$

Let $P$ be a smooth point on a possibly singular integral complete curve $C$
of arithmetic genus $g>1$, defined over an algebraically closed field
$\mathbf{k}$ of characteristic zero. An integer $n\in\mathbb{N}$ is a gap if
there does not exist rational function on $C$ with pole divisor $nP$, or
equivalently $H^{0}(C,\mathcal{O}_{C}(n-1)P))=H^{0}(C,\mathcal{O}_{C}(nP))$.
There are exactly $g$ gaps by the Weierstrass gap theorem, an easy consequence
of Riemann-Roch. The nongaps form a numerical semigroup $\Gamma$, the
Weierstrass semigroup of $C$ at $P$; this is the set of nonnegative integers
$n\in\mathbb{N}$ such that there is a rational function on $C$ with pole
divisor $nP$. For any numerical semigroup the genus is defined as the number
of gaps.

Given a numerical semigroup $\Gamma$ of genus $g>1$, let
${\mathcal{M}_{g,1}^{\Gamma}}$ be the space parameterising pointed smooth
curves with $\Gamma$ as Weierstrass semigroup at the marked point. It is a
locally closed subspace of the moduli space $\mathcal{M}_{g,1}$ of pointed
smooth curves of genus $g$. Note that ${\mathcal{M}_{g,1}^{\Gamma}}$ can be
empty.

The connection between the moduli space ${\mathcal{M}_{g,1}^{\Gamma}}$ and
deformations of negative weight of monomial curves was first observed by
Pinkham [21, Ch. 13]. Given a numerical semigroup $\Gamma=\langle
n_{1},\dots,n_{r}\rangle$ we form the semigroup ring
$\mathbf{k}[\Gamma]:=\oplus_{n\in\Gamma}\mathbf{k}\,t^{n}$ and denote by
$C_{\Gamma}:=\operatorname{Spec}\mathbf{k}[\Gamma]$ its associated affine
monomial curve. Consider the versal deformation of $C_{\Gamma}$

$\begin{matrix}\mathcal{X}_{t_{0}}\cong
C_{\Gamma}&\longrightarrow&\mathcal{X}\\\\[3.0pt]
\Big{\downarrow}&&\Big{\downarrow}\\\\[7.0pt]
\\{t_{0}\\}=\operatorname{Spec}\,\mathbf{k}&\longrightarrow&B\end{matrix}$

where $B=\operatorname{Spec}A$ is the spectrum of local, complete noetherian
$\mathbf{k}$-algebra. Pinkham [21] showed that the natural
$\mathbb{G}_{m}$-action on $C_{\Gamma}$ can be extended to the total and
parameter spaces. This induces a grading on the tangent space
$T^{1}_{C_{\Gamma}}$ to $B$. The convention here is that a deformation has
negative weight $-e$ if it decreases the weights of the equations of the curve
by $e$; the corresponding deformation variable has then (positive) weight $e$.
A numerical semigroup $\Gamma$ is called negatively graded if
$T^{1}_{C_{\Gamma}}$ has no positive graded part.

Let $B^{-}$ be the subspace of $B$ with negative weights. Then the restriction
$\mathcal{X}^{-}\to B^{-}$ is versal for deformations with good
$\mathbb{G}_{m}$-action . Both $\mathcal{X}^{-}$ and $B^{-}$ are defined by
polynomials and we use the same symbols for the corresponding affine
varieties. The deformation $\mathcal{X}^{-}\to B^{-}$ can be fiberwise
compactified to $\smash{\overline{\mathcal{X}}}^{-}\to B^{-}$; each fibre is
an integral curve in a weighted projective space with one point $P$ at
infinity and this is a point with semigroup $\Gamma$. All the fibres over a
given $\mathbb{G}_{m}$ orbit in $\mathcal{T}^{-}$ are isomorphic, and two
fibres are isomorphic if and only if they lie in the same orbit. This is
proved in [21] for smooth fibres and in general in the Appendix of [16].

Each pointed curve from ${\mathcal{M}_{g,1}^{\Gamma}}$ occurs as fibre by the
following construction. Consider the section ring
$\mathcal{R}=\oplus_{n=0}^{\infty}H^{0}(C,\mathcal{O}(nP))$. It gives an
embedding of $C=\operatorname{Proj}\mathcal{R}$ in a weighted projective
space, with coordinates $X_{0},\dots,X_{r}$ where $\deg X_{0}=1$. The space
$\operatorname{Spec}\mathcal{R}$ is the corresponding quasi-cone in affine
space. Setting $X_{0}=0$ defines the monomial curve $C_{\Gamma}$, all other
fibres are isomorphic to $C\setminus P$. In particular, if $C$ is smooth, this
construction defines a smoothing of $C_{\Gamma}$.

######  Theorem 1.1 ([21, Thm. 13.9]).

Let $\mathcal{X}^{-}\to B^{-}$ be the equivariant negative weight miniversal
deformation of the monomial curve $C_{\Gamma}$ for a given semigroup $\Gamma$
and denote by $B^{-}_{s}$ the open subset of $B^{-}$ given by the points with
smooth fibers. Then the moduli space ${\mathcal{M}_{g,1}^{\Gamma}}$ is
isomorphic to the quotient
${\mathcal{M}_{g,1}^{\Gamma}}=B^{-}_{s}/\mathbb{G}_{m}$ of $B^{-}_{s}$ by the
$\mathbb{G}_{m}$-action.

The closure of a component of $B^{-}_{s}$ is a smoothing component and is
itself contained in a smoothing component in $B$. For quasihomogeneous curve
singularities there is a simple formula for the dimension of smoothing
components: it is $\mu+t-1$ [7], with $\mu=2\delta-r+1$ the Milnor number and
$t=\dim_{\mathbf{k}}\operatorname{Ext}^{1}_{\mathcal{O}}(\mathbf{k},\mathcal{O})$
the type. For monomial curves $\delta=g$ and $r=1$, and the type can be
computed from the semigroup [1, 4.1.2] : $t=\lambda(\Gamma)$, the number of
gaps $\ell$ of $\Gamma$ such that $\ell+n\in\Gamma$ whenever $n$ is a nongap.
Given the equations of $C_{\Gamma}$ (anyway needed for deformation
computations) the type is easily found as the rank of the highest syzygy
module.

Let $\dim\mathrm{T}^{1,+}$ be the dimension of the space of infinitesimal
deformations of $C_{\Gamma}$ of positive weight. Then we have the following
bounds for the dimension of components of $M$ [4]; the upper bound is due to
Rim–Vitulli [22].

######  Theorem 1.2.

Let $\mathbb{N}$ be a numerical semigroup $\mathbb{N}$ of genus bigger than
$1$. If ${\mathcal{M}_{g,1}^{\Gamma}}$ is nonempty, then for any irreducible
component $E$ of ${\mathcal{M}_{g,1}^{\Gamma}}$

$2g-2+t-\dim\mathrm{T}^{1,+}\leq\dim E\leq 2g-2+t\;.$

##  2\. Computing deformation spaces in negative weight

By Pinkham’s theorem (Theorem 1.1), to explicitly describe the moduli space
${\mathcal{M}_{g,1}^{\Gamma}}$ one can compute the negative weight part of the
versal deformation of the monomial curve $C_{\Gamma}$. For many semigroups of
low genus this was done by Nakano-Mori [18] and Nakano [19, 20], using the
computer algebra system Singular [6]. The main obstacle in the remaining cases
is that the computations take too long, and result in long formulas without
apparent structure. In this section we describe several methods to determine
versal deformations, with comments on computational matters.

###  2.1. The standard approach

We recall the main steps, see also [24, Ch. 3]. Let $X$ be a variety with
$\mathbb{G}_{m}$-action with isolated singularity at the origin in
$\mathbb{A}^{n}$. Let $S=\mathbf{k}[X_{1},\dots,X_{n}]$ be the polynomial ring
in $n$ variables. Let $f=(f_{1},\dots,f_{r})$ generate the ideal $I(X)$ of
$X$. The first few terms of the resolution of $\mathbf{k}[X]=S/I(X)$ are

$0\longleftarrow\mathbf{k}[X]\longleftarrow
S\mathrel{\smash{\mathop{\longleftarrow}\limits^{f}}}S^{k}\mathrel{\smash{\mathop{\longleftarrow}\limits^{r}}}S^{l}\;$

where the columns of the matrix $r$ generate the module of relations. Let
$X_{B}\to B$ be a deformation of $X$ over $B=\operatorname{Spec}A$. The
flatness of the map $X_{B}\to B$ translates into the existence of a lifting of
the resolution to

$0\longleftarrow\mathbf{k}[X_{B}]\longleftarrow S\otimes
A\mathrel{\smash{\mathop{\longleftarrow}\limits^{F}}}(S\otimes
A)^{k}\mathrel{\smash{\mathop{\longleftarrow}\limits^{R}}}(S\otimes A)^{l}\;.$

To find the versal deformation we must find a lift $FR=0$ in the most general
way. The first step is to compute infinitesimal deformations. We write
$F=f+\varepsilon f^{\prime}$ and $R=r+\varepsilon r^{\prime}$. As
$\varepsilon^{2}=0$, the condition $FR=0$ gives

$FR=(f+\varepsilon f^{\prime})(r+\varepsilon
r^{\prime})=fr+\varepsilon(fr^{\prime}+f^{\prime}r)=0\;.$

Because $fr=0$, we obtain the equation $fr^{\prime}+f^{\prime}r=0$ in $S$. We
first solve the equation $f^{\prime}r=0$ or rather its transpose
$r^{t}(f^{\prime})^{t}=0$ in $\mathbf{k}[X]$. This means finding syzygies
between the columns of the matrix $r^{t}$; then we find $r^{\prime}$ by
lifting $f^{\prime}r$ with $f$. After this we lift order for order.
Obstructions to do this may come up, leading to equations in the deformation
parameters.

All these computations can be done with a computer algebra system. Indeed,
they are implemented implemented [11, 17] in _Macaulay2_ [5] and Singular [6].
The specific outcome of a computation, which depends on Groebner basis
calculations, is governed by the chosen monomial ordering and also by the
choice of the generators $(f_{1},\dots,f_{k})$ of the ideal $I(X)$. The
algorithm tries to find the row vector $F$, equations of the base space come
from obstructions to do that. Typically a computer computation will not choose
the easiest form of the base equations.

When restricting to deformations of negative weight all resulting equations
are polynomial and the computation is finite; it might be undoable in
practice, even with a powerful computer.

###  2.2. Hauser’s algorithm

An alternative method was developed in the complex analytic setting by Hauser
[9, 10]. One can see the method of Contiero-Stöhr [3] to compute a
compactification of the moduli space ${\mathcal{M}_{g,1}^{\Gamma}}$ as a
variant. It has been used in [4] to compute the base space for several
families of Gorenstein monomials curves. We start again from the generators
$f$ of the ideal $I(X)$, but now we perturb $f$ in the most general way,
modulo trivial perturbations, that is we take a semi-universal unfolding of
the associated map $f\colon\mathbb{A}^{n}\to\mathbb{A}^{k}$. Except when $X$
is zero dimensional, the base space of this unfolding will be infinite
dimensional; this problem is handled carefully by Hauser [10]. In our
situation $f$ is weighted homogeneous and we restrict ourselves to an
unfolding with terms of lower degree. Therefore we are back in a finite
dimensional situation, and we can work over any field $\mathbf{k}$. So we have
an unfolding $F\colon\mathbb{A}^{n}\times\mathbb{A}^{s}\to\mathbb{A}^{k}$ of
$f$. Now we determine the locus $B$ containing $0\in\mathbb{A}^{s}$ over which
$F$ is flat. The restriction of $F$ to $B$ is then the versal deformation of
$X$ of negative weight.

In our situation we have a monomial curve $X$ of multiplicity $m$ and
embedding dimension $e+1$. We take coordinates $x,y_{1},\dots,y_{e}$. An Apéry
basis of the semigroup leads to an additive realisation of $\mathbf{k}[X]$ as
$\sum_{i=0}^{m}y^{(i)}\mathbf{k}[x]$, where $y^{(0)}=1$, $y^{(1)}\dots
y^{(m-1)}$ are expressions in the variables $y_{1},\dots,y_{e}$. The equations
of $X$ are then (in multi-index notation) of the form $y^{\alpha}=\varphi$
with $\varphi\in\sum_{i=0}^{m}y^{(i)}\mathbf{k}[x]$. The unfolding is also
done only with terms from $\sum_{i=0}^{m}y^{(i)}\mathbf{k}[x]$. We start from
generators $f$ of the said form, compute the relation matrix $r$ and write the
unfolding $F$. We have to lift $fr=0$ to $FR=0$. To this end we compute $Fr$
and reduce this column vector to normal form with respect to the list $F$. It
is important that we do not compute a Groebner basis of the ideal generated by
$F$, as this will take too long. But reducing with respect to $F$ will result
in a vector with entries of bounded degree lying in
$\sum_{i=0}^{m}y^{(i)}R[x]$ with coefficients from
$R=\mathbf{k}[t_{1},\dots,t_{s}]$, where the $t_{j}$ are coordinates on the
base $\mathbb{A}^{s}$. The vanishing of these coefficients define the locus
where $FR=0$, so where $F$ is flat.

This procedure leads to a rather large number of relatively simple equations
in a large number of variables, most of which occur linearly and can be
eliminated. It is this process of elimination which can lead to few equations
in a limited number of variables, but with many monomials, see the proof of
Proposition 3.5 for an example.

Also here most computations are easily done with a computer algebra system.
The first step, to find the unfolding, can be automatised, but for the not too
complicated cases relevant for this paper it seems preferable to do it by
hand, choosing names for the deformation variables reflecting their weights.

###  2.3. The projection method

Computing deformations using projections onto a hypersurface is a method
developed in a series of papers by Theo de Jong and Duco van Straten, see [12,
13]. The application to curves is in [23], see also [24, Ch. 11]. Let again
$X$ be a monomial curve and $X\to Y$ a projection onto a plane curve, which is
a finite generically injective map. Let $\Sigma$ be the subspace of $Y$ by the
conductor ideal
$I={\operatorname{Hom}}_{Y}({\mathcal{O}}_{X},{\mathcal{O}}_{Y})$ in
${\mathcal{O}}_{Y}$. This makes it possible to reconstruct $X$, as
${\mathcal{O}}_{X}={\operatorname{Hom}}_{Y}(I,{\mathcal{O}}_{Y})$. Because we
use this method only once, we refer to [24, Chapter 11] for a description how
to use deformations the plane curve $Y$ together with $\Sigma$ to get
deformations of the original curve $X$.

The space $\Sigma$ is a fat point, so in particular Cohen-Macaulay of
codimension 2. Therefore the ideal $I$ defining $\Sigma$ in $\mathbb{A}^{2}$
is generated by the maximal minors ${\Delta_{1}}\dots\Delta_{k}$ of an
$k\times(k-1)$ matrix $M$. We write these generators as row vector $\Delta$.
The curve $Y$ is defined by a function of the form $f=\Delta\alpha$ with
$\alpha$ a column vector, or equivalently by the determinant of the matrix
$(M,\alpha)$. We write an element $n\colon\Delta_{i}\mapsto n_{i}$ of the
normal module $N:={\rm Hom}_{\Sigma}(I/I^{2},{\mathcal{O}}_{\Sigma})$ as row
vector $n$. A deformation $\Sigma_{B}\to Y_{B}$ comes from a deformation of
the curve $X$ if for every normal vector $n_{B}$ there exists a vector
$\gamma_{B}$ on the ambient space, satisfying

(1) $n_{B}\alpha_{B}+\Delta_{B}\gamma_{B}=0\;.$

This is the basic deformation equation, which can be solved step by step.

When restricting to deformations of negative weight the result of the
computation is again given by quasihomogeneous matrices with polynomial
entries. Once setup correctly the computation is easily done with a computer
algebra system.

An important concept here is that of $I^{2}$-equivalence [12, Def. 1.14]: two
functions $f$ and $g$ are $I^{2}$-equivalent, if and only if $f-g\in I^{2}$.
Suppose $f=\Delta\alpha$ and $g=\Delta\beta$ are $I^{2}$-equivalent. Then
$\alpha-\beta=A\Delta^{t}$ for some matrix $A$. Suppose
$n_{B}\alpha_{B}+\Delta_{B}\gamma_{B}$ is a lift of $n\alpha+\Delta\gamma$
over a base space $B$. Choose any lift $A_{B}$ of $A$. Then

(2)
$n_{B}(\alpha_{B}-A_{B}\Delta_{B}^{t})+\Delta_{B}(\gamma_{B}+A_{B}^{t}n_{B}^{t})$

is a lift of $n\beta+\Delta(\gamma+A^{t}n^{t})$. In particular, for curves
with projections defined by $I^{2}$-equivalent functions, the base spaces of
the versal deformation are the same up to a smooth factor.

##  3\. Semigroups of genus $g\leq 7$

In Tables 1 and 2 we list the semigroups of genus at most 7. For $g\leq 6$ we
follow the notation of [19]. The tables also contain also the dimension $d$ of
${\mathcal{M}_{g,1}^{\Gamma}}$ and the type $t$ of the semigroup. Furthermore
they give under the heading base the structure of
${\mathcal{M}_{g,1}^{\Gamma}}$ in the cases we have been able to determine it;
the entries indicating the different possibilities are discussed below.
Inspection of the tables shows that the main parameters governing the
structure of ${\mathcal{M}_{g,1}^{\Gamma}}$ are the number of generators of
$\Gamma$ and the type $t$. The first step in our computations is always to
find equations for the monomial curve $C_{\Gamma}$, followed by the free
resolution. This gives the type $t$. The next step is to find the graded parts
of the vector space $T^{1}$ of infinitisemal deformations.

######  Proposition 3.1.

For all semigroups with $g\leq 7$ the dimension of
${\mathcal{M}_{g,1}^{\Gamma}}$ is given by the lower bound
$2g-2+t-\dim\mathrm{T}^{1,+}$ of Theorem 1.2.

This result follows from the computations discussed in the rest of this
section.

[19] | semigroup | $d$ | $t$ | base | [19] | semigroup | $d$ | $t$ | base
---|---|---|---|---|---|---|---|---|---
$N(1)_{1}$ | 2,3 | 1 | 1 | sm | $N(6)_{1}$ | 2,13 | 11 | 1 | sm
$N(2)_{1}$ | 2,5 | 3 | 1 | sm | $N(6)_{2}$ | 3,10,11 | 12 | 2 | sm
$N(2)_{2}$ | 3,4,5 | 4 | 2 | sm | $N(6)_{3}$ | 3,8,13 | 11 | 2 | sm
$N(3)_{1}$ | 2,7 | 5 | 1 | sm | $N(6)_{4}$ | 3,7 | 10 | 1 | sm
$N(3)_{2}$ | 3,5,7 | 6 | 2 | sm | $N(6)_{5}$ | 4,9,10,11 | 13 | 3 | $B_{2}$
$N(3)_{3}$ | 3,4 | 5 | 1 | sm | $N(6)_{6}$ | 4,7,10,13 | 12 | 3 | $B_{1}$
$N(3)_{4}$ | 4,5,6,7 | 7 | 3 | $B_{1}$ | $N(6)_{7}$ | 4,7,9 | 11 | 2 | sm
$N(4)_{1}$ | 2,9 | 7 | 1 | sm | $N(6)_{8}$ | 4,6,11,13 | 11 | 3 | $B_{1}^{*}$
$N(4)_{2}$ | 3,7,8 | 8 | 2 | sm | $N(6)_{9}$ | 4,6,9 | 10 | 1 | sm
$N(4)_{3}$ | 3,5 | 7 | 1 | sm | $N(6)_{10}$ | 4,5 | 10 | 1 | sm
$N(4)_{4}$ | 4,6,7,9 | 9 | 3 | $B_{1}$ | $N(6)_{11}$ | 5,8,9,11,12 | 14 | 4 | ?
$N(4)_{5}$ | 4,5,7 | 8 | 2 | sm | $N(6)_{12}$ | 5,7,9,11,13 | 13 | 4 | !
$N(4)_{6}$ | 4,5,6 | 7 | 1 | sm | $N(6)_{13}$ | 5,7,8,11 | 12 | 3 | $B_{1}$
$N(4)_{7}$ | 5,6,7,8,9 | 10 | 4 | ! | $N(6)_{14}$ | 5,7,8,9 | 11 | 1 | sm
$N(5)_{1}$ | 2,11 | 9 | 1 | sm | $N(6)_{15}$ | 5,6,9,13 | 12 | 3 | $B_{1}$
$N(5)_{2}$ | 3,8,10 | 10 | 2 | sm | $N(6)_{16}$ | 5,6,8 | 11 | 2 | sm
$N(5)_{3}$ | $3,7,11$ | 9 | 1 | sm | $N(6)_{17}$ | 5,6,7 | 10 | 2 | sm
$N(5)_{4}$ | 4,7,9,10 | 11 | 3 | $B_{1}$ | $N(6)_{18}$ | 6,8,9,10,11,13 | 15 | 5 | ?
$N(5)_{5}$ | 4,6,9,11 | 10 | 3 | $B_{1}$ | $N(6)_{19}$ | 6,7,9,10,11 | 14 | 4 | ?
$N(5)_{6}$ | 4,6,7 | 9 | 1 | sm | $N(6)_{20}$ | 6,7,8,10,11 | 13 | 3 | $G^{\prime}$
$N(5)_{7}$ | 4,5,11 | 9 | 2 | sm | $N(6)_{21}$ | 6,7,8,9,11 | 12 | 2 | $G$
$N(5)_{8}$ | 5,7,8,9,11 | 12 | 4 | ? | $N(6)_{22}$ | 6,7,8,9,10 | 11 | 1 | $G$
$N(5)_{9}$ | 5,6,8,9 | 11 | 3 | $B_{1}$ | $N(6)_{23}$ | $7,\dots,13$ | 16 | 6 | ?
$N(5)_{10}$ | 5,6,7,9 | 10 | 2 | sm |  |  |  |  |
$N(5)_{11}$ | 5,6,7,8 | 9 | 1 | sm |  |  |  |  |
$N(5)_{12}$ | $6,\dots,\\!11$ | 13 | 5 | ? |  |  |  |  |
Table 1. semigroups of genus $\leq 6$

###  3.1. Smooth base space

The base space of the versal deformation of $C_{\Gamma}$ is smooth (indicated
with ‘sm’ in the tables) if the obstruction space $T^{2}$ vanishes. This
happens if the curve is a complete intersection, or Gorenstein of codimension
three, or Cohen-Macaulay of codimension two. In the latter case the equations
are the vanishing the minors of a $2\times 3$ matrix, and $t=2$. Also
$T^{2}=0$ for codimension 3 curves with $t=2$; two of these curves,
$N(7)_{31}$ and $N(7)_{32}$ are almost complete intersections.

name | semigroup | $d$ | $t$ | base | name | semigroup | $d$ | $t$ | base
---|---|---|---|---|---|---|---|---|---
$N(7)_{1}$ | 2,15 | 13 | 1 | sm | $N(7)_{21}$ | 5,6,9 | 12 | 2 | sm
$N(7)_{2}$ | 3,11,13 | 14 | 2 | sm | $N(7)_{22}$ | 6,9,10,11,13,14 | 17 | 5 | ?
$N(7)_{3}$ | 3,10,14 | 13 | 2 | sm | $N(7)_{23}$ | 6,8,10,11,13,15 | 16 | 5 | ?
$N(7)_{4}$ | 3,8 | 12 | 1 | sm | $N(7)_{24}$ | 6,8,9,11,13 | 15 | 4 | ?
$N(7)_{5}$ | 4,10,11,13 | 15 | 3 | $B_{2}$ | $N(7)_{25}$ | 6,8,9,10,13 | 14 | 2 | $G^{\prime}$
$N(7)_{6}$ | 4,9,11,14 | 14 | 3 | $B_{1}$ | $N(7)_{26}$ | 6,8,9,10,11 | 13 | 1 | $G$
$N(7)_{7}$ | 4,9,10,15 | 13 | 3 | $B_{1}$ | $N(7)_{27}$ | 6,7,10,11,15 | 15 | 4 | ?
$N(7)_{8}$ | 4,7,13 | 13 | 2 | sm | $N(7)_{28}$ | 6,7,9,11 | 14 | 3 | $B_{1}$
$N(7)_{9}$ | 4,7,10 | 12 | 1 | sm | $N(7)_{29}$ | 6,7,9,10 | 13 | 3 | $B_{1}$
$N(7)_{10}$ | 4,9,11,14 | 12 | 3 | $B_{1}^{*}$ | $N(7)_{30}$ | 6,7,8,11 | 13 | 3 | $B_{1}$
$N(7)_{11}$ | 4,6,11 | 10 | 1 | sm | $N(7)_{31}$ | 6,7,8,10 | 12 | 2 | sm
$N(7)_{12}$ | 5,9,11,12,13 | 16 | 4 | ? | $N(7)_{32}$ | 6,7,8,9 | 11 | 2 | sm
$N(7)_{13}$ | 5,8,11,12,14 | 15 | 4 | ? | $N(7)_{33}$ | $7,9,\dots,13,15$ | 18 | 6 | ?
$N(7)_{14}$ | 5,8,9,12 | 14 | 3 | $B_{1}$ | $N(7)_{34}$ | 7,8,10,11,12,13 | 17 | 5 | ?
$N(7)_{15}$ | 5,8,9,11 | 13 | 2 | sm | $N(7)_{35}$ | 7,8,9,11,12,13 | 16 | 4 | ?
$N(7)_{16}$ | 5,7,11,13 | 14 | 3 | $B_{1}$ | $N(7)_{36}$ | 7,8,9,10,12,13 | 15 | 3 | ?
$N(7)_{17}$ | 5,7,9,13 | 13 | 2 | sm | $N(7)_{37}$ | 7,8,9,10,11,13 | 14 | 2 | ?
$N(7)_{18}$ | 5,7,9,11 | 12 | 1 | sm | $N(7)_{38}$ | 7,8,9,10,11,12 | 13 | 1 | ?
$N(7)_{19}$ | 5,7,8 | 12 | 2 | sm | $N(7)_{39}$ | $8,\dots,15$ | 19 | 7 | ?
$N(7)_{20}$ | 5,6,13,14 | 13 | 3 | $B_{1}$ |  |  |  |  |
Table 2. semigroups of genus $7$

###  3.2. Cone over a Segre embedding

For codimension 3 curves $C_{\Gamma}$ with $t=3$ and $g\leq 7$ it is possible
to explicitly determine the structure of the base space. Most cases with
$g\leq 6$ were computed by Nakano [19].

The result for $N(6)_{6}=\langle 4,7,10,13\rangle$ was not given in [19]. We
computed the deformation using Bernd Martin’s Singular [6] package deform.lib
[17]. The equations for the curve are determinantal:

$\begin{bmatrix}x&y_{7}&y_{10}&y_{13}\\\
y_{7}&y_{10}&y_{13}&x^{4}\end{bmatrix}$

The speed of the computation in Singular depends very much on the chosen
ordering. A good choose is using the variables $(y_{13},y_{10},y_{7},x)$ in
this order with graded reverse lexicographic order, but with weights of the
variables all equal to 1, not using the weights $13,10,7,4$. Singular returns
an ideal $Js$ in 16 variables $A,\dots,P$ of weight $2$, $6$, $10$, $1$, $5$,
$9$, $13$, $8$, $12$, $16$, $7$, $10$, $4$, $1$, $4$, $7$. It is generated by
the minors of

(3) $\begin{bmatrix}N&-K+P\\\ O&C-L-BM+AM^{2}\\\
P&2G-2FM+2EM^{2}-2DM^{3}-M^{3}N\\\ C-BM+AM^{2}&-J+IM-
HM^{2}-M^{4}+M^{3}O\end{bmatrix}$

We are allowed to simplify the equations of the base space by a coordinate
transformation. An obvious transformation gives the matrix of the cone over
the Segre embedding of $\mathbb{P}^{1}\times\mathbb{P}^{3}$.

Observe that the coordinate ring of the Segre cone has a resolution of the
form

$0\longleftarrow S/I\longleftarrow
S\mathrel{\smash{\mathop{\longleftarrow}\limits^{f}}}S^{6}\mathrel{\smash{\mathop{\longleftarrow}\limits^{r}}}S^{8}\mathrel{\smash{\mathop{\longleftarrow}\limits^{s}}}S^{3}\longleftarrow
0$

where $f$ is the row vector of minors of the matrix

$\begin{bmatrix}X_{1}&X_{2}&X_{3}&X_{4}\\\
Y_{1}&Y_{2}&Y_{3}&Y_{4}\end{bmatrix}$

and the $8\times 3$ matrix $s$ is the transpose of a matrix of the form

$\begin{bmatrix}X_{1}&X_{2}&X_{3}&X_{4}&0&0&0&0\\\
Y_{1}&Y_{2}&Y_{3}&Y_{4}&X_{1}&X_{2}&X_{3}&X_{4}\\\
0&0&0&0&Y_{1}&Y_{2}&Y_{3}&Y_{4}\end{bmatrix}$

Computing the resolution of the ideal $Js$ with Singular gives indeed a
$8\times 3$ matrix with some zeroes, but of course not exactly in the form
above. This form can be achieved by column and row operations; in this way the
matrix (3) was found.

The Segre cone occurs for many curves as base space. A necessary condition is
that $\dim T^{2}=6$. For some curves $\dim T^{2}=12$. This happens for the
semigroups $\langle n_{1},n_{2},n_{3},n_{4}\rangle$ in the tables with
$n_{2}>2n_{1}$. Then the base space has a more complicated structure.

######  Proposition 3.2.

For monomial curve singularity of genus at most $7$ of codimension $3$, with
type $t=3$, such that the first blow up has lower embedding dimension, the
base space of negative weight is up to a smooth factor the cone over the Segre
embedding of $\mathbb{P}^{1}\times\mathbb{P}^{3}$, except in the cases
$N(6)_{8}$ and $N(7)_{10}$, where it has two components, being the
intersection of the Segre cone with coordinate hyperplanes ($B_{1}^{*}$ in
Tables 1 and 2).

###### Proof.

By the assumption in the statement $\dim T^{2}=6$. Most cases with $g\leq 6$
were computed by Nakano [19]. It can be checked that systems of generators
given in [19] are minors of $2\times 4$ matrices.

To identify the base space as Segre cone it in fact suffices to show that the
quadratic part of the equations defines a Segre cone. If it does, the Segre
cone has to be the tangent cone of the base space, for otherwise the dimension
of the tangent cone should be less than the dimension of the Segre cone, but
this dimension is in all cases equal to the lower bound of theorem 1.2.
Because the Segre cone is rigid and the base space itself is a deformation of
its tangent cone, they are isomorphic.

For the semigroups with $4$ generators and $t=3$ of genus $g=7$ (see Table 2)
the versal deformation up to degree 2 is easily computed with Singular, and
the cases where the base space is $B_{1}$ identified.

For $N(6)_{8}=\langle 4,6,11,13\rangle$ the versal deformation in all degrees
can be computed. The generators of the ideal of the curve are the $2\times 2$
minors of the symmetric matrix

$\begin{bmatrix}x&y_{6}&y_{11}\\\ y_{6}&x^{2}&y_{13}\\\
y_{11}&y_{13}&x^{3}y_{6}\end{bmatrix}$

With these generators and the graded reverse lexicographic order with
variables $(y_{13},y_{11},y_{6},x)$ of weights $(13,11,6,4)$ Singular succeeds
in computing rather quickly the versal deformation in all degrees. Replacing
the generator $y_{11}y_{13}-x^{3}y_{6}^{2}$ by $y_{11}y_{13}-x^{6}$ results in
a computation which does not finish in reasonable time. After a coordinate
transformation the base space is given by the minors of

$\begin{bmatrix}T_{-1}&T_{1}&T_{6}&T_{8}\\\
T_{9}&T_{11}&T_{16}&T_{18}\end{bmatrix}$

where the indices indicate the weight of the deformation variables. The base
space is again a Segre cone, but the base space in negative weight lies in the
hyperplane $T_{-1}=0$ and consists of two components, one smooth given by
$T_{1}=T_{6}=T_{8}=0$ and the other by $T_{9}=0$ and the vanishing of the
three minors of the matrix not involving $T_{9}$. Note that the last generator
of the ideal of the second component given in [19, p.159] can be expressed in
the previous ones.

For $N(7)_{10}=\langle 4,6,13,15\rangle$ the quadratic part of the equations
for the bases space are the minors of

$\begin{bmatrix}T_{-3}&T_{-1}&T_{6}&T_{8}\\\
T_{11}&T_{13}&T_{20}&T_{22}\end{bmatrix}$

and in negative weight there are two components of different dimension, given
by $T_{11}=T_{13}=T_{6}T_{22}-T_{8}T_{20}=0$ and $T_{6}=T_{8}=0$. Over the
largest component the equations of the total space can be written in rolling
factors format (see e.g. [24, p. 95]): three equations are the minors of the
matrix

$\begin{bmatrix}x&y_{6}+T_{2}x&y_{13}\\\
y_{6}&x^{2}+T_{4}x&y_{15}\end{bmatrix}$

while the fifth and sixth equations are obtained by replacing in each monomial
a factor occurring in the top row of the matrix by one of the bottom row. From
the equations in the matrix one finds that
$x(xy_{13}+T_{4}y_{13})=y_{6}(y_{15}+T_{2}y_{13})$, so $y_{15}+T_{2}y_{13}$
rolls to $xy_{13}+T_{4}y_{13}$. This gives:

$\displaystyle x^{2}y_{6}^{3}$ $\displaystyle-y_{13}^{2}$
$\displaystyle+P_{22}x+P_{20}y_{6}+T_{13}y_{13}+T_{11}y_{15}$ $\displaystyle
xy_{6}^{4}$ $\displaystyle-y_{13}y_{15}$ $\displaystyle+P_{22}y_{6}+\dots$
$\displaystyle y_{6}^{5}$ $\displaystyle-y_{15}^{2}$
$\displaystyle+P_{22}(x^{2}+T_{4}x-T_{2}y_{6})+\dots$

Here $P_{22}$ and $P_{20}$ are polynomials containing deformation variables of
degree $4,6,\dots,22$. It follows in particular that the origin is a singular
point of all fibres, in general an ordinary double point. Only the smallest
component is a smoothing component. ∎

######  Remark 3.3.

For $N(7)_{10}$ the gap sequence is $1,2,3,5,7,9,11$ and Haure [8] gives a
plane model of degree 13 with 11 moduli, whereas
$\dim{\mathcal{M}_{g,1}^{\Gamma}}=12$. This is the only case where Haure’s
result differs from our result.

###  3.3. Curves with first blow-up of multiplicity four

For the cases $N(6)_{5}=\langle 4,9,10,11\rangle$ and $N(6)_{5}=\langle
4,10,11,13\rangle$ the first blow-up is $N(3)_{4}=\langle 4,5,6,7\rangle$ and
$N(4)_{4}=\langle 4,6,7,9\rangle$ respectively. For the first curve we compute
the base space with Hauser’s algorithm; we do it in fact for all semigroups
$\langle 4,1+4\tau,2+4\tau,3+4\tau\rangle$. A similar, but more complicated
computation is in [4].

The equations of the curve are given by the minors of the matrix

$\begin{bmatrix}x^{\tau}&y_{1}&y_{2}&y_{3}\\\
y_{1}&y_{2}&y_{3}&x^{\tau+1}\end{bmatrix}$

We write the unfolding with variables which are polynomials in $x$, where
$f_{i}^{\scriptscriptstyle(j)}$ with $i\neq j$ has degree $4\tau+j$. We use
coordinate transformations to remove as many terms as possible. The result is

$\displaystyle y_{1}^{2}-y_{2}x^{\tau}$
$\displaystyle+f_{2}^{\scriptscriptstyle(1)}y_{1}+f_{2}^{\scriptscriptstyle(2)}+f_{2}^{\scriptscriptstyle(-1)}y_{3}+f_{2}^{\scriptscriptstyle(0)}y_{2}$
$\displaystyle y_{1}y_{2}-y_{3}x^{\tau}$
$\displaystyle+f_{3}^{\scriptscriptstyle(1)}y_{2}+f_{3}^{\scriptscriptstyle(2)}y_{1}+f_{3}^{\scriptscriptstyle(3)}+f_{3}^{\scriptscriptstyle(0)}y_{3}$
$\displaystyle y_{1}y_{3}-x^{2\tau+1}$
$\displaystyle+f_{4}^{\scriptscriptstyle(2)}y_{2}+f_{4}^{\scriptscriptstyle(3)}y_{1}+f_{4}^{\scriptscriptstyle(4)}$
$\displaystyle y_{2}^{2}-x^{2\tau+1}$
$\displaystyle+g_{4}^{\scriptscriptstyle(1)}y_{3}+g_{4}^{\scriptscriptstyle(2)}y_{2}+g_{4}^{\scriptscriptstyle(3)}y_{1}+g_{4}^{\scriptscriptstyle(4)}$
$\displaystyle y_{2}y_{3}-y_{1}x^{\tau+1}$
$\displaystyle+f_{5}^{\scriptscriptstyle(5)}+f_{5}^{\scriptscriptstyle(4)}y_{1}$
$\displaystyle y_{3}^{2}-y_{2}x^{\tau+1}$
$\displaystyle+f_{6}^{\scriptscriptstyle(5)}y_{1}+f_{6}^{\scriptscriptstyle(6)}+f_{6}^{\scriptscriptstyle(3)}y_{3}+f_{6}^{\scriptscriptstyle(4)}y_{2}$

We have four transformations left, which we cannot show in the above notation.
They act on the unfolding as $f_{3}^{\scriptscriptstyle(1)}-x^{\tau}a_{3,1}$,
$f_{2}^{\scriptscriptstyle(1)}-x^{\tau}a_{2,1}$,
$f_{4}^{\scriptscriptstyle(2)}+x^{\tau}a_{3,2}$ and
$f_{2}^{\scriptscriptstyle(0)}+\tau a_{0}x^{\tau-1}$; we use them to remove
the lowest weight variables from $f_{2}^{\scriptscriptstyle(0)}$,
$f_{2}^{\scriptscriptstyle(1)}$, $f_{3}^{\scriptscriptstyle(1)}$ and
$f_{4}^{\scriptscriptstyle(2)}$.

We proceed as explained in section 2.2: we compute the relation matrix for the
unperturbed generators of the ideal, multiply with the perturbed generators
and reduce the result with them. The result does not contain quadratic
monomials in the $y_{i}$ and for flatness it has to vanish identically, giving
conditions on the coefficients. We write these as equations for the
polynomials $f_{i}^{\scriptscriptstyle(j)}$, $g_{i}^{\scriptscriptstyle(j)}$.
The polynomials $f_{i}^{\scriptscriptstyle(i)}$ and
$g_{4}^{\scriptscriptstyle(4)}$ can be eliminated. We obtain fifteen
equations.

The first one is
$(x^{\tau}-f_{3}^{\scriptscriptstyle(0)})(f_{2}^{\scriptscriptstyle(1)}-f_{3}^{\scriptscriptstyle(1)})+(x^{\tau}-f_{2}^{\scriptscriptstyle(0)})g_{4}^{\scriptscriptstyle(1)}+f_{2}^{\scriptscriptstyle(-1)}f_{3}^{\scriptscriptstyle(2)}=0$.
We will use this equation to eliminate $g_{4}^{\scriptscriptstyle(1)}$. To
this end we rewrite it, and do the same with five other equations containing
$x^{\tau}-f_{2}^{\scriptscriptstyle(0)}$. We obtain

$(x^{\tau}-f_{2}^{\scriptscriptstyle(0)})(g_{4}^{\scriptscriptstyle(1)}+f_{2}^{\scriptscriptstyle(1)}-f_{3}^{\scriptscriptstyle(1)})={-(f_{2}^{\scriptscriptstyle(0)}-f_{3}^{\scriptscriptstyle(0)})(f_{2}^{\scriptscriptstyle(1)}-f_{3}^{\scriptscriptstyle(1)})-f_{2}^{\scriptscriptstyle(-1)}f_{3}^{\scriptscriptstyle(2)}}\\\
(x^{\tau}-f_{2}^{\scriptscriptstyle(0)})(f_{3}^{\scriptscriptstyle(2)}-g_{4}^{\scriptscriptstyle(2)})=-(f_{2}^{\scriptscriptstyle(1)}-f_{3}^{\scriptscriptstyle(1)})f_{3}^{\scriptscriptstyle(1)}-f_{2}^{\scriptscriptstyle(-1)}(f_{4}^{\scriptscriptstyle(3)}-f_{6}^{\scriptscriptstyle(3)})\\\
(x^{\tau}-f_{2}^{\scriptscriptstyle(0)})(g_{4}^{\scriptscriptstyle(3)}-f_{4}^{\scriptscriptstyle(3)}+f_{6}^{\scriptscriptstyle(3)})=(f_{2}^{\scriptscriptstyle(0)}-f_{3}^{\scriptscriptstyle(0)})(f_{4}^{\scriptscriptstyle(3)}-f_{6}^{\scriptscriptstyle(3)})-f_{3}^{\scriptscriptstyle(1)}f_{3}^{\scriptscriptstyle(2)}\\\
(x^{\tau}-f_{2}^{\scriptscriptstyle(0)})(f_{4}^{\scriptscriptstyle(3)}-xf_{2}^{\scriptscriptstyle(-1)})=(xf_{2}^{\scriptscriptstyle(0)}-f_{6}^{\scriptscriptstyle(4)})f_{2}^{\scriptscriptstyle(-1)}-(f_{2}^{\scriptscriptstyle(1)}-f_{3}^{\scriptscriptstyle(1)})f_{4}^{\scriptscriptstyle(2)}\\\
(x^{\tau}-f_{2}^{\scriptscriptstyle(0)})(f_{6}^{\scriptscriptstyle(4)}-f_{5}^{\scriptscriptstyle(4)}-xf_{2}^{\scriptscriptstyle(0)}+xf_{3}^{\scriptscriptstyle(0)})\\\
=f_{3}^{\scriptscriptstyle(2)}f_{4}^{\scriptscriptstyle(2)}+(f_{2}^{\scriptscriptstyle(0)}-f_{3}^{\scriptscriptstyle(0)})(xf_{2}^{\scriptscriptstyle(0)}-f_{6}^{\scriptscriptstyle(4)})\\\
(x^{\tau}-f_{2}^{\scriptscriptstyle(0)})(f_{6}^{\scriptscriptstyle(5)}+xf_{3}^{\scriptscriptstyle(1)})=-(xf_{2}^{\scriptscriptstyle(0)}-f_{6}^{\scriptscriptstyle(4)})f_{3}^{\scriptscriptstyle(1)}-f_{4}^{\scriptscriptstyle(2)}(f_{4}^{\scriptscriptstyle(3)}-f_{6}^{\scriptscriptstyle(3)})$

It can be checked that the remaining equations are consequences of these ones.
All the above equations are of the form

$L\cdot(x^{\tau}-f_{2}^{\scriptscriptstyle(0)})=R$

with $L$ and $R$ polynomials in $x$ satisfying $\deg_{x}(R)\leq\deg_{x}(L)+t$.
Division with remainder gives
$R=Q(x^{\tau}-f_{2}^{\scriptscriptstyle(0)})+\overline{R}$, and therefore we
can solve $L=Q$ and find the coefficients of $\overline{R}$ as equations for
the base space. In other words, the condition leading to the equations of the
base space is that the right hand side of the above equations is divisible by
$x^{\tau}-f_{2}^{\scriptscriptstyle(0)}$. A similar structure first appeared
for the base spaces of rational surface singularities of multiplicity four
[14].

The right hand side of the equations are the minors of the matrix

$\begin{bmatrix}-f_{2}^{\scriptscriptstyle(-1)}&(f_{2}^{\scriptscriptstyle(0)}-f_{3}^{\scriptscriptstyle(0)})&f_{3}^{\scriptscriptstyle(1)}&f_{4}^{\scriptscriptstyle(2)}\\\
(f_{2}^{\scriptscriptstyle(1)}-f_{3}^{\scriptscriptstyle(1)})&f_{3}^{\scriptscriptstyle(2)}&(f_{4}^{\scriptscriptstyle(3)}-f_{6}^{\scriptscriptstyle(3)})&-(xf_{2}^{\scriptscriptstyle(0)}-f_{6}^{\scriptscriptstyle(4)})\end{bmatrix}$

It seems that the eliminated variable $f_{4}^{\scriptscriptstyle(3)}$ occurs
in the matrix, but we can take
$f_{4}^{\scriptscriptstyle(3)}-f_{6}^{\scriptscriptstyle(3)}$ as independent
variable.

We make the divisibility conditions explicit for $\tau=1$ ($N(3)_{4})$) and
$\tau=2$ ($N(6)_{5}$). The $f_{i}^{\scriptscriptstyle(j)}$ are polynomials in
$x$, of the form
$f_{i}^{\scriptscriptstyle(j)}=f_{i,j+4\tau}+f_{i,j+4\tau-4}x+\dots+f_{i,r}x^{k}$
if $j+4\tau=4k+r$ with $1\leq r\leq 4$. Recall that we removed the variables
of lowest weight in $f_{2}^{\scriptscriptstyle(0)}$,
$f_{2}^{\scriptscriptstyle(1)}$, $f_{3}^{\scriptscriptstyle(1)}$ and
$f_{4}^{\scriptscriptstyle(2)}$.

For $\tau=1$ the matrix becomes

$\begin{bmatrix}-f_{2,3}&-f_{3,4}&f_{3,5}&f_{4,6}\\\
f_{2,5}-f_{3,5}&f_{3,6}+f_{3,2}x&f_{4,7}-f_{6,7}+(f_{4,3}-f_{6,3})x&f_{6,8}+f_{6,4}x\end{bmatrix}$

and the condition that the minors are divisible by $x$ is obviously that they
vanish when $x=0$ is substituted. Therefore the base space is given by the
vanishing of the minors of

$\begin{bmatrix}-f_{2,3}&-f_{3,4}&f_{3,5}&f_{4,6}\\\
f_{2,5}-f_{3,5}&f_{3,6}&-f_{6,4}f_{2,3}-f_{6,7}&f_{6,8}\end{bmatrix}$

where we substituted the value for $f_{4,7}$. Note that the variables
$f_{6,4}$, $f_{6,3}$ and $f_{3,2}$ do not occur in the equations. We recover
the result that the base space for $N(3)_{4}$ is the Segre cone.

For $\tau=2$ the last entry of matrix becomes
$f_{6,12}+f_{6,8}x+f_{6,4}x^{2}-f_{2,8}x$. We apply division with remainder by
$x^{2}-f_{2,8}$, leading to $f_{6,12}+f_{6,4}f_{2,8}+(f_{6,8}-f_{2,8})x$.
Doing the same for other entries we obtain the transpose of the matrix

$\begin{bmatrix}-f_{2,7}-f_{2,3}x&f_{2,9}-f_{3,9}+(f_{2,5}-f_{3,5})x\\\
f_{2,8}-f_{3,8}-f_{3,4}x&f_{3,10}+f_{3,2}f_{2,8}+f_{3,6}x\\\
f_{3,9}+f_{3,5}x&f_{4,11}-f_{6,11}+(f_{4,3}-f_{6,3})f_{2,8}+(f_{4,7}-f_{6,7})x\\\
f_{4,10}+f_{4,6}x&f_{6,12}+f_{6,4}f_{2,8}+(f_{6,8}-f_{2,8})x\end{bmatrix}$

Making a coordinate transformation and renaming the variables gives a matrix
of the form

$\begin{bmatrix}a_{7}+a_{3}x&a_{8}+a_{4}x&a_{9}+a_{5}x&a_{10}+a_{6}x\\\
b_{9}+b_{5}x&b_{10}+b_{6}x&b_{11}+b_{7}x&b_{12}+b_{8}x\end{bmatrix}$

Division with remainder and taking the $x$-coefficient leads to two equations
from each minor:

$\displaystyle a_{i+4}b_{j+2}+a_{i}b_{j+6}-a_{j+4}b_{i+2}+a_{j}b_{i+6}$
$\displaystyle
a_{i+4}b_{j+6}+a_{i}b_{j+2}f_{2,8}-a_{j+4}b_{i+6}-a_{j}b_{i+2}f_{2,8}$

For $N(7)_{5}$ a computation of the versal deformation up to order 3 allows to
recognise the base to be $B_{2}$ also in this case.

###  3.4. The cone over a Grassmannian

The semigroup $N(6)_{22}=\langle 6,7,8,9,10\rangle$ is the first of the second
family of curves studied in [4]. The computation can also easily be done with
Singular. The result is that the base space is the cone over the Grassmannian
$G(2,5)$. In Tables 1 and 2 this base space is denote by $G$. This shows that
$\mathcal{M}_{6,1}^{\scriptscriptstyle N(6)_{22}}$ is rational. Equations for
the base space can be recognised because they are the Pfaffians of a skew-
symmetric $5\times 5$ matrix, which is the relation matrix between the
equations. Again, a computer computation will in general not lead to a skew
matrix, but one can obtain that form by row and column operations.

The curve $N(7)_{26}=\langle 6,8,9,10,11\rangle$ is also Gorenstein and has as
base space a cone over $G(2,5)$. While $N(6)_{21}=\langle 6,7,8,9,11\rangle$,
which deforms into $N(6)_{22}$, is not Gorenstein, but has type $t=2$, the
dimension of $T^{2}$ is also five, and a computation with Singular shows that
the base space has the same structure: it is a cone over the Grassmannian.

###  3.5. A codimension four base space

For $N(6)_{20}=\langle 6,7,8,10,11\rangle$ ($t=3$) and $N(7)_{25}=\langle
6,8,9,10,13\rangle$ ($t=2$) one has $\dim T^{2}=9$. We compute the base spaces
with Hauser’s algorithm. It turns out that they have the same structure,
called $G^{\prime}$ in the tables. We give here the details for the first
curve. An additive basis over $\mathbf{k}[x]$ of the coordinate ring is
$(1,y_{7},y_{8},y_{10},y_{11},y_{7}y_{8})$. We take the following unfolding of
the generators of the ideal:

$y_{7}^{2}-y_{8}x+(f_{14,1}x+f_{14,7})y_{7}+f_{14,14}+f_{14,3}y_{11}+f_{14,4}y_{10}+f_{14,6}y_{8}\\\
y_{8}^{2}-y_{10}x+(f_{16,2}x+f_{16,8})y_{8}+(f_{16,3}x+f_{16,9})y_{7}\\\
+f_{16,16}+f_{16,5}y_{11}+f_{16,6}y_{10}\\\
y_{7}y_{10}-y_{11}x+(f_{17,1}x+f_{17,7})y_{10}+(f_{17,3}x+f_{17,9})y_{8}\\\
+(f_{17,4}x+f_{17,10})y_{7}+f_{17,17}+f_{17,6}y_{11}\\\
y_{11}y_{7}-x^{3}+(f_{18,2}x+f_{18,8})y_{10}+(f_{18,4}x+f_{18,10})y_{8}+f_{18,18}\\\
y_{8}y_{10}-x^{3}+(g_{18,1}x+g_{18,7})y_{11}+(g_{18,5}x+g_{18,11})y_{7}+g_{18,18}\\\
y_{11}y_{8}-y_{7}x^{2}+f_{19,19}+(f_{19,2}x+f_{19,8})y_{11}+(f_{19,3}x+f_{19,9})y_{10}\\\
+(f_{19,5}x+f_{19,11})y_{8}+(f_{19,6}x+f_{19,12})y_{7}\\\
y_{10}^{2}-y_{8}x^{2}+(f_{20,1}x^{2}+f_{20,7}x+f_{20,13})y_{7}+f_{20,20}+(f_{20,3}x+f_{20,9})y_{11}\\\
+(f_{20,4}x+f_{20,10})y_{10}+f_{20,5}y_{7}y_{8}+(f_{20,6}x+f_{20,12})y_{8}\\\
y_{11}y_{10}-y_{8}y_{7}x+(f_{21,1}x^{2}+f_{21,7}x+f_{21,13})y_{8}+(f_{21,5}x+f_{21,11})y_{10}\\\
+(f_{21,2}x^{2}+f_{21,8}x+f_{21,14})y_{7}+(f_{21,4}x+f_{21,10})y_{11}+f_{21,21}\\\
y_{11}^{2}-y_{10}x^{2}+f_{22,7}y_{7}y_{8}+(f_{22,6}x+f_{22,12})y_{10}+(f_{22,5}x+f_{22,11})y_{11}\\\
+(f_{22,3}x^{2}+f_{22,9}x+f_{22,15})y_{7}+(f_{22,2}x^{2}+f_{22,8}x+f_{22,14})y_{8}+f_{22,22}$

This shows the variables involved, except that the $f_{i,i}$ and $g_{18,18}$
are polynomials in $x$. In practice it is easier to first work with the
coefficients of the $y_{i}$ as polynomials. On this level the variables
$f_{i,i}$ and $g_{18,18}$ can be eliminated. After that step the coefficients
of $x$ can be taken. Most variables can be eliminated. What is left are nine
rather long polynomials with in total 134 monomials, but on closer inspection
a coordinate transformation can be found, leading to the following generators
of the ideal of the base space:

$\displaystyle f_{18,8}f_{20,5}-f_{17,6}f_{22,7}$ $\displaystyle
f_{14,4}f_{20,9}-f_{19,3}f_{21,10}+g_{18,7}f_{22,6}$ $\displaystyle-
f_{16,6}f_{19,3}f_{20,5}+f_{14,4}f_{20,5}f_{21,5}-g_{18,7}f_{22,7}$
$\displaystyle
f_{18,8}g_{18,7}+f_{16,6}f_{17,6}f_{19,3}-f_{14,4}f_{17,6}f_{21,5}$
$\displaystyle-f_{16,8}g_{18,7}-f_{16,6}f_{20,9}+f_{21,10}f_{21,5}$
$\displaystyle-
f_{16,8}f_{19,3}f_{20,5}+f_{20,9}f_{22,7}+f_{20,5}f_{21,5}f_{22,6}$
$\displaystyle
f_{14,4}f_{16,8}f_{20,5}-f_{21,10}f_{22,7}-f_{16,6}f_{20,5}f_{22,6}$
$\displaystyle-
f_{16,8}f_{17,6}f_{19,3}+f_{18,8}f_{20,9}+f_{17,6}f_{21,5}f_{22,6}$
$\displaystyle
f_{14,4}f_{16,8}f_{17,6}-f_{18,8}f_{21,10}-f_{16,6}f_{17,6}f_{22,6}$

The singular locus consists of two components, the $(f_{20,5},f_{17,6})$-plane
and the Segre cone

$\begin{bmatrix}f_{21,5}&f_{16,6}&f_{16,8}\\\
f_{19,3}&f_{14,4}&f_{22,6}\end{bmatrix}$

the other variables being zero. If $f_{20,5}=1$ then
$f_{18,8}=f_{17,6}f_{22,7}$ and the generators reduce to the Pfaffians of the
matrix

$\begin{bmatrix}0&f_{19,3}&f_{14,4}&f_{22,6}&f_{22,7}\\\
-f_{19,3}&0&-g_{18,7}&f_{20,9}&-f_{21,5}\\\
-f_{14,4}&g_{18,7}&0&f_{21,10}&-f_{16,6}\\\
-f_{22,6}&-f_{20,9}&-f_{21,10}&0&-f_{16,8}\\\
-f_{22,7}&f_{21,5}&f_{16,6}&f_{16,8}&0\end{bmatrix}$

in accordance with the fact that the curve deforms into $N(6)_{21}$ and
$N(6)_{22}$.

On the other component of the singular locus we take $f_{19,3}=1$ and find
$f_{16,6}=f_{14,4}f_{21,5}$, $f_{16,8}=f_{21,5}f_{22,6}$ while the generators
reduce to the minors of

$\begin{bmatrix}f_{22,7}&f_{18,8}&f_{16,6}-f_{14,4}f_{21,5}&f_{16,8}-f_{21,5}f_{22,6}\\\
f_{20,5}&f_{17,6}&g_{18,7}&f_{20,9}\end{bmatrix}$

###  3.6. Codimension 4 and type 4

For most of the semigroups with 5 generators and type 4 in the list the
associated monomial curve has $\dim T^{2}=20$. Only for $N(6)_{19}=\langle
6,7,9,10,11\rangle$ and $N(7)_{24}=\langle 6,8,9,11,13\rangle$ one has $\dim
T^{2}=21$, while $\dim T^{2}=26$ for $N(7)_{12}=\langle 5,9,11,12,13\rangle$.
The first two curves deform into $N(6)_{20}$ respectively $N(7)_{25}$, which
are curves with base space $G^{\prime}$. We have not been able to determine
the exact structure of the base space; in the tables this is marked by a
question mark (?). Only for two cases ($N(4)_{7}$ and $N(6)_{12}$, marked !)
we give here explicit equations. For $N(4)_{7}$ Nakano computed the base
computing in characteristic $7$ [20]. The versal deformation of the monomial
curve with semigroup $N(4)_{7}=\langle 5,6,7,8,9\rangle$ was computed with the
projection method in [23]. This computation also takes care of $N(6)_{12}$ by
the following result.

######  Lemma 3.4.

The curves $N(4)_{7}$ and $N(6)_{12}$ have $I^{2}$-equivalent plane
projections.

###### Proof.

The projection onto the plane of the first two coordinates has equation
$y_{6}^{5}-x^{6}=0$ for $N(4)_{7}$ and $y_{7}^{5}-x^{7}=0$ for $N(6)_{12}$.
The conductor ideal $I$ has in both cases length 6, being the difference of
the $\delta$-invariant of the plane curve and $\delta=g$ of the monomial
curve. An easy computation gives that $I=\mathfrak{m}^{3}$, and therefore
$x^{7}-x^{6}\in I^{2}$. ∎

We slightly modify the computation given in [23] by disregarding all terms in
$I^{2}$. We start by describing the deformation of the matrix defining
$\Sigma$:

$\begin{bmatrix}y&e_{01}&e_{02}\\\ -(x+e_{10})&y+e_{11}&e_{12}\\\
-e_{20}&-(x+e_{21})&y+e_{22}\\\ -e_{30}&-e_{31}&-x\end{bmatrix}$

We consider only consider deformations of negative weight, so we deform the
equation of the plane curve in the following way:

$y^{5}+c_{0}x^{5}+c_{1}x^{4}y+c_{2}x^{3}y^{2}+c_{3}x^{2}y^{3}+d_{0}x^{4}+d_{1}x^{3}y+d_{2}x^{2}y^{2}+d_{3}xy^{3}+d_{4}y^{4}$

With the help of Singular [6] the deformation equation (1) was solved for all
generators of $N$. The equation holds modulo the ideal $J$ of the base space,
described below. We give here the vector $\alpha$ as direct result of the
computation.

  * $\alpha_{1}=$

$x^{2}c_{0}+{\textstyle\frac{1}{2}}xc_{2}e_{01}+xc_{3}e_{02}+xd_{0}-yc_{3}e_{01}-yc_{1}e_{10}+yc_{2}e_{11}+yc_{3}e_{12}\linebreak-
c_{3}e_{02}e_{10}+c_{2}e_{02}e_{20}+c_{3}e_{02}e_{21}-c_{0}e_{01}e_{30}-c_{1}e_{02}e_{30}+c_{0}e_{12}e_{30}\linebreak-
e_{10}e_{12}e_{30}-c_{1}e_{01}e_{31}-c_{2}e_{02}e_{31}+c_{0}e_{22}e_{31}+{\textstyle\frac{1}{2}}d_{2}e_{01}+d_{3}e_{02}$

  * $\alpha_{2}=$

$x^{2}c_{1}+{\textstyle\frac{1}{2}}xyc_{2}+xc_{3}e_{01}+xc_{1}e_{10}-{\textstyle\frac{1}{2}}xc_{2}e_{11}+xd_{1}+{\textstyle\frac{1}{2}}yd_{2}+d_{3}e_{01}\linebreak-
e_{01}^{2}+d_{4}e_{02}+d_{1}e_{10}-{\textstyle\frac{1}{2}}d_{2}e_{11}$

  * $\alpha_{3}=$

${\textstyle\frac{1}{2}}x^{2}c_{2}+xyc_{3}+xc_{1}e_{20}+{\textstyle\frac{1}{2}}xc_{2}e_{21}+{\textstyle\frac{1}{2}}xd_{2}-yc_{3}e_{10}+yc_{2}e_{20}+yc_{3}e_{21}\linebreak+yd_{3}-c_{3}e_{02}e_{30}+d_{4}e_{01}+e_{02}e_{10}-e_{01}e_{11}+d_{1}e_{20}+{\textstyle\frac{1}{2}}d_{2}e_{21}+e_{01}e_{22}$

  * $\alpha_{4}=$

$y^{2}+xc_{1}e_{30}+{\textstyle\frac{1}{2}}xc_{2}e_{31}+yc_{2}e_{30}+yc_{3}e_{31}+yd_{4}+e_{01}e_{10}+e_{02}e_{20}\linebreak+d_{1}e_{30}+{\textstyle\frac{1}{2}}d_{2}e_{31}-e_{02}e_{31}$

To describe the base space it is useful to apply a coordinate transformation,
given by:

$\displaystyle d_{0}$ $\displaystyle\mapsto d_{0}+c_{0}e_{21}$ $\displaystyle
d_{1}$ $\displaystyle\mapsto d_{1}+c_{1}e_{21}+c_{0}e_{31}$ $\displaystyle
d_{2}$ $\displaystyle\mapsto d_{2}+c_{1}e_{31}$ $\displaystyle d_{3}$
$\displaystyle\mapsto d_{3}+e_{01}+c_{3}e_{10}$ $\displaystyle d_{4}$
$\displaystyle\mapsto d_{4}+e_{11}$

In the new coordinates ideal of the base is given by the following 20
generators, which we write as sum of corresponding minors:

$\begin{bmatrix}d_{0}+c_{3}e_{02}-c_{0}e_{10}&d_{1}-c_{1}e_{10}+c_{3}e_{12}-c_{0}e_{20}&d_{2}-c_{2}e_{10}-c_{0}e_{30}&d_{3}&d_{4}\\\
e_{01}&e_{11}&e_{10}-e_{21}&e_{20}-e_{31}&e_{30}\end{bmatrix}\\\
{}+\begin{bmatrix}-c_{0}e_{31}&e_{02}-c_{1}e_{31}&-e_{01}+e_{12}-c_{2}e_{31}&-e_{11}+e_{22}-c_{3}e_{31}&e_{21}\\\
e_{02}-c_{0}e_{30}&e_{12}-c_{1}e_{30}&e_{22}-c_{2}e_{30}&e_{10}-c_{3}e_{30}&e_{20}\end{bmatrix}$
$\begin{bmatrix}d_{0}&d_{1}&d_{2}-e_{02}+c_{1}e_{20}-c_{3}e_{22}&d_{3}-e_{12}+c_{2}e_{20}+c_{1}e_{30}&d_{4}-e_{22}+c_{2}e_{30}\\\
e_{02}&-e_{01}+e_{12}&-e_{11}+e_{22}&e_{21}&e_{31}\end{bmatrix}\\\ {}+{1\over
c_{0}}\begin{bmatrix}c_{0}e_{12}-c_{1}e_{02}&c_{0}e_{22}-c_{2}e_{02}&c_{0}e_{10}-c_{3}e_{02}&c_{0}e_{20}&c_{0}e_{30}-e_{02}\\\
c_{1}e_{01}-c_{0}e_{11}&c_{2}e_{01}-c_{0}e_{10}+c_{0}e_{21}&c_{3}e_{01}-c_{0}e_{20}+c_{0}e_{31}&-c_{0}e_{30}&e_{01}\end{bmatrix}$

The $\frac{1}{c_{0}}$ in front of the last matrix means that each minor has to
be divided by $c_{0}$. The structure of this base space is discussed in[23].

According to the formula (2) we obtain the deformation for $N(4)_{7}$ by
adding $\Delta_{1}$ to $\alpha_{1}$. For $N(6)_{12}$ the terms in $I^{2}$ are
$x^{7}+b_{0}x^{6}+b_{1}x^{5}y+b_{2}x^{4}y^{2}$, so we add the vector
$\Delta_{1}(x+b_{0},b_{1},b_{2},0)^{t}$ to $\alpha$. In particular we find
that the codimension of the base space is the same for $N(4)_{7}$ and
$N(6)_{12}$.

The curve $N(6)_{11}=\langle 5,8,9,11,12\rangle$ deforms with the deformation
$(t^{5},t^{8}+st^{7},t^{9},t^{11},t^{12})$ of the parametrisation to a curve
with semigroup $\langle 5,7,9,11,13\rangle$ but not to the monomial curve
$N(6)_{12}$ with this semigroup: the deformation
$(t^{5},t^{7}+s^{\prime}t^{8},t^{9},t^{11},t^{13})$ of $N(6)_{12}$ is non-
trivial of positive weight. We did not compute the base space for $N(6)_{11}$,
but we determined the quadratic part of the equations. It contains quadrics of
rank two, so the base space is definitely more complicated. It is feasible to
compute the deformation with Hauser’s algorithm, but the problem is to
simplify the resulting equations and write them in a systematic way. Even for
$N(4)_{7}$ it is very hard to see that the equations from Hauser’s algorithm
give the same base space as the one above from the projection method.

######  Proposition 3.5.

For all semigroups of genus $g\leq 7$ with $5$ generators and type $4$ one has
$\dim M=2g+2-\dim T^{1,+}$.

###### Proof.

If the monomial curve is negatively graded the result follows directly from
the Rim–Vitulli formula in Theorem 1.2. For $N(7)_{13}$ and $N(7)_{27}$ a
computation of the deformation up to order two yields 20 quadratic equations
which are among the equations for the tangent cone to the base space (and
probably give the tangent cone exactly). These 20 equations define a
projective scheme of dimension 15, which is therefore an upper bound for the
dimension of ${\mathcal{M}_{g,1}^{\Gamma}}$. At the same time Theorem 1.2
gives 15 as lower bound.

For $N(7)_{24}$ the situation is more complicated. One of the 21 equations
starts with cubic terms. We did compute the base space with Hauser’s method.
It leads to 256 equations in 63 variables, with 6923 monomials in total. These
equations are not independent, in fact they can be reduced to 59 equations.
Thirty eight variables occur linearly and can be eliminated. The result
consists of 21 equations in 25 variables, with 24829 monomials in total; the
equation starting with cubic terms has 3196 monomials. Taking the lowest
degree part of each equation gives a manageable system with 163 monomials
defining a scheme of dimension 15. ∎

###  3.7. Higher codimension

For the remaining curves we did not determine the base space. For the curves
$N(5)_{12}$, $N(6)_{18}$, $N(7)_{22}$ and $N(7)_{23}$ with type 5 the
dimension of $T^{2}$ is 45, for $N(7)_{34}$ it is 46. The curves $N(6)_{22}$
and $N(7)_{33}$ have type 6 and $\dim T^{2}=84$, while for $N(7)_{39}$, the
only type 8 curve, $\dim T^{2}=140$. With decreasing type the dimension of
$T^{2}$ also decreases: for $N(7)_{35}$, $N(7)_{36}$, $N(7)_{37}$ and
$N(7)_{38}$ the dimensions are 28, 19, 14, 14 respectively. All the curves
discussed here are negatively graded, except $N(7)_{23}$. For this case the
base space was computed up to order two, and a standard basis of the resulting
ideal was computed in finite characterstic, to speed up the computation. The
resulting upper bound for the dimension of
$\mathcal{M}_{7,1}^{\scriptscriptstyle N(7)_{23}}$ again coincides with the
lower bound of Theorem 1.2. Herewith Proposition 3.1 is completely establised.

## References

  * [1] Ragnar-Olaf Buchweitz, On deformations of monomial curves. In: Demazure M., Pinkham H.C., Teissier B. (eds) Séminaire sur les Singularités des Surfaces. Lect. Notes Math., vol 777. Springer, Berlin, Heidelberg, 1980), pp. 205–220. doi:10.1007/BFb0085884
  * [2] Evan M. Bullock, Irreducibility and stable rationality of the loci of curves of genus at most six with a marked Weierstrass point. Proc. Am. Math. Soc. 142 (2014), 1121–1132. doi:10.1090/S0002-9939-2014-11899-5
  * [3] André Contiero and Karl-Otto Stohr, Upper bounds for the dimension of moduli spaces of curves with symmetric Weierstrass semigroups. J. London Math. Soc. 88 (2013), 580–598. doi:10.1112/jlms/jdt034
  * [4] André Contiero, Aislan Leal Fontes, Jan Stevens and Jhon Quispe Vargas, On nonnegatively graded Weierstrass points. arXiv:2111.07721
  * [5] Daniel R. Grayson and Michael E. Stillman, Macaulay2, a software system for research in algebraic geometry, Available at http://www.math.uiuc.edu/Macaulay2/
  * [6] Decker, W.; Greuel, G.-M.; Pfister, G.; Schönemann, H.:  Singular 4-1-3 — A computer algebra system for polynomial computations.  https://www.singular.uni-kl.de (2020).
  * [7] Gert-Martin Greuel, On deformation of curves and a formula of Deligne. In: Algebraic Geometry. Lect. Notes Math., vol 961. Springer, Berlin, Heidelberg, 1982, pp. 141–168 . doi:10.1007/BFb0071281
  * [8] M. Haure, Recherches sur les points de Weierstrass d’une courbe plane algébrique Ann. Sci. Éc. Norm. Supér. (3) 13 (1896), 115–196.
doi:10.24033/asens.426

  * [9] Herwig Hauser,  An algorithm of construction of the semiuniversal deformation of an isolated singularity  In: Singularities, Part 1 (Arcata, Calif., 1981), Proc. Sympos. Pure Math. 40. Amer. Math. Soc., Providence, R.I., 1983, pp. 567–573.
  * [10] Herwig Hauser, La construction de la déformation semi-universelle d’un germe de variété analytique complexe. Ann. Sci. École Norm. Sup. 18 (1985), 1–56.
doi:10.24033/asens.1483

  * [11] Nathan Ilten, VersalDeformations: versal deformations and local Hilbert schemes. Version 3.0, A _Macaulay2_ package available at https://github.com/Macaulay2/M2/tree/master/M2/Macaulay2/packages
  * [12] T. de Jong and D. van Straten, A deformation theory for non-isolated singularities. Abh. Math. Sem. Univ. Hamburg 60 (1990),177–208.
doi:10.1007/BF02941057

  * [13] T. de Jong and D. van Straten, Deformations of the normalization of hypersurfaces. Math. Ann. 288 (1990), 527–547. doi:10.1007/BF01444547
  * [14] T. de Jong and D. van Straten, On the base space of a semi-universal deformation of rational quadruple points. Ann. of Math. 134 (1991), 653–678.
doi:10.2307/2944359

  * [15] Jiryo Komeda, On the existence of Weierstrass gap sequences on curves of genus $\leq$ 8, J. Pure Appl. Algebra 97 (1994), 51–71. doi:10.1016/0022-4049(94)90039-6
  * [16] E. Looijenga, The smoothing components of a triangle singularity. II. Math. Ann. 269 (1984), 357–387. doi:10.1007/BF01450700
  * [17] Bernd Martin, Deform.lib. A Singular library for computing Miniversal Deformation of Singularities and Modules.
  * [18] Tetsuo Nakano and Tatsuji Mori, On the moduli space of pointed algebraic curves of low genus: a computational approach. Tokyo J. Math. 27 (2004), 239–253. doi:10.3836/tjm/1244208488
  * [19] Tetsuo Nakano, On the Moduli Space of Pointed Algebraic Curves of Low Genus II —Rationality—. Tokyo J. Math. 31 (2008), 147–160.
doi:10.3836/tjm/1219844828

  * [20] Tetsuo Nakano, On the Moduli Space of Pointed Algebraic Curves of Low Genus III —Positive Characteristic—. Tokyo J. Math. 39 (2026), 565–582.
doi:10.3836/tjm/1484903137

  * [21] Henry C. Pinkham, Deformations of algebraic varieties with $G_{m}$-action. Astérisque 20 (1974).
  * [22] Dock Sang Rim and Marie A. Vitulli, Weierstrass points and monomial curves. J. Algebra 48 (1977), 454–476. doi:10.1016/0021-8693(77)90322-2
  * [23] J. Stevens, The versal deformation of universal curve singularities. Abh. Math. Sem. Univ. Hamburg 63 (1993), 197–213. doi:10.1007/BF02941342
  * [24] Jan Stevens, Deformations of singularities. Springer, Berlin etc. 2003, (Lect. Notes in Math.; 1811) doi:10.1007/b10723
  * [25] Jan Stevens, Computing Versal Deformations of Singularities with Hauser’s Algorithm. In: Deformations of Surface Singularities. Bolyai Society Mathematical Studies, vol 23. Springer, Berlin, Heidelberg (2013), pp. 203–228.
doi:10.1007/978-3-642-39131-6_6


11institutetext:  University of Trento, Italy
11email<EMAIL_ADDRESS><EMAIL_ADDRESS>22institutetext: University of Twente, The Netherlands
22email<EMAIL_ADDRESS>
# Large-scale multi-objective influence maximisation with network downscaling

Elia Cunegatti 1122 Giovanni Iacca 11 0000-0001-9723-1830 Doina Bucur 22
0000-0002-4830-7162

###### Abstract

Finding the most influential nodes in a network is a computationally hard
problem with several possible applications in various kinds of network-based
problems. While several methods have been proposed for tackling the influence
maximisation (IM) problem, their runtime typically scales poorly when the
network size increases. Here, we propose an original method, based on network
downscaling, that allows a multi-objective evolutionary algorithm (MOEA) to
solve the IM problem on a reduced scale network, while preserving the relevant
properties of the original network. The downscaled solution is then upscaled
to the original network, using a mechanism based on centrality metrics such as
PageRank. Our results on eight large networks (including two with $\sim$50k
nodes) demonstrate the effectiveness of the proposed method with a more than
10-fold runtime gain compared to the time needed on the original network, and
an up to $82\%$ time reduction compared to CELF.

###### Keywords:

Social Network Influence Maximisation Complex Network Genetic Algorithm Multi-
Objective Optimisation.

##  1 Introduction

Given a social network for which the network structure is known and the
process of influence propagation can be modelled, the problem of influence
maximisation [27] in its simplest form aims to select a certain number of
participants (nodes) in the network, such that their combined influence upon
the network is maximal. This is a combinatorial optimisation task, NP-hard for
most propagation models [17]. We study its multi-objective formulation, with
two competing objectives: the number of nodes is itself an objective to be
minimised, while the combined influence is to be maximised. Various
metaheuristics, both single- and multi-objective, were shown to obtain near-
optimal solutions [15, 4, 11, 6, 5, 22, 23, 31]. However, the drawback is
their long runtime (particularly for multi-objective optimisation), which
makes them infeasible to use on large social networks with more than $10^{5}$
nodes.

We contribute a scalable method for the multi-objective influence maximisation
problem, which allows to tackle the problem for social networks orders of
magnitude larger than before. The method is built around a state-of-the-art
Multi-Objective Evolutionary Algorithm (MOEA), but additionally employs a
first step which downscales the network (by a configurable factor) while
preserving its important structural properties, and a last step which upscales
the solutions from the downscaled network to the original one. This allows the
MOEA to run in feasible time, since it is executed on a smaller instance of
the problem.

The runtime has always been a key issue in the literature on the influence
maximisation problem. Some previous works have tried to overcome this
limitation by improving directly the effectiveness of the algorithm, see [21]
for a survey on this topic. Some recent works have tried to minimise the
runtime in billion-scale networks [20, 33, 12].

Yet, to the best of our knowledge no previous work has attempted to tackle the
problem by focusing on the input (i.e., the network), instead of the
algorithm.

We tested our method on six different networks, using two propagation models.
For the downscaling process, we used three different values of scaling factor,
to analyse how this affects the performance of our method. As for the
upscaling process, we tested different degree measures to find the best one
for the task.

Finally, we tested our method on two large networks with high scaling factor
values and compared the results with a classical heuristic algorithm.

The results show that our method can achieve near-optimal or even better
results, compared to the MOEA on the corresponding unscaled networks, while
drastically reduce the runtime required.

The rest of the paper is structure as follows. In the next section, we
describe our method. In Section 3, we present the numerical results. Finally,
we give the conclusions in Section 4.

##  2 Method

We provide a first overview of the method in Fig. 1. As for the MOEA, we use
Non-Dominated Sorting Genetic Algorithm-II (NSGA-II) [8], which has shown good
results on this problem in prior work [6, 5, 14], but whose runtime made it
prohibitive on large networks. This computationally heavy method is marked in
Fig. 1 on the left with a heavy red arrow. Instead of attempting to further
improve the algorithm (with likely minor gains in efficiency), here we design
an alternative which fundamentally changes the way we treat the problem input.

Figure 1: The method. The larger the original network (top left), the less
feasible influence maximisation is (bottom left). Our efficient three-step
method scales down the network, does influence maximisation on the scaled
network, then upscales the solutions (right).

Given a large social network (top left in Fig. 1), in step (1) we synthesise a
downscaled version of the network, for which the scaling factor is
configurable. A network scaled by a factor $s=2$ would contain half of the
nodes of the original, but otherwise preserve all the important properties of
the original network: the number of communities is maintained constant, and
the node degree distribution is scaled proportionally with the network size.
In step (2), we apply the MOEA on this downscaled network, obtaining a number
of non-dominated solutions (where each solution is a _seed set_ , i.e., the
set of nodes from which influence is propagated). Only one such seed set is
shown in Fig. 1, with the corresponding nodes marked in red. Finally, for step
(3) we devise a method based on node centrality metrics to select the seed set
in the original network, such that its nodes correspond (in terms of position
in the network) to the ones found in step (2). Steps (1-3) output a Pareto
front (PF) of solutions. To evaluate how accurate this method is, we also
execute the MOEA on the original network, and compare the two PFs. In the rest
of this section, we detail the three aforementioned steps111Code available at:
https://github.com/eliacunegatti/Influence-Maximization..

###  2.1 Step (1): Community-based downscaling

The output of the downscaling process is a completely synthetic network, not
identical to any part of the original network, but which appears very similar,
yet much smaller. The _scaling factor_ $s$ is the key parameter when
downscaling: we experiment with values in a geometric sequence,
$s\in\\{2,4,8\\}$. The downscaling process satisfies the following
requirements:

  1. 1.

preserves the number of communities in the network;

  2. 2.

downscales the number of nodes and edges by a factor $s$;

  3. 3.

preserves the the node degree distribution.

We pose the last requirement because dynamic phenomena on a network (such as
information propagation) have outcomes which depend on the node degrees. We
use the (2) algorithm [30], a state-of-the-art, scalable method for community
detection. The algorithm is stochastic, so variations in the number and size
of the communities are possible; because of this, we select one solution of
the Leiden algorithm, then filter out from the network any communities that
are too small (i.e., those that contain a number of nodes lower than the
scaling factor $s$). We then preserve this number of communities obtained on
the original network, downscaling (proportionally with $s$) the number of
nodes and edges in each community. Per community, the shape of the node degree
distribution is also preserved, as follows. Take the number of nodes in some
original community to be $N$. We take a number of samples of size $N/s$ from
the original node degrees of each community, then retain only the samples with
the smallest Euclidean distance (computed in terms of mean degree and standard
deviation per community) compared to the original ones. We thus have a desired
node degree distribution for a downscaled network.

The downscaled network is then generated by the Stochastic Block Model (SBM),
a random generative network model originally proposed in [13]. This generates
random networks with a configured number of communities, number of nodes per
community, and edge density per community. Here, we used a more fine-grained,
recent SBM method [16, 26] which takes also into account node degrees, and is
implemented in the Python graph-tool library222https://graph-tool.skewed.de.

###  2.2 Step (2): MOEA on two objectives (cascade size and seed set size)

Single-objective influence maximisation is the problem of finding those $k$
nodes with maximum collective influence upon the network. As mentioned above,
a candidate solution for this is a _seed set_ (a set of node identifiers) of
size $k$. The multi-objective formulation in this study aims to maximise the
collective influence, while minimising the size of the seed set $k$. In other
words, the fitness of a candidate solution is a tuple of: (a) the estimated
collective influence of the seed set, and (b) the size of the seed set. Both
values are normalised with respect to the network size, to allow for a fair
comparison between scaled and unscaled networks, as well as between networks
of different sizes. We set the maximum possible value of $k$ to be 2.5% of the
network size.

As for the estimated collective influence, we model influence cascade using
two classic, discrete-time propagation models for social networks [17]. They
simulate the dynamics of information adoption in a network modelled by graph
$G$, in which a set $S$ of “seed” nodes are the initial sources of
information. At any given time, the nodes in $G$ are in one of two states:
“activated” (if they received the information and may propagate it further) or
not. Initially, only the nodes in $S$ are activated. The information
propagates via network links probabilistically: a probability $p$ models the
likelihood of a source node activating a neighbouring destination node via
their common link. The important quantity is the number of nodes eventually
activated, also called the _cascade size_ —for influence maximisation, this is
typically the main objective.

Algorithm 1 gives a general view of cascade propagation models: set $A$
consists of all the activated nodes, and is initially equal to the seed set
$S$. At each time step, recently activated source nodes try to activate their
neighbours independently. If an activation fails, it is never retried (a
destination node is assumed to have made its decision). If it succeeds, the
propagation may continue; the process stops when no new nodes were activated
in a time step.

We use two model variants: Independent Cascade (IC) and Weighted Cascade (WC).
IC was first introduced in marketing, to model the complex effects of word-of-
mouth communication [10]. In IC, the probability $p$ is equal across all links
(when a node has more than one neighbour, their activations are tried in
arbitrary order). WC further models the fact that a node’s attention is
limited: the probabilities of activation on links leading to a destination
node $m$ are not uniform, but inversely proportional to the number of such
links in $G$ (in other words, the degree of $m$), $p=1/deg(m)$ [17], where
$deg(m)$ is the in-degree of node $m$, i.e., the number of edges incoming to
$m$.

Algorithm 1 Cascade propagation models. $G$ is the graph, $S$ the set of seed
nodes, and $p$ the probability that a link will be activated.

1:$G$, $S$, $p$

2:$A\leftarrow S$ $\triangleright$ The complete set of activated nodes

3:$B\leftarrow S$ $\triangleright$ Nodes activated in the previous iteration

4:while $B$ not empty do

5: $C\leftarrow\emptyset$ $\triangleright$ Nodes activated in the current
iteration

6: for $n$ in $B$ do

7: for $m$ in $neighbours(n)\setminus A$ do

8: $C.add(m)$ with probability $p$ $\triangleright$ Activation attempt

9: end for

10: end for

11: $B\leftarrow C$ and $A\leftarrow A\cup B$

12:end while

13:return $|A|$ $\triangleright$ The final size of the cascade

Although a single execution of Algorithm 1 is polynomial in the size of the
network, the model is stochastic, and computing the expected cascade size
exactly for a given seed set $S$ is #P-complete [32]. However, good estimates
of $|A|$ can be obtained by Monte Carlo simulations: in our experiments, we
run $100$ repetitions of Algorithm 1 for each estimation.

Concerning the MOEA, we used the implementation and parameterisation of NSGA-
II adopted in prior work [5, 14]. In short, the parent solutions are selected
by tournament selection; the child solutions are generated by one-point
crossover and random mutation. An archive keeps all the non-dominated
solutions found, i.e., the PF. The replacement mechanism selects non-dominated
solutions by their dominance levels, and then sorts them by crowding distance
to prefer isolated solutions and obtain a better coverage of the PF.

To improve the convergence of the MOEA, we apply a _smart initialisation_ of
its initial population, as proposed in [18]. First, we apply node filtering,
which computes the influence of each node in the network separately, and then
keeps the 50% most influential nodes. Then, each of these nodes is added to a
candidate solution with a probability proportional to its degree.

We summarise the parameters of the method in Table 1.

Table 1: Parameters of the method.

Network parameters |
---|---
Scaling factor $s$ | $\\{2,4,8\\}$
Max. seed set size $k$ | 2.5% $\cdot$ network size
IC probability $p$ | 0.05
No. simulations | 100

NSGA-II parameters |
---|---
Population size | 100
Generations | 1000
Elites | 2
Crossover rate | 1.0
Mutation rate | 0.1
Tournament size | 5

###  2.3 Step (3): Upscaling

Once the MOEA has been run on the downscaled network, the last step is to map
the solutions back to the original network. This step takes in input two
graphs (the original $G$ and the downscaled $G_{s}$) and a set seed on
$G_{s}$, denoted as $S_{s}$. The task is to translate $S_{s}$ into an seed set
$S$ on $G$.

We achieve this by _matching_ nodes between the two graphs, based on their
_node centrality indicators_ , namely node statistics which capture the
position of the node in the network. We test the following classical
centrality indicators, based on them being shown to be predictive of the
node’s influence [3]: each node’s _degree_ , _eigenvector centrality_ and its
variants _PageRank_ with a 0.85 damping factor and _Katz centrality_ ,
_closeness_ , _betweenness_ , and _core number_ (see [25] for their
definitions).

For a seed set $S_{s}$ in $G_{s}$, we find a matching seed set $S$ of
$|S_{s}|\times s$ nodes in $G$. We do this per community. Each node in $S_{s}$
has a _rank_ in its community, based on the centrality values of all nodes in
that community. We then search in $G$ (among the nodes in the corresponding
community) for $s$ nodes with the most similar ranks. These nodes form $S$.

Evaluation. We evaluate the PFs obtained, particularly to compare between the
MOEA results on the original network and those obtained with our new method.
We use the hypervolume (HV) indicator (also known as Lebesgue measure, or S
metric) proposed in [34]. This is calculated as the volume (of the fitness
space) dominated by each solution in the PF with respect to a reference point.
The hyperarea (HR) [34] is the ratio of two HVs, and is used here in the final
evaluation step (bottom center in Fig. 1).

##  3 Results

Network data. We test our method on six real-world social network topologies
(listed in Table 2). These range between 4 039 and 28 281 nodes, with variable
average degrees (and thus network densities), and variable number and size of
communities. Ego Fb. denotes data merged from many ego networks on Facebook,
collected from survey participants at a large university. Fb. Pol. is a
network of mutually liked, verified politicians’ pages on Facebook. Fb. Pag.
is similar, but with Facebook pages from various categories. Fb. Org. is a
network of friendships among Facebook users who indicated employment at one
corporation. PGP is the largest connected component in the network of PGP
encryption users. Deezer represents online friendships between users of the
Deezer music platform. All graphs are undirected and connected.

Table 2: Networks considered in the experimentation. |  |  | Communities | Node degrees
---|---|---|---|---
Network |  Nodes |  Edges |  Num. |  Min. |  Max. |  Avg. |  Std. |  Max.
Ego Fb. [24] | 4 039 | 88 234 | 17 | 19 | 548 | 43.90 | 52.41 | 1045
Fb. Pol. [28] | 5 908 | 41 729 | 31 | 8 | 562 | 14.12 | 20.09 | 323
Fb. Org. [9] | 5 524 | 94 219 | 13 | 35 | 1045 | 34.11 | 31.80 | 417
Fb. Pag. [28] | 11 565 | 67 114 | 31 | 8 | 1916 | 11.60 | 21.28 | 326
PGP [1] | 10 680 | 24 316 | 91 | 8 | 668 | 4.55 | 8.07 | 205
Deezer [29] | 28 281 | 92 752 | 71 | 8 | 4106 | 6.55 | 7.94 | 172

In the remainder of this section, we experiment with and evaluate our method.
We present results for the three distinct steps of the method (as per Fig. 1).

###  3.1 Community-based downscaling of large networks

This step obtains synthetic scaled networks, with the scaling factor $s$.
These networks have the same number of communities, a scaled number of nodes
and edges, and the same shape of the degree distribution. For
$s\in\\{2,4,8\\}$, we show in Fig. 2 the degree distributions (in log-log
scale) for the six networks: that of the original (unscaled) network, and that
of synthetic, scaled versions. Fig. 1 included plots of Fb. Org. before and
after downscaling ($s=4$).

Figure 2: Degree distributions, before and after downscaling.

The networks plausibly fit typical power-law degree distributions, in which
the fraction of nodes with a certain degree $d$ is proportional to
$d^{-\alpha}$ where $\alpha$ is positive (so, decreases with $d$), after a
cutoff point $d_{\text{min}}$. In real-world networks from various domains,
the power-law parameter $\alpha$ is often measured between 1.5 and 3 [2],
which is mostly the case also for these six social networks. This parameter
can be seen in Fig. 2, in the linear slope of all distributions (for high
enough degrees). Our downscaling step preserves the power-law parameter
$\alpha$ between the original and downscaled networks, naturally while scaling
down the degree frequencies with $s$. We show the fitted values for $\alpha$
in Table 3, from which it is clear that the downscaling method introduced
little error in the shape of the degree distribution.

Table 3: Degree distribution preservation, power-law coefficients. | Original | $\quad s=2$ | $\quad s=4$ | $\quad s=8$
---|---|---|---|---
Ego Fb. | 1.32 | 1.35 | 1.38 | 1.42
Fb. Pol. | 1.50 | 1.52 | 1.54 | 1.57
Fb. Org. | 1.40 | 1.32 | 1.33 | 1.35
Fb. Pag. | 1.60 | 1.58 | 1.60 | 1.62
PGP | 2.11 | 1.94 | 1.97 | 1.93
Deezer | 1.73 | 1.66 | 1.68 | 1.68

In the next step, we run the MOEA on the downscaled networks (and, for
evaluation, also on the original networks).

###  3.2 MOEA and solution upscaling: the optimality of solutions

The optimisation process obtains a two-dimensional PF of solutions, where as
said each solution is a seed set of $k$ nodes of the network. We show an
example of PFs in Fig. 3, for the PGP case and for both propagation models (IC
and WC), obtained in one single run of the MOEA on the original network and on
the downscaled networks (for three values of $s$). The PFs for the original
and downscaled networks (top in Fig. 3) show that running the optimisation on
the downscaled networks preserves the shape of the PF, but slightly lowers the
values reached for the main objective, namely the percentage of influenced
nodes (i.e., the cascade size). The more downscaled the network is, the more
pronounced this effect appears to be. When upscaling the solutions obtained on
the downscaled networks, here using the PageRank centrality in the upscaling
process (bottom in Fig. 3), this gap closes for IC, but not for WC
propagation.

Figure 3: PGP Pareto fronts: (top) for the original and downscaled networks,
and (bottom) for the original network and the upscaled solutions. Figure 4:
Fb. Pag. Pareto fronts: (top) for the original and downscaled networks, and
(bottom) for the original network and the upscaled solutions.

Of note, the PGP case shown in Fig. 3 is actually one of the cases where our
method performs worst (see below). One of the cases where it performs best is
Fb. Pag., whose PFs are shown in Fig. 4 (also in this case, for one single run
of the MOEA on the original network and on the downscaled networks, using
PageRank for upscaling). On this network, the MOEA on the downscaled networks
often produces a better PF than on the original (top in 4), and the final,
upscaled PFs are comparable to the original one (bottom in 4). Thus, the
method largely preserved the quality of the solutions.

In general and quantitatively, we observe great variation among the networks
under test in terms of HR, i.e., on the ratio between (1) the HV subtended by
the PF found by the MOEA on the original network and (2) the HV subtended by
the PF obtained from the upscaled solutions.

To provide a more robust estimate of the HR values, for each network and
propagation model we executed the MOEA in 10 independent runs on the original
network, and in 10 runs for each value of scaling factor333We also compared
directly the HV values. We applied the Wilcoxon Rank-Sum test (with
$\alpha=0.05$) to analyse whether the HV values calculated on the downscaled
solutions and the upscaled ones (with upscaling based on PageRank) were
significantly different from the HV values obtained on the original network,
all on 10 runs. All the pairwise comparisons resulted statistically
significant, excluding the one related to the downscaled solutions found on
Fb. Pag. with $s=2$ and WC model.. We show the HR values (averaged across 10
runs) comparatively in Fig. 5. Each cell contains the HR for a particular
network, propagation model, and scaling factor. The “MOEA” rows contain
intermediate HR values, which compare the PF on the downscaled networks with
the PF on the original network. For three out of six networks (Ego Fb., Fb.
Pol., and PGP) the HR never reaches 1, meaning that the HV on the downscaled
networks is _lower_ than the one on the original network. For the other three
networks, HR reaches or surpasses 1, for at least some scaling factor and one
or both propagation models, meaning that the downscaling step by itself
preserved or even raised the optimality of the PF.

Figure 5: Hyperarea (averaged across 10 runs) for each network, propagation
model, scaling factor, and centrality metric.

The HR values in the rows labelled with the various centrality names in Fig. 5
compare instead the PF of the upscaled solutions with the PF on the original
network, so serve as evaluation metrics for our method. These show how
accurate each centrality is at the upscaling task, and thus help choose the
most suitable centrality for any future work. We observe that it is generally
easier for all centralities to obtain a good PF of upscaled solutions when
using IC. However, three of the centralities consistently yield good upscaling
results for both IC and WC: PageRank, betweenness, and degree centralities.
PageRank is the best option overall (this is why we used it in Fig. 3 and Fig.
4). Across networks with IC, the HR obtained by PageRank is in the interval
$[0.93,1]$ when $s=2$, in $[0.86,0.97]$ when $s=4$, and in $[0.78,0.96]$ when
$s=8$. Fairly similar numbers are obtained with WC.

###  3.3 Runtime analysis

The proposed method not only can preserve the quality of the solutions, but,
by design, gains drastically in runtime due to our design based on downscaling
the input data. We compute the runtime in terms of number of _activation
attempts_ (line 7 in Algorithm 1). This is a proxy metric for the actual
runtime, as it counts how many times that activation step is executed during
all the simulations needed by a MOEA run (either on the original network, or
on the downscaled one). We show these measurements in Fig. 6, from which we
can see (note the log scale on the y-axis) that the runtime needed by our
method decreases by a factor from two to five when the scaling factor is
doubled.

Figure 6: Runtime (no. activation attempts) in the comparative experiments
with MOEA on the original network (average across $10$ runs, error bars
indicate std. dev.).

###  3.4 Comparison with heuristic algorithm

To further prove the applicability of the proposed method, we conducted a
final set of experiments on two different networks with $\sim$50k nodes: soc-
gemsec [28] and soc-brightkite [7]. The goal of these experiments was to test
our method with higher scaling factors on larger networks.

Due to the large runtime required, we decided to run the experiments only with
the WC model for $s=16$ and $s=32$, and compare the results with those
obtained by the CELF [19] algorithm computed on the unscaled network. Due to
computational limitations, we could perform only one run of the two
algorithms.

Despite these limitations, we can see from Fig. 7 that our proposed method is
able to achieve better results than CELF, even for higher scaling factors. Not
only that: Fig. 8 shows that we obtain these results with a much lower number
of activation attempts compared to CELF (with a reduction of up to $82\%$).

It is worth to mention that the results obtained with our method depend on the
MOEA’s parameters, which remained the same as in the previous experiments, see
Table 1. However, we have noticed that the HV reaches a plateau after $\sim$
300 generations. This means that with a simple implementation of a convergence
termination criteria, the gain in runtime would be even higher.

Figure 7: PFs obtained with CELF and with our method for $s=16$ and $s=32$.
Figure 8: Runtime (no. activation attempts) measurements in the comparative
experiment with CELF.

##  4 Discussion and conclusions

In this paper, we proposed a novel approach to tackle the influence
maximisation problem where the focus is on the input network instead of the
algorithm itself.

Our method has been proven to work correctly, although with some differences
in the results, with both IC and WC propagation models on all the tested
networks, regardless their sizes or properties.

The results demonstrate the effectiveness of our method in terms of quality of
the solutions obtained. At the same time, our method is able to drastically
decrease the runtime, allowing the use of the multi-objective evolutionary
algorithm even in large networks.

Our method has proven to work properly with different scaling values.
Nevertheless, the results show a lower quality of the solutions as the scaling
factor increases. This result is in line with expectations, as it shows a
clear trade-off between solution quality and runtime gain.

To the best of our knowledge, this is the first work where a downscaling and
upscaling process is proposed on networks to solve the influence maximisation
problem. Regarding the degree measure used in the upscaling process, we can
state the best one to be Page Rank, given the high quality of the upscaling
results obtained and the low complexity required to compute it.

## References

  * [1] Boguñá, M., Pastor-Satorras, R., Díaz-Guilera, A., Arenas, A.: Models of social networks based on social distance attachment. Physical Review. E 70(5), 056122 (2004)
  * [2] Broido, A.D., Clauset, A.: Scale-free networks are rare. Nature communications 10(1), 1–10 (2019)
  * [3] Bucur, D.: Top influencers can be identified universally by combining classical centralities. Scientific Reports 10(1), 1–14 (2020)
  * [4] Bucur, D., Iacca, G.: Influence Maximization in Social Networks with Genetic Algorithms. In: EvoApplications (2016)
  * [5] Bucur, D., Iacca, G., Marcelli, A., Squillero, G., Tonda, A.: Improving multi-objective evolutionary influence maximization in social networks. In: EvoApplications. pp. 117–124 (2018)
  * [6] Bucur, D., Iacca, G., Marcelli, A., Squillero, G., Tonda, A.P.: Multi-objective Evolutionary Algorithms for Influence Maximization in Social Networks. In: EvoApplications (2017)
  * [7] Cho, E., Myers, S.A., Leskovec, J.: Friendship and mobility: user movement in location-based social networks. In: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 1082–1090. ACM (2011)
  * [8] Deb, K., Agrawal, S., Pratap, A., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computing 6, 182–197 (2002)
  * [9] Fire, M., Puzis, R., Elovici, Y.: Organization Mining Using Online Social Networks. Networks and Spatial Economics 16, 545–578 (2013)
  * [10] Goldenberg, J., Libai, B., Muller, E.: Talk of the Network: A Complex Systems Look at the Underlying Process of Word-of-Mouth. Marketing Letters 12, 211–223 (2001)
  * [11] Gong, M., Yan, J., Shen, B., Ma, L., Cai, Q.: Influence maximization in social networks based on discrete particle swarm optimization. Information Sciences 367-368, 600–614 (2016)
  * [12] Güney, E., Leitner, M., Ruthmair, M., Sinnl, M.: Large-scale influence maximization via maximal covering location. Eur. J. Oper. Res. 289, 144–164 (2021)
  * [13] Holland, P., Laskey, K.B., Leinhardt, S.: Stochastic blockmodels: First steps. Social Networks 5, 109–137 (1983)
  * [14] Iacca, G., Konotopska, K., Bucur, D., Tonda, A.: An evolutionary framework for maximizing influence propagation in social networks. Software Impacts 9, 100107 (2021)
  * [15] Jiang, Q., Song, G., Cong, G., Wang, Y., Si, W., Xie, K.: Simulated Annealing Based Influence Maximization in Social Networks. In: AAAI (2011)
  * [16] Karrer, B., Newman, M.E.J.: Stochastic blockmodels and community structure in networks. Physical Review. E 83 1 Pt 2, 016107 (2011)
  * [17] Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: KDD. pp. 137–146 (2003)
  * [18] Konotopska, K., Iacca, G.: Graph-aware evolutionary algorithms for influence maximization. In: GECCO Companion (2021)
  * [19] Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., Vanbriesen, J.M., Glance, N.S.: Cost-effective outbreak detection in networks. In: KDD (2007)
  * [20] Li, X., Smith, J.D., Dinh, T.N., Thai, M.T.: Tiptop: (almost) exact solutions for influence maximization in billion-scale networks. IEEE/ACM Transactions on Networking 27, 649–661 (2019)
  * [21] Li, Y., Fan, J., Wang, Y., Tan, K.L.: Influence maximization on social graphs: A survey. IEEE Transactions on Knowledge and Data Engineering 30, 1852–1872 (2018)
  * [22] Lotf, J.J., Azgomi, M.A., Dishabi, M.R.E.: An improved influence maximization method for social networks based on genetic algorithm. Physica A: Statistical Mechanics and its Applications 586, 126480 (2022)
  * [23] Ma, L., Shao, Z., Li, X., Lin, Q., Li, J., Leung, V.C., Nandi, A.K.: Influence Maximization in Complex Networks by Using Evolutionary Deep Reinforcement Learning. IEEE Transactions on Emerging Topics in Computational Intelligence (2022)
  * [24] McAuley, J., Leskovec, J.: Learning to Discover Social Circles in Ego Networks. In: NIPS (2012)
  * [25] Newman, M.: Networks. Oxford University Press (2018)
  * [26] Peixoto, T.P.: Nonparametric Bayesian inference of the microcanonical stochastic block model. Physical Review. E 95 1-1, 012317 (2017)
  * [27] Richardson, M., Agrawal, R., Domingos, P.M.: Trust Management for the Semantic Web. In: SEMWEB (2003)
  * [28] Rozemberczki, B., Davies, R., Sarkar, R., Sutton, C.: GEMSEC: Graph Embedding with Self Clustering. In: ASONAM. pp. 65–72 (2019)
  * [29] Rozemberczki, B., Sarkar, R.: Characteristic functions on graphs: Birds of a feather, from statistical descriptors to parametric models. In: CIKM. pp. 1325–1334 (2020)
  * [30] Traag, V.A., Waltman, L., van Eck, N.J.: From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports 9 (2019)
  * [31] Wang, C., Zhao, J., Li, L., Jiao, L., Liu, J., Wu, K.: A multi-transformation evolutionary framework for influence maximization in social networks (2022)
  * [32] Wang, C., Chen, W., Wang, Y.: Scalable influence maximization for independent cascade model in large-scale social networks. Data Mining and Knowledge Discovery 25, 545–576 (2012)
  * [33] Wu, H.H., Küçükyavuz, S.: A two-stage stochastic programming approach for influence maximization in social networks. Computational Optimization and Applications 69, 563–595 (2018)
  * [34] Zitzler, E.: Evolutionary algorithms for multiobjective optimization: Methods and applications, vol. 63. Citeseer (1999)