#  Approximation algorithms for k-median problems on complex networks: theory
and practice

Roldan Pozo
National Institute of Standards & Technology

###### Abstract

Finding the k-median in a network involves identifying a subset of k vertices
that minimize the total distance to all other vertices in a graph. This
problem has been extensively studied in computer science, graph theory,
operations research, and numerous areas due to its significance in a wide
range of applications. While known to be computationally challenging (NP-hard)
several approximation algorithms have been proposed, most with high-order
polynomial-time complexity. However, the graph topology of complex networks
with heavy-tailed degree distributions present characteristics that can be
exploited to yield custom-tailored algorithms. We compare eight algorithms
specifically designed for complex networks and evaluate their performance
based on accuracy and efficiency for problems of varying sizes and application
areas. Rather than relying on a small number of problems, we conduct over
16,000 experiments covering a wide range of network sizes and k-median values.
While individual results vary, a few methods provide consistently good
results. We draw general conclusions about how algorithms perform in practice
and provide general guidelines for solutions.

##  1 Introduction

The $k$-median problem is an important and fundamental problem in graph
theory, and various application areas. Given a connected network, it seeks to
find $k$ vertices which are the closest (in terms of average distance) to the
remaining vertices in the network graph. These $k$ vertices . This is crucial
in the spread of viral messages in social networks, disease contagion in
epidemiological models, operation and distribution costs for goods and
services, marketing and advertising, design layout of communication networks,
and other wide-ranging applications.

Finding such an optimal set of vertices is referred to as the influence
maximization problem [1] and numerous algorithms have been proposed to address
this issue. Although these algorithms were not explicitly designed for the
$k$-median problem, they share mathematical similarities, as they attempt to
find influential vertices that are similarly well-connected and can quickly
disseminate information throughout the network. The level of influence can be
measured in various ways, typically employing diffusion models such as
independent cascade model [2] or epidemiological models of the Susceptible-
Infected (SI) and Susceptible-Infected-Recovered (SIR) [3] types. Section 3
illustrates how the $k$-median problem is a special case of these models. A
related problem, the $k$-center, minimizes the maximum, rather than the
summation of distances to remaining nodes. In practice, the $k$-medium is
better adapted for distribution and throughput optimization as it minimizes
the total distances traveled.

Formally, the $k$-median problem on network graphs has been shown to be NP-
hard (in terms of $k$) by reduction to the dominant cover problem [4] and is
computationally intractable for large network graphs. The situation is
difficult largely in part to the explosion of the solution space as the value
of $k$ grows. A graph with $|V|$ vertices yields $\binom{|V|}{k}$ possible
$k$-element candidate sets. Even a modest problem of $k=10$ for a graph with
1,000 vertices would yield $10^{23}$ vertex sets to examine. In this paper, we
consider real graphs containing millions of vertices with $k$ values up to
100, yielding solution spaces of over $10^{400}$ possibilities. A brute-force
approach, in such cases, is clearly infeasible and approximation methods must
be employed.

##  2 Notation and definitions

###### Definition 2.1

k-median problem: Given an integer $k$ and a connected graph $G=(V,E)$, find a
set of $S$ of $k$ vertices that minimize the summation of distances from $S$
to the remaining vertices of $G$.

Using $d(v,u)$ as the distance (length of shortest path) between vertices $v$
and $u$, we can define the distance $d(v,S)$ between a single vertex and a
vertex set $S$ as the minimum distance between $v$ and any vertex in $S$. We
can then define the farness metric $F(S)$ as

$F(S)\doteq\sum_{v\>\in\>V-S}d(v,S)$ (1)

Often, it is convenient to normalize this quantity by the number of external
vertices and express this as an average distance, $A(S)$ to the remainder of
the graph as

$A(S)\doteq\frac{F(S)}{|V-S|}$ (2)

as it is more intuitive and makes the comparisons of these values more
meaningful across graphs of varying sizes. This is sometimes referred to as
the normalized farness metric. Note that a set $S$ that minimizes $F$ also
minimizes $A$ and vice versa, as these are scalar multiple of the other. From
here on we will utilize this normalized farness metric, or simply the average-
distance, $A(S)$ in the formulation of the original minimization problem, Def.
2.1, without loss of generality.

In this context, we can restate the $k$-median problem on a network graph $G$
to be the identification of a set of $k$-vertices which minimize the average
distance to the remaining $|V|-k$ vertices:

$M^{*}(k)\;\doteq\min_{|S|=k}A(S)$ (3)

Thus, $X=\\{v_{1},v_{2},\ldots v_{k}\\}$ is a solution to the $k$-median
problem if and only if

$A(X)=M^{*}(k)$ (4)

or, equivalently, if and only if

$X\in\mathop{\mathrm{argmin}}_{|S|=k}A(S)$ (5)

We refer to $M^{*}(k)$ as the true optimal value of the $k$-median problem on
a graph $G$, and let $M(k)$ denote an approximation to this solution using the
methods described in Sec. 3. When necessary, we use $M_{\mbox{\it method}}(k)$
to avoid ambiguity.

The neighborhood of a vertex $a$ is the set of its adjacent nodes and is given
as $N(a)\doteq\\{b\in V\>|\>d(a,b)=1\\}$. The degree of a vertex,
$\mbox{deg}(v)$, is given by $|N(v)|$. The $p$th level neighborhood shell is
comprised of the vertices a distance $p$ away and is given as
$N^{(p)}(a)\;\doteq\;\\{b\in V\;|\;d(a,b)=p\\}$. These definitions are
extended to arbitrary subsets $A\subseteq V$ as $d(A,b)\doteq\min_{a\in
A}d(a,b)$ and $N^{(p)}(A)\doteq\\{b\in V\>|\>d(A,b)=p\\}$. If $S$ is a set,
then $S|_{k}$ is the collection of all subsets of $S$ of size $k$.

Given these definitions, we can recast the farness metric $F(S)$ in Eq. 1 as a
summation of neighborhood shells weighted by their distance:

$F(S)\;=\;\sum_{p=0}^{D}p\>|N^{(p)}(S)|$ (6)

where $D$ is the diameter of the graph. This alternate representation of
$F(S)$ provides a connection to influential nodes network models described in
Sec. 3.

If $f$ is a function that maps domain $D$ to range $R$, $f:D\rightarrow R$,
then it can be applied to any subset of $D$ to generate a set of values. That
is, for $S\subseteq D$, $f(S)\doteq\\{f(x),x\in S\\}$. For a finite set,
$\max_{x\in S}f(x)$ returns the maximum value of $f$ over domain $S$, and

$\mathop{\mathrm{argmax}}_{x\in S}f(x)\;\doteq\;\\{s\in S,f(s)=\max f(S)\\}$
(7)

denotes the elements of $S$ where the maxima of $f$ occur. This notion can be
extended to the top largest $k$ values of $f$, which can be considered an
ordered list in decreasing order and represented as a sequence
$T=(x_{1},x_{2},\ldots x_{k})$ where $f(x_{1})\geq f(x_{2})\geq\ldots\geq
f(x_{k})$. As in the case of the conventional $\mathop{\mathrm{argmin}}$
function, this sequence may not be unique, due to ties. We define this
extension of $\mathop{\mathrm{argmax}}$ as the set of all possible such
sequences:

$\displaystyle\mathop{\mathrm{argmax}[k]}_{x\in S}$ $\displaystyle
f(x)\;\doteq\;\\{(x_{1},x_{2},\ldots x_{k}):$ (8) $\displaystyle f(x_{i})\geq
f(x_{j})\;\;\forall i<j$ $\displaystyle f(x_{i})\geq f(s)\>\>\forall x\in
S\setminus\\{x_{1},\ldots x_{i-1}\>\>\\}$

A similar definition can be described for $\mathop{\mathrm{argmin}}$ and
$\mathop{\mathrm{argmin}[k]}$. While $\max f$ is a single value,
$\mathop{\mathrm{argmax}}f$ is a set of values, and
$\mathop{\mathrm{argmax}[k]}f$ is a set of sets of sequences. Since any
$x\in\mathop{\mathrm{argmax}}f$ is a maximum of $f$, one can write
$x\leftarrow\mathop{\mathrm{argmax}}f$ to select one of its elements.
Similarly, $x\leftarrow\mathop{\mathrm{argmax}[k]}f$ selects a unique group of
top-$k$ performers.

##  3 Approximation algorithms and related problems

The field of approximation methods to the $k$-median problem is quite large.
Resse [5] provides a comprehensive overview of over 100 methods from linear
programming, genetic algorithms, simulated annealing, vertex substitution, and
other approaches. In general, the algorithm with the best guaranteed
approximation ratio is a local search and swap method [6] with provides a
bound of $3+2/p$ where $p$ is the number of vertices simultaneously swapped.
Its computation time is $O(n^{p})$, where $n$ is the number of vertices. Thus,
even for a quadratic-order complexity $O(n^{2})$, which is quite limiting for
large networks, the best guarantee we can get is a factor of four from
optimal. While these approaches were adequate for small networks, the higher-
order polynomial time complexity makes them unfeasible for networks with
thousands or million of vertices [7].

Instead, researchers have turned their attention to algorithms for finding
effective spreaders in connected networks with heavy-tailed degree
distributions, often employing an Susceptible-Infected (SI) or Susceptible-
Infected-Recovered (SIR) model of spread [8] [9], where $I(t)$ denotes the
number of infected nodes at time $t$, and $I(0)$ is the number of initially
infected nodes. The $k$-median can be thought of a special case of an SI model
where the probability of an infected node transmitting the disease to a
susceptible neighbor is 1.0, or an SIR model with the the probability of
recovery for each node is 0.0. In which case, the solution to the
$k$-medianproblem can be thought of as maximizing the integral of the number
of infected nodes over the propagation steps, starting with $k$ initial
infected vertices.

That is, at each time step an infected node may transmit its disease to
neighboring nodes, then starting with an infected set of vertices S and a
probability of transmission of 1.0, the number of new infected nodes at each
time step $t$, is simply the size of the neighborhood shell $N^{(t)}(S)$. That
is,

$|N^{(t)}(S)|\;=\;I(t)-I(t-1)$ (9)

where we take each neighborhood shell to be a discrete time step. In the
formulation of epidemiological models, the continuous version of Eq. 6 can be
expressed as

$\sum_{p=0}^{D}t\>|N^{(t)}(S)|\;\rightarrow\;\int_{0}^{D}t\>I^{\prime}(t)dt$
(10)

and integrating by parts, we have

$\displaystyle\int_{0}^{D}t\>I^{\prime}(t)dt\;$
$\displaystyle=\;tI(t)\arrowvert^{D}_{0}-\int_{0}^{D}I(t)dt$ (11)
$\displaystyle=\;|V|\cdot D-\int_{0}^{D}I(t)dt$ (12)

Since $|V|\cdot D$ is a fixed constant for each network, minimizing Eq. 12
requires maximzing

$\int_{0}^{D}I(t)dt$ (13)

Hence, the set of maximal influencers $S$ that make $I(t)$ grown as quickly as
possible, is also a solution to the k-median problem. Thus, approximation
methods for finding maximal influencers in networks can serve to find
approximations to minimizing $F(S)$.

The algorithms described below represent methods used in the literature for
solving these types of problems. Typically, they work by assigning each vertex
a numerical value (centrality) which captures the affinity of this vertex to
be a maximal influencer. The vertices with the top $k$ values then become the
candidate target set for the solution. For each algorithm, we define
$k$-median approximation as

$X_{\mbox{\it method}}\>(k)=(v_{1},v_{2},...v_{k})$ (14)

and the corresponding sum of distances as

$M_{\mbox{\it method}}^{*}\>(k)\;\doteq\;A(\>X_{\mbox{\it method}}\>(k)\>)$
(15)

with the intent that the relative error to the true solution is relatively
small:

$\frac{M_{\mbox{\it method}}\>(k)-M^{*}(k)}{M^{*}(k)}\;\ll\;1$ (16)

###  3.1 Degree ordering

Approximating the $k$-median solution as the top $k$ hubs of the network is
perhaps the most straightforward approach:

$X_{\mbox{\tt degree}}\>(k)\;\leftarrow\;\mathop{\mathrm{argmax}[k]}_{v\in
V}\mbox{deg}(v)$ (17)

The idea here is that the hubs (high-degree vertices) serve as efficient
spreaders since they are connected to large number of neighbors. This is
countered by the notion that there may be significant overlap among their
aggregate neighborhoods, i.e. $|N(a_{i})|+|N(a_{2})|+\ldots+|N(a_{k})|$ can be
significantly smaller than $|N(\\{a_{1},\ldots,a_{k}\\})|$ with other vertices
potentially covering the graph more effectively.

This is a common criticism of degree ordering for this problem, but our
experimental results show that this may not be as critical an issue in
practice (see Sec. 6).

###  3.2 Extended degree ordering

A more sophisticated approach is the extended degree ordering, which measures
the sum of degrees for neighboring vertices:

$\mbox{deg}^{+}(v)\>\doteq\>\sum_{x\in N(v)}\mbox{deg}(x)$ (18)

and uses the top $k$ values as an approximation of the $k$-median solution:

$X_{\mbox{\tt degree+}}\>(k)\;\leftarrow\;\mathop{\mathrm{argmax}[k]}_{v\in
V}\;\mbox{deg}^{+}(v)$ (19)

This is a semi-local algorithm, utilizing more information about the network’s
topology by analyzing the second-level neighborhood, i.e. neighbors of
neighbors. The motivation for this centrality measure is that it uses more
information about the graph topology and can lead to an improved metric for
identify candidate vertices for the set $S$.

###  3.3 PageRank ordering

PageRank is a variant of the eigenvalue centrality, which treats the network
as a flow graph and values vertices with high eigenvalues. It is the basis for
some commercial web search engines. [8]. Given a damping factor,
$0\leq\delta\leq 1$, the PageRank centrality is given as the convergence of
the iteration

$\mbox{PageRank}(v)\>=\>(1-\delta)\;+\;\delta\sum_{u\in
N(v)}\frac{\mbox{PageRank}(u)}{\mbox{deg}(u)}$ (20)

typically a value of $\delta=0.85$ is used in these calculations [8]. The
corresponding approximation for the $k$-median solution is

$X_{\mbox{{\tt PRank}{}}}\>(k)\;\leftarrow\;\mathop{\mathrm{argmax}[k]}_{v\in
V}\;\mbox{PageRank}(v)$ (21)

###  3.4 VoteRank ordering

A method developed by Zhang et.al. [7], is the VoteRank algorithm, which uses
an iterative voting methodology to determine the best influencer nodes. Each
vertex $i$ has a pair of values $(S_{i},T_{i})$ denoting the collective
(incoming) votes from neighbors $S_{i}$ and the number of (outgoing) votes to
give out in each voting round, $T_{i}$. At each voting round (complete pass
through the graph) a vertex with the maximum (incoming) vote score is selected
$(i^{*})$ and its $(S_{i}^{*},T_{i}^{*})$ values are set to zero, effectively
taking it out of future voting in subsequent rounds. The neighbors of vertex
$i^{*}$ have their respective $T_{i}$ votes reduced by a fixed value $f$, and
the process is repeated until $k$ vertices are found. In their paper, the
authors use $f=1/\langle d\rangle$, where $\langle d\rangle$ is the average
degree of the graph, and this value is fixed throughout the algorithm.
Typically, one would choose $f$ such that $kf\ll 1$ but this implementation
does not allow the $T_{i}$ values to go negative. An outline of the algorithm
is presented in Fig. 1. The $k$-median approximation is given by

$X_{\mbox{{\tt VRank}{}}}\>(k)\;\leftarrow\;\mathop{\mathrm{argmax}[k]}_{v\in
V}\;\mbox{VoterRank}(v)$ (22)

and we refer to this algorithm as VRank in the comparisons.

Data: Graph G=(V,E), $f$, $N$

Result: $R=(\mbox{VoterRank}(v_{1}),\ldots\mbox{VoterRank}(v_{N}))$

1 $S_{v}=\epsilon,\;T_{v}=1.0,\;\;\forall v\in V$ ;

2

3for  _$i=1$ to $N$_ do

4 for  _$v\in V$_ do

5 $S_{v}=\sum_{u\in N(v)}T_{u}$;

6

7 end for

8 $v^{*}=\mathop{\mathrm{argmax}}_{v\in V}S_{v}$ ;

9 $R_{i}=v^{*}$ ;

10 $S_{v^{*}}=0.0\;;\;T_{v^{*}}=0.0$ ;

11 for  _$v\in N(v^{*})$_ do

12 $T_{v}=\max(0.0,\;T_{v}-f)$;

13

14 end for

15

16 end for

17

Algorithm 1 outline of VoteRank algorithm

###  3.5  Coreness ordering

Another vertex centrality measure that has been proposed for finding effective
spreaders is based on the degeneracy of network graphs. The $i$-core of a
graph is collection of connected components that remain after all vertices
with degrees less than $n$ have been removed. (This is often referred to as
the $k$-core of a graph in the literature, but we use $i$ to avoid conflict
with the $k$ used in the $k$-median formulation.) To compute the $i$-core of a
graph, we remove all vertices of degree $i-1$ or less. This process is
repeated until there are no vertices of the graph with degrees less than $n$.
The notion here is that vertices in higher value $i$-cores represent the inner
backbone of the network, as opposed to lower-valued $i$-cores which lie at its
periphery, and serve as better-connected vertices to efficiently spread
information throughout the network. The core-number of a vertex is the largest
value $i$ which it belongs to the $i$-core of the graph.

Although one could use this centrality to identify candidate vertices [10],
one problem that has been noted is that the core values of the highest
vertices are often the same and hence are not distinguishable to form a proper
ordering [11]. To remedy this, a slightly extended centrality has been
proposed that replaces the $i$-shell value of a vertex with the sum of its
neighbors’ core-number. That is, if $c(v)$ is the core-number of $v$, then

$C(v)\;\doteq\;\sum_{u\in N(v)}c(u)$ (23)

$X_{\mbox{\tt core}}\>(k)\;\leftarrow\mathop{\mathrm{argmax}[k]}_{v\in
V}\;C(v)\;$ (24)

We refer to this algorithm as core.

###  3.6  Extended coreness ordering

Extensions to the $C(v)$ centrality have also been proposed [11] as an
improved measure for influence. In a similar manner to $\mbox{deg}^{+}$,
neighborhood coreness, or $\mbox{core}^{+}$, uses the values of its neighbor’s
core centrality.

$C^{+}(v)\;\doteq\;\sum_{u\in N(v)}C(u)$ (25)

$X_{\mbox{\tt core+}}\>(k)\;\leftarrow\;\mathop{\mathrm{argmax}[k]}_{v\in
V}\;C^{+}(v)\;$ (26)

We refer to this algorithm as core+.

###  3.7  H-index ordering

The Hirsch index or $H$-index [12], originally intended to measure the impact
of authors and journals by way of citations, has also been studied as
centrality to measure ranking of influence and its relation to other
centralities [13]. The original measure for an author or journal was
determined as the number of $n$ publications that have at least $n$ citations.
For example, an author with the following number of citations $[13,16,27,9,2]$
would have an $H$-index of 4. In terms of a network graph, the Hirsch index of
a vertex $v$, given as $H(v)$, can be represented as the maximal number of $n$
neighbors that each have at a degree of $n$ or more. That is, if $h(v,n)$ is
the number of neighbors of $v$ with degree at least $n$,

$h(v,n)\doteq\\{e\;|\;\mbox{deg}(e)\geq n,\;e\in N(v)\\}$ (27)

then

$H(v)\;\doteq\;\max_{n}\;\\{|h(v,n)|\geq n\\}$ (28)

The $k$-median approximation can be then be given as

$X_{\mbox{\tt H-index}}\>(k)\;\leftarrow\mathop{\mathrm{argmax}[k]}_{v\in
V}\;H(v)\;$ (29)

This algorithm is referenced as H-index.

###  3.8 Expected value (Random)

The mean average-distance of every $k$-element vertex set is simply the
expected value of all possible combinations:

$E^{*}(k)\doteq\frac{1}{\binom{|V|}{k}}\>\sum_{|S|=k}A(S)$ (30)

That is, the average value of a random guess chosen from a uniform
distribution of all $\binom{|V|}{k}$ possible sets. This can be computed
exactly by brute force for small networks and small $k$-values. For larger
cases, the expected value is approximated by sampling a finite subset of these
possibilities. The strong law of large numbers (SLT) guarantees this finite
approximation converges to the actual value as the number of subsets
indepentently samples from this distrubtion increase. One can then use the
Central Limit Theorem (CTL), which states that the mean of $N$ sample values
of $A(S)$ will tend towards a normal distribution, regardless if the sample
distribution itself is normal or skewed. If $\mu$ and $\sigma$ denote the mean
and standard deviation of the original samples, then the expected value and
deviation of the sample means of is given by $\mu^{*}=\mu$ and
$\sigma^{*}=\sigma/\sqrt{N}$, respectively. This typically holds true for
sample sizes $N\geq 30$, and we generally consider $N\approx 100$ for our
approximations. We use the notation $E(k)$ to the denote this approximation:

$E(k)\doteq\frac{1}{N}\>\sum_{i=1}^{N}A(S_{i})$ (31)

where $\\{|S_{i}|=k\\}$ and each $S_{i}$ is random set of $k$ vertices.

##  4 Experiments & Methodology

For these experiments, we focused on connected simple graphs that were
undirected, unweighted, with no self-loops or multi-edges. This represents the
least common denominator for graph topologies, as not all datasets have edge
weights and other metadata. Directed graphs were represented as undirected by
making each edge bi-directional. For disconnected networks, we used the
largest connected component. Additionally, the input networks had their
vertices renumbered to be contiguous for optimized operations, and therefore
did not necessarily match the vertex numbers in the original sources.

Table 1: Application network topologies used in this study (largest connected component of undirected graph). The average degree is $\langle d\rangle$ and the maximum degree is $\Delta$.  Network | Application | $|V|$ | $|E|$ | $\langle d\rangle$ | $\Delta$ | $\Delta/\langle d\rangle$
---|---|---|---|---|---|---
Zebra | animal contact network | 23 | 105 | 9.13 | 14 | 1.5
Dolphin | animal contact network | 62 | 159 | 5.13 | 12 | 2.3
Terrorist network | social network | 64 | 243 | 7.59 | 29 | 3.8
High School | social network | 70 | 274 | 7.83 | 19 | 2.4
MIT students | mobile social network | 96 | 2,539 | 52.90 | 92 | 1.7
Hypertext 2009 | social interaction | 113 | 2,196 | 38.9 | 98 | 2.5
Florida ecosystem wet | food network | 128 | 2,075 | 32.42 | 110 | 3.4
PDZBase | metabolic network | 161 | 209 | 2.59 | 21 | 8.1
Jazz | collaboration network | 198 | 2,742 | 27.79 | 100 | 3.6
GE_200 | top-level web graph | 200 | 1,202 | 12,02 | 124 | 10.3
Chevron_200 | top-level web graph | 200 | 5.450 | 54.50 | 189 | 3.5
Abilene218 | computer network | 218 | 226 | 2.07 | 10 | 4.8
Bethesda | top-level web graph | 255 | 422 | 3.31 | 81 | 24.5
C. Elegans | neural network | 297 | 2,148 | 14.46 | 134 | 9.3
NetScience | co-authorship | 379 | 914 | 4.82 | 34 | 7.0
Arenas-email | email communications | 1,133 | 5,451 | 9.62 | 71 | 7.4
FAA air traffic | infrastructure | 1,226 | 2,408 | 3.9 | 34 | 8.6
Human protein | protein interaction | 2,217 | 6,418 | 8.94 | 314 | 26.5
ca-GrQc | co-authorship | 4,158 | 13,422 | 6.46 | 81 | 12.5
ca-HepTh | co-autorship | 8,638 | 24,806 | 5.74 | 65 | 11.3
ca-HepPh | co-authorship | 11,204 | 117,619 | 23.38 | 491 | 21.0
ca-CondMat | co-authorship | 21,363 | 91,286 | 8.54 | 279 | 32.6
email-Enron | email communications | 33,696 | 180,811 | 10.73 | 1,383 | 128.9
cit-HepPh | citation network | 34,401 | 420,784 | 24.46 | 846 | 34.6
flickrEdges | online social network | 105,722 | 2,316,668 | 43.83 | 5,425 | 123.8
email-EuAll | email communications | 224,832 | 339,925 | 3.02 | 7,636 | 2,525.3
com-YouTube | online social network | 1,134,890 | 2,987,624 | 5.27 | 28,754 | 5,631.3
soc-Pokec | online social network | 1,632,803 | 22,301,964 | 27.32 | 14,854 | 543.8
soc-LiveJournal | online social network | 4,846,609 | 42,851,237 | 17.68 | 20,333 | 1,149.9

The dataset comprised a wide range of application areas, including social,
mobile, metabolic, neural, email, biological, and collaboration networks
listed in Table 1. Examples were collected from network databases Konect [14],
SNAP [15], and UC Irvine [16], as well as several webgraphs generated by
examining public websites. Network sizes ranged from less than 100 vertices
(for exact verification of k-median problems) to networks with over 1 million
vertices, with most networks containing several thousand vertices. This study
focused on 32 of these networks, comparing the eight algorithms from Section 3
for k-values from 1 to 100, resulting in roughly 25,000 experiments of graph,
algorithm, and k-value combinations. This provided a clearer view of the
performance landscape and algorithm behavior.

The evaluation occurred in three separate stages. First, we compared these
heuristics to the exact solution for small networks and small k-values, where
this could be computed by brute force. This established a baseline of how well
these algorithms performed and with an actual error measurement. Second, for
larger networks where a true solution was not feasible, we compared the
methods against each other. Finally, we compared the methods to the null model
of an expected value of A(S): the average solution obtained from a random
guess (Eq. 31).

Computational experiments were conducted on a desktop workstation, running
Ubuntu Linux 5.15.0-46, with an AMD Ryzen 7 1700x (8-core) processor running
at 3.4 GHz, and outfitted with 32 MB of RAM 111Certain commercial products or
company names are identified here to describe our study adequately. Such
identification does not imply recommendation or endorsement by the National
Institute of Standards and Technology, nor does it imply that the products or
names identified are necessarily the best available for the purpose.. The
algorithms were coded in C++, and compiled under GNU g++ 11.1.0 with the
following optimization and standardization flags: [-O3 -funroll-loops
-march=native -std="c++11"]. Modules were used from the NGraph C++ library and
Network Tookit [17], as well as optimized C++ implementations of algorithms
noted in the paper.

##  5 Results

The results of the computational experiments on real networks showed
significant variations. Despite claims made for any particular approach, we
did not see a single method consistently producing a winner in every case.
Instead, we were presented with trade-offs for varying network topologies.
Nevertheless, we were able to form general observations about the expected
behavior on classes of networks and provide some guidelines for choosing
appropriate methods.

###  5.1 Case study: distribution of $A(S)$

Figure 1: Distribution of average distances $A(S)$ for all $k$-element
subsets, $k=\\{2,3,4\\}$ in ca-netscience. Such example networks are used to
determine the accuracy of approximations to exact solutions.

To better understand the nature of the $k$-median problem, we can compute by
$A(S)$ by brute force for all of the $\binom{V}{k}$ $k-$element subsets. It is
a computationally expensive task, but insightful to appareciate the behavior
of the function we are optimizing over.

As an example, Figure. 1 illustrates the distribution of these values for of
the ca-netscience network [15], using various values of $k$. Here, $V=379$ and
each curve signifies the distribution of $A(S)$ values for every one the
possible $k$-element subsets. For instance, the $k=4$ curve represents the
distribution of all $\binom{379}{4}=846,153,126$ four-element subsets:

$\displaystyle S_{1}$ $\displaystyle=\\{1,2,3,4\\}$ $\displaystyle S_{2}$
$\displaystyle=\\{1,2,3,5\\}$ $\displaystyle S_{3}$
$\displaystyle=\\{1,2,3,6\\}$ $\displaystyle\vdots$ $\displaystyle
S_{846,153,126}$ $\displaystyle=\\{376,377,378,379\\}$

In finding the $k$-median solution, we are interested in the left-most
(minimum) $x$-value of the tail. As $k$ increases, its distribution graph
smooths out, as the number of samples points increase exponentially and begins
to look more like a continuous distribution. In this case, the optimal
$4$-median, $M(4)=2.20$, with an expected value of $E^{*}(4)=3.97$. as given
by Eq. (3) and Eq. (30), respectively.

Table 2: $k$-median and expected values for ca-netscience $k$ | $M^{*}(k)$ | $E^{*}(k)$ |  $E$(k) | $\frac{E^{*}(k)}{M^{*}(k)}$
---|---|---|---|---
1 | 3.90 | 6.04 | 6.01 | 1.55
2 | 2.97 | 4.90 | 4.91 | 1.65
3 | 2.53 | 4.33 | 4.31 | 1.71
4 | 2.20 | 3.97 | 3.95 | 1.80
5 | 2.08 | 3.70 | 3.69 | 1.79

Table 2 lists these values for $k=1,2,\ldots 5$. Here, the average random
guess can be less than twice the optimal $k$-median solution, which is a much
tighter result than for general problems. (As described in later sections,
this pattern is typical for complex networks.) Furthermore, this table shows
that the approximated expected value, $E(k)$ closely matches the exact value
within $\pm 0.5\%$ using the Central Limit Theorem with $N=100$.

###  5.2 Comparisons with optimal $k$-median solutions

For small networks, we compared the accuracy of the approximation algorithms
by running them for various values, up to $k=5$, except where limited by the
computation effort. Figure 2 illustrates the results for several small example
networks. The bar graphs show the computed approximations for
$k=\\{1,2,\ldots,5\\}$ for the methods listed in Section 3. This collection
illustrates several interesting patterns:

  * •

guessing a solution (random) performs, on average, within a factor of 2 from
optimal

  * •

for $k>2$ some approximation methods (degree+, core, core+, H-index) can
perform worse than random guessing

  * •

most methods (excluding random) stay within a 1.5 factor of optimal

  * •

VRank and PRank seem to be perform best, staying within 1.2 of optimal for
$1\leq k\leq 5$.

  * •

core, core+, and H-index, typically perform worse, underperformed only by
random

Although some networks exhibited slightly different behavior, these are the
common patterns. We explore these characteristics in Sec. 5.3.

(a) ca-netscience network: VRank, and PRank perform well but others are worse
than random guessing.

(b) C Elegans network: methods work well but H-index performs substantially
worse.

(c) Abilene218 network: PRank performs poor and not much better than random
guessing.

(d) USAir87 network: approximation methods perform better than random
guessing.

Figure 2: Comparison of approximation methods to exact $k$-median solutions
for smaller networks.

Compared to ca-netscience, the other networks appear better behaved. The  C.
Elegans network (Fig. 2(b)) for example, shows extremely good approximations
(relative error less than 5%) for all methods, except for random and H-index.

In the Abilene218 network (Fig. 2(c)) we encounter quite different behavior:
the PRank method performs substantially worse than every other one, except
random guessing. This is in sharp contrast to other examples, where VRank and
PRank methods perform similarly and are often beat out other algorithms.

Table 3: Average error (%) to true-optimal for small graphs ($1\leq k\leq 5$) Network | random | degree | degree+ | VRank | PRank | core | core+ | H-index
---|---|---|---|---|---|---|---|---
Abilene218 | 68.9 | 11.1 | 3.4 | 10.2 | 54.0 | 4.4 | 3.4 | 8.4
USAir87 | 60.0 | 2.6 | 2.7 | 2.6 | 3.1 | 2.7 | 2.7 | 10.7
ca-HepTh | 46.4 | 4.7 | 5.8 | 4.7 | 4.7 | 26.2 | 26.2 | 34.9
ca-netscience | 68.6 | 32.7 | 65.3 | 18.0 | 17.0 | 56.0 | 67.0 | 66.8
celegans | 50.2 | 1.8 | 2.1 | 1.8 | 3.3 | 1.8 | 2.1 | 25.9
faa | 48.4 | 10.7 | 5.0 | 10.7 | 8.9 | 4.8 | 5.3 | 12.6
foodweb_florida_wet | 53.8 | 5.6 | 5.6 | 5.6 | 5.6 | 5.6 | 5.6 | 5.0
hypertext_2009 | 38.8 | 3.3 | 0.6 | 3.0 | 3.3 | 0.6 | 0.6 | 7.5
jazz | 43.7 | 7.7 | 10.1 | 7.7 | 5.8 | 10.1 | 10.1 | 15.0
pdzbase | 64.3 | 10.7 | 22.9 | 10.7 | 10.7 | 20.0 | 14.2 | 32.6
Table 4: Ranking of methods by actual error (%) in small graphs: average relative errors for each method in Table 3 method | error (%)
---|---
VRank | 7.5
degree | 9.1
PRank | 11.6
degree+ | 12.3
core | 13.2
core+ | 13.7
H-index | 21.9
random | 54.3

Finally, the USAir87 network (Figure 2(d)) illustrates that the approximation
algorithms are capable of calculating good-quality solutions (even H-index)
that are significantly better than random guessing.

Table 3 provides a tabular form of similar results from a larger study of 10
networks. From this data we see that the behavior of these methods on real
networks can vary significantly. Ignoring random and H-index momentarily, the
remaining competitive methods can be quite accurate for these networks. For
example, C Elegans, hypertext_2009, USAir87 and foodweb_florida_wet all
exhibit approximations that are within 5% of optimal.The ca-netscience network
was the sole outlier, with the best methods of the group exhibiting roughly a
20% error.

Taking the average error for each method across the networks we arrive at
(Table 4) illustrating that VRank performed the best overall, with the other
methods not too far behind. In this experiment, degree+, core, and core+ did
not perform as badly, while H-index and random fared significantly worse. This
table represents the anaylis for small network comparisons with exact
solutions. It illustrates that the top methods generally work quite well,
typically within 10% to 20% of optimal and seem reasonable candidates for
testing on larger networks.

###  5.3 Analysis of larger networks

(a) Amazon0302: methods perform similar and an improvement over random
guessing.

(b) ca-HepTh: core, core+, and H-index algorithms perform worse than random.

(c) hypertex-2009: core+ closely outperforms most methods.

(d) jazz: PRank closely outperforms VRank and most other methods.

(e) ca-GrQc: degree falls behind random for $k>25$.

(f) roadNet-PA: methods perform about as good as guessing and H-index is 5x
worse.

Figure 3: Comparison of approximation methods to expected mean value of $A(S)$
for larger networks.

This section describes the core of the study which focuses on larger networks
more typical of modern datasets. In such cases, the optimal solution is
unknown and we use the expected value of a random guess to gauge the quality
of the approximations. Similarly to the smaller network examples, the
expected-value random provides solutions that are typically within a factor of
two of optimal, so the bound can be useful in providing a practical measure.
As we shall see, a random guessing can sometimes outperform more sophisticated
algorithms (although such occurrences are uncommon).

In short, the outcome of the approximation algorithms on real network data
yield mixed results, and examples can be found to substantiate nearly any
hypothesis. As an illustration, we have listed several observations together
with the specific network examples to substantiate that claim. In short, one
can substantiate incomplete(and sometimes conflicting) hypotheses by simply
choosing the appropriate network examples:

  * •

all approximation methods yield similar results: figure 3(a) illustrates an
example of the amazon0302 network, where all approximation methods yield near
identical results and there is little discernible quality difference between
methods. Networks that exhibit this behavior include as20000102, chevron-
top200, com-YouTube, dlmf, email-Enron, p2p-Gnutalla31, soc-Epinions, soc-
Slashdot0922, wiki-Vote.

  * •

random sometimes may out-perform heuristics: Figure 3(b) demonstrates the ca-
HepTh network where several algorithms (core, core+, H-index) perform
substantially worse than expected value. Other networks experienced similar
behavior, where one or more methods performed worse than random guessing: ca-
GrQc, ca-HePh, caj-GrQc, ca-netscience, faa, and pdzbase .

  * •

core+ can may outperform other methods: despite the relative poor performance
of core+ there are (rare) instances where it is competitive with other methods
and retains a slight advantage for small $k$ values. One such example is the
hypertext-2009 network, as shown in Fig. 3(c). It should be noted that this
network is rather well-connected, with an $M(k)$ values less than 1.7, even
for small $k$. The $k$-median approximation quickly goes to 1.0 (the minimum)
for $k>5$.

  * •

best methods sometimes dependent on $k$ values: network email-EuAll
demonstrates an example where core and degree+ algorithms perform best for
small $k$, but are surpassed by VRank and PRank for $k>20$.

  * •

PRank and VRank often perform equally well: despite the criticism of PRank for
these types of problems, in practice it often performs just as good as VRank.
Example networks exhibiting this behavior include as20000102, bethesda, ca-
CondMat, ca-GrQc, ca-netscience, faa, and human-protein. Figure 3(d)
illustrates the jazz network, where PRank slightly outperforms VRank.

  * •

degree may performs worse than random: although the degree algorithm typically
performs quite well, it can fall behind random guessing in rare instances. The
ca-GrQc network (Fig. 3(e)) exhibits such behavior. Note that this network
proved difficult for the H-index, core, and core+ algorithms as well.

  * •

H-index typically worst performer: although not specifically design for this
purpose, H-index has become a popular centrality in the publishing industry
and is often cited as a measure of importance for spreading information.
Unsurprisingly, it often comes in last (slightly better than random guessing)
but sometimes it can completely miss the mark. In the roadNet-PA network, for
example, it is roughly five times worse than random (Fig. 3(f)).

###  5.4 Case studies: million-node networks

Here we focus on three larger examples with millions of vertices and edges
used in the study of large social networks [18]. Figure 4(a) illustrates the
larger YouTube network (V=1,134,890 E=2,987,624) where the various heuristics
perform about the same: roughly 35% better than a random guess. In this case,
all methods yield nearly identical values, and one can simply use the fastest
one (degree) to generate competitive results.

Table 5 lists the how each method ranked in the top 1%, 10%, and 100% of
solutions. For example, degree scored in the top 10% solutions about 3/4 of
the time, while random guessing always remained within a factor 2 of the best
solution.

Table 6 illustrates the cost trade-off between computation time and solution
quality. Using the fastest method (degree) as a reference, we see that VRank
and PRank provided the best solutions, but at a computational cost of nearly
three orders of magnitude.

Table 5: Percentage of cases where each method scored within $x\%$ of best solution $(k={1,\ldots,100}$) for million-vertex network (YouTube). Nearly all methods are within a factor of two of best solution. method | 0% (best) | 1% | 10% | 100%
---|---|---|---|---
degree | 12.5 | 24.0 | 75.7 | 100.0
degree+ | 8.5 | 11.5 | 42.7 | 99.9
VRank | 20.4 | 44.2 | 91.9 | 100.0
PRank | 18.5 | 33.7 | 91.6 | 100.0
core | 9.1 | 15.5 | 50.1 | 99.0
core+ | 6.3 | 8.7 | 41.0 | 97.8
H-index | 3.9 | 6.0 | 39.7 | 95.5
random | 0.6 | 3.1 | 12.3 | 99.4
Table 6: Relative computation cost for large graph (YouTube network) with over 1 million vertices and 3 million edges, together with overall performance within 10% of best solution. method | cost factor | quality
---|---|---
degree | 1.0 | 75.7
degree+ | 13.5 | 42.7
core | 50.3 | 50.1
core+ | 112.8 | 41.0
H-index | 259.1 | 39.7
PRank | 485.7 | 91.9
VRank | 736.1 | 91.6

Similar results are seen for the soc-pokec social network (V=1,632,803,
E=22,301,964) in Fig. 4(b). From these two examples, one may be tempted to
conclude that the algorithms perform equally well for large networks. However,
computations for the LiveJournal social network (V=4,846,609 E= 42,851,237) in
Fig. 4(c) show a significant difference between various methods, with PRank,
VRank, and degree performing better than most other heuristics and roughly 30%
better than random.

(a) network com-YouTube $(V\approx 1.1M,\>E\approx 3.0M)$

(b) network soc-pokec $(V\approx 1.6M,\>E\approx 22.3M)$

(c) network LiveJournal $(V\approx 5M,\>E\approx 43M)$ where PRank, VRank, and
degree algorithms perform significantly better

Figure 4: Comparison of approximation methods for large online social
networks.

###  5.5 Overall results

Table 7 describes the overall performance of approximation algorithms on the
32 networks under consideration. The values are described as relative error to
the best solution for each method. For example, a value of 10 signifies that
particular method performed on average within 10% above the best possible
heuristic for each $k$ from one to one hundred.

Table 8 presents the same results, based on their rankings, with the first
place highlighted. From here we see that VRank and PRank come in first and
second position, respectively, for the majority of cases while degree comes in
a close third position.

Table 10 summarizes these results, where we compute the overall error of each
method from the best solution for each $k$-value. For example, degree is
typically about 5% greater than the best solution, while random produced, on
average, a solution that was less than 50% greater than the best algorithm.

Table 7: Quality of methods for large graphs ($k=1,2,\ldots 100$). Relative performance ( %) from best solution. A value of 10 signifies that on average that method performed 10% above best possible value from all heuristics. Network | degree | degree+ | VRank | PRank | core | core+ | H-index | random
---|---|---|---|---|---|---|---|---
Abilene218 | 8.2 | 11.1 | 3.2 | 10.1 | 8.6 | 12.8 | 13.4 | 79.7
USAir87 | 10.0 | 18.1 | 0.4 | 1.8 | 18.0 | 18.9 | 19.7 | 43.7
amazon0302 | 0.5 | 3.0 | 0.3 | 0.4 | 0.8 | 3.0 | 3.9 | 48.0
areans_email | 3.3 | 9.4 | 0.0 | 0.8 | 7.3 | 11.1 | 10.9 | 30.9
as20000102 | 1.4 | 12.5 | 0.0 | 0.5 | 4.5 | 11.4 | 7.0 | 76.1
bethesda | 3.6 | 10.9 | 0.8 | 1.5 | 17.4 | 11.5 | 40.7 | 76.8
ca-CondMat | 4.3 | 11.3 | 1.3 | 0.0 | 11.6 | 13.9 | 12.6 | 40.0
ca-GrQc | 40.1 | 51.3 | 1.3 | 1.4 | 51.7 | 51.7 | 56.2 | 37.9
ca-HepPh | 11.7 | 13.1 | 1.4 | 1.1 | 14.1 | 14.7 | 16.6 | 20.2
ca-HepTh | 4.8 | 21.1 | 0.2 | 0.9 | 61.5 | 63.0 | 47.4 | 34.4
ca-netscience | 12.6 | 34.9 | 0.3 | 3.2 | 35.6 | 59.5 | 48.0 | 50.9
celegans | 0.9 | 6.9 | 0.1 | 0.9 | 1.6 | 6.6 | 7.8 | 25.0
chevron_top200 | 0.0 | 0.5 | 0.0 | 0.0 | 0.5 | 1.1 | 1.1 | 7.8
cit-HepPh | 3.2 | 11.3 | 2.3 | 0.0 | 8.8 | 15.2 | 18.8 | 38.6
com-youtube | 0.8 | 2.7 | 0.1 | 0.4 | 2.5 | 3.2 | 3.6 | 51.3
dlmf | 3.1 | 7.6 | 0.0 | 2.0 | 8.5 | 7.5 | 8.3 | 67.2
email-Enron | 2.7 | 11.6 | 0.7 | 0.4 | 9.0 | 12.1 | 13.3 | 59.1
email-EuAll | 2.4 | 11.8 | 2.4 | 3.2 | 5.0 | 10.5 | 12.5 | 66.9
faa | 8.6 | 31.0 | 0.7 | 1.8 | 18.0 | 41.1 | 30.8 | 40.3
flickrEdges | 8.2 | 79.4 | 2.3 | 0.5 | 88.8 | 89.2 | 89.5 | 35.6
foodweb_florida_wet | 0.1 | 0.6 | 0.1 | 0.1 | 0.4 | 0.7 | 1.5 | 8.7
ge_top200 | 3.0 | 14.3 | 0.3 | 0.3 | 9.4 | 17.4 | 22.8 | 36.0
human_protein_gcc | 2.7 | 30.4 | 0.1 | 1.3 | 6.2 | 30.0 | 20.6 | 58.4
hypertext_2009 | 0.3 | 0.0 | 0.3 | 0.3 | 0.0 | 0.0 | 0.8 | 8.5
jazz | 5.1 | 12.4 | 1.2 | 0.1 | 14.2 | 14.8 | 13.6 | 11.2
p2p-Gnuetalla31 | 0.3 | 1.5 | 0.0 | 1.5 | 0.6 | 2.6 | 5.5 | 32.3
pdzbase | 7.1 | 69.6 | 0.1 | 3.7 | 19.3 | 70.9 | 55.2 | 71.1
roadNet-PA | 8.8 | 17.5 | 8.7 | 1.2 | 19.1 | 32.1 | 351.3 | 3.5
soc-Epinions | 1.2 | 4.0 | 0.1 | 0.2 | 3.3 | 4.4 | 5.0 | 48.8
soc-Slashdot0922 | 0.8 | 1.8 | 0.2 | 0.5 | 1.1 | 2.8 | 3.6 | 45.8
web-Stanford | 2.2 | 21.3 | 0.8 | 0.7 | 12.4 | 20.9 | 26.5 | 37.0
wiki-Vote | 1.6 | 2.0 | 0.6 | 0.1 | 2.8 | 2.0 | 2.2 | 38.5
Table 8: Ranking of k-median approximations Network | degree | degree+ | VRank | PRank | core | core+ | H-index | random
---|---|---|---|---|---|---|---|---
Abilene218 | 5 | 2 | 1 | 7 | 3 | 4 | 6 | 8
USAir87 | 3 | 4 | 1 | 2 | 5 | 6 | 7 | 8
amazon0302 | 3 | 5 | 1 | 2 | 4 | 6 | 7 | 8
areans_email | 3 | 5 | 1 | 2 | 4 | 7 | 6 | 8
as20000102 | 3 | 7 | 1 | 2 | 4 | 6 | 5 | 8
bethesda | 3 | 4 | 1 | 2 | 6 | 5 | 7 | 8
ca-CondMat | 3 | 4 | 2 | 1 | 5 | 7 | 6 | 8
ca-GrQc | 3 | 4 | 2 | 1 | 5 | 6 | 8 | 7
ca-HepPh | 3 | 4 | 2 | 1 | 5 | 6 | 7 | 8
ca-HepTh | 3 | 4 | 1 | 2 | 7 | 8 | 6 | 5
ca-netscience | 3 | 5 | 1 | 2 | 4 | 8 | 6 | 7
celegans | 2 | 6 | 1 | 3 | 4 | 5 | 7 | 8
chevron_top200 | 1 | 4 | 2 | 3 | 5 | 6 | 7 | 8
cit-HepPh | 3 | 5 | 2 | 1 | 4 | 6 | 7 | 8
com-youtube | 3 | 5 | 1 | 2 | 4 | 6 | 7 | 8
dlmf | 3 | 5 | 1 | 2 | 7 | 4 | 6 | 8
email-Enron | 3 | 5 | 2 | 1 | 4 | 6 | 7 | 8
email-EuAll | 5 | 3 | 6 | 7 | 1 | 2 | 4 | 8
faa | 3 | 5 | 2 | 1 | 4 | 7 | 6 | 8
flickrEdges | 3 | 5 | 2 | 1 | 6 | 7 | 8 | 4
foodweb_florida_wet | 3 | 5 | 1 | 2 | 4 | 6 | 7 | 8
ge_top200 | 3 | 5 | 1 | 2 | 4 | 6 | 7 | 8
human_protein_gcc | 3 | 7 | 1 | 2 | 4 | 6 | 5 | 8
hypertext_2009 | 5 | 1 | 4 | 6 | 2 | 3 | 7 | 8
jazz | 3 | 4 | 2 | 1 | 5 | 6 | 7 | 8
p2p-Gnuetalla3 | 2 | 4 | 1 | 5 | 3 | 6 | 7 | 8
pdzbase | 3 | 7 | 1 | 2 | 4 | 6 | 5 | 8
roadNet-PA | 4 | 6 | 3 | 1 | 5 | 7 | 8 | 2
soc-Epinions | 3 | 5 | 1 | 2 | 4 | 6 | 7 | 8
soc-Slashdot0922 | 4 | 5 | 1 | 3 | 2 | 6 | 7 | 8
web-Stanford | 3 | 6 | 2 | 1 | 4 | 5 | 7 | 8
wiki-Vote | 3 | 4 | 2 | 1 | 7 | 5 | 6 | 8
Table 9: Efficiency of k-median approximations on large networks: computation time (secs) Network | degree | degree+ | VRank | PRank | core | core+ | H-index | random
---|---|---|---|---|---|---|---|---
soc-LiveJournal | 0.01 | 0.8 | 50.8 | 35.2 | 5.4 | 11.5 | 5.6 | 166.9
soc-pokec | 0.01 | 0.5 | 24.4 | 20.0 | 2.2 | 4.7 | 3.28 | 62.5
com-youtube | 0.01 | 0.04 | 2.1 | 1.4 | 0.1 | 0.32 | 0.75 | 7.0
Table 10: Ranked performance of k-median approximations. A value of $x$ signifies that $M_{\mbox{\it method}}\>(k)$, on average, was within $x\%$ of the best solution for each graph and k-value combination from Table 7. method | performance (%)
---|---
VRank | 0.9
PRank | 1.3
degree | 5.1
core | 14.4
degree+ | 16.7
core+ | 20.5
H-index | 30.3
random | 41.6

##  6 Conclusion

We have compared eight $k$-median approximation methods for various $k$-values
(typically 1 to 100) on 32 networks over a diverse range of application areas.
After conducting thousands of experiments, we have observed patterns and
formulated guidance for solving the k-median problem on a broad range of
application network problems.

Overall, these approximation algorithms are efficient and some can produce
good-quality solutions on complex networks. However, they cannot replace
traditional methods[5] for general graphs that do not exhibit heavy-tailed
degree distributions. These skewed distributions often lead to small-world
topologies, where the largest distance between vertices grows slowly compared
to the size of the graph. In short, a vertex is typically not far from a large
hub, quickly covering the graph and collapsing distances. In fact, the
expected value of $E(k)$ for $k=1$ is simply the average distance from any one
vertex to the remainder of a given network topology, which is typically less
than 6 in our experiments, thus providing another empirical demonstration of
the “six degrees of separation” phenomena [19].

We have demonstrated that the algorithms in this study can indeed yield high-
quality results on smaller networks where we can compute the optimal solution
explicitly (Sec. 5.2, Tbl.4) with degree, VRank, and PRank achieving roughly a
1.1 factor of the true solution. By contrast, the best algorithms for general
graphs provide a guaranteed factor of 3 or higher.

For larger networks, the exact optimal solution is not computationally
tractable and we can only compare the approximation methods against
themselves. As Sec. 5.3 illustrates, one may reach an incomplete or premature
conclusions by examining only a small number of networks. Exploring a larger
and more diverse dataset, however, reveals certain patterns that aid in
algorithm choices.

Like many approximation heuristics, the practical question comes down to a
trade-off between performance (computational cost) and quality of solution. If
one is willing to accept a factor of 2 from the best methods, then simply
choosing $k$ random vertices from an uniform distribution may suffice. (This
may come as a unexpected result, as hard problems typically do not behave in
this manner.) If a higher quality solution is needed, we can consult Tbl. 10
which summarizes the results of roughly 25,000 experiments. Here we see that
VRank and PRank perform, on average, within about a 1.01 factor of the best
method in every $k$-value in the [1:100] range. The simple degree method
yields results on average within about 1.05 factor of the best method while
exhibiting a performance speedup of three orders of magnitude over VRank and
PRank.

Thus, we can form a general best-practices guide for choosing the appropriate
algorithms:

  * •

if a quality factor of 2 is sufficient, choose $k$ random vertices from
uniform distribution (random)

  * •

if a better quality solution is needed, choose the top $k$ hubs (degree)

  * •

if quality still not sufficient, use VRank or PRank for slight improvement (at
a $10^{2}$ to $10^{4}x$ computational cost)

In practice, these approximation algorithms remain efficient, even for
networks containing millions of elements. The more expensive algorithms
(VRank, PRank) require about a minute to approximate $k$-median solutions for
up to $k=100$ on a personal computer (Tbl. 9). Thus, one possible approach
would create an amalgamate super-algorithm which would run the seven methods
(degree, degree+, VRank, PRank, core, core+, H-index) concurrently and choose
the best one for each $k$-value. A final step could compare this to the
expected value (random) to give an indication how well the approximation
methods have improved the solution.

In summary, the methods presented here do a reasonable job at estimating the
$k$-median problem on complex networks. Despite the challenges of this
fundamental problem, these methods provide a reasonable approximation and can
be used efficiently to formulate approximations to this important problem,
providing researchers with practical tools in studying large-scale complex
networks.

## References

  * [1] Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. _Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining_ , , pp 137–146.
  * [2] Granovetter M (1978) Threshold models of collective behavior. _American journal of sociology_ 83(6):1420–1443.
  * [3] Hethcote HW (2000) The mathematics of infectious diseases. _SIAM review_ 42(4):599–653.
  * [4] Kariv O, Hakimi SL (1979) An algorithmic approach to network location problems. i: The p-centers. _SIAM journal on applied mathematics_ 37(3):513–538.
  * [5] Reese J (2006) Solution methods for the p-median problem: An annotated bibliography. _Networks_ 48(3):125–142. https://doi.org/https://doi.org/10.1002/net.20128. https://onlinelibrary.wiley.com/doi/pdf/10.1002/net.20128 Available at https://onlinelibrary.wiley.com/doi/abs/10.1002/net.20128
  * [6] Arya V, Garg N, Khandekar R, Meyerson A, Munagala K, Pandit V (2001) Local search heuristic for k-median and facility location problems. _Proceedings of the thirty-third annual ACM symposium on Theory of computing_ , , pp 21–29.
  * [7] Zhang JX, Chen DB, Dong Q, Zhao ZD (2016) Identifying a set of influential spreaders in complex networks. _Scientific Reports_ 6(1):27823. https://doi.org/10.1038/srep27823. Available at https://doi.org/10.1038/srep27823
  * [8] Newman M (2018) _Networks_ (Oxford university press), .
  * [9] Porter MA, Gleeson JP (2016) _Dynamical Ssystems on Networks_ (Springer Internationl Publishing), .
  * [10] Kitsak M, Gallos LK, Havlin S, Liljeros F, Muchnik L, Stanley HE, Makse HA (2010) Identification of influential spreaders in complex networks. _Nature physics_ 6(11):888–893.
  * [11] Bae J, Kim S (2014) Identifying and ranking influential spreaders in complex networks by neighborhood coreness. _Physica A: Statistical Mechanics and its Applications_ 395:549–559. https://doi.org/https://doi.org/10.1016/j.physa.2013.10.047. Available at https://www.sciencedirect.com/science/article/pii/S0378437113010406
  * [12] Hirsch JE (2010) An index to quantify an individual’s scientific research output that takes into account the effect of multiple coauthorship. _Scientometrics_ 85(3):741–754. https://doi.org/10.1007/s11192-010-0193-9. Available at https://doi.org/10.1007/s11192-010-0193-9
  * [13] Lü L, Zhou T, Zhang QM, Stanley HE (2016) The h-index of a network node and its relation to degree and coreness. _Nature Communications_ 7(1):10168. https://doi.org/10.1038/ncomms10168. Available at https://doi.org/10.1038/ncomms10168
  * [14] Kunegis J (2013) Konect - The Koblenz Network Collection. _Proceedings of the International Web Observatory Workshop_ (Boston, MA), , pp 1343–1350. Available at http://konect.uni-koblenz.de/networks.
  * [15] Leskovec J, Krevl A (2014) Snap datasets: Stanford Large Network Dataset collection. Available at http://snap.stanford.edu/data.
  * [16] DuBois CL (2008) UCI Network Data Repository, University of California, School of Information and Computer Sciences, Irvine, CA. Available at http://networkdata.ics.uci.edu.
  * [17] Pozo R (2019) NGraph Network Toolkit. Available at https://math.nist.gov/R̃Pozo/ngraph.
  * [18] Mislove A, Marcon M, Gummadi KP, Druschel P, Bhattacharjee B (2007) Measurement and Analysis of Online Social Networks. _Proceedings of the 5th ACM/Usenix Internet Measurement Conference (IMC’07)_ (San Diego, CA), , .
  * [19] Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’networks. _nature_ 393(6684):440–442. https://doi.org/10.1038/30918


1]Department of Engineering Design and Teaching Innovation, University of
Ottawa, 800 King Edward Avenue, Ottawa, K1N6N5, Canada 2]Department of
Software Engineering, University of Rostock, Albert-Einstein-Straße, Rostock,
18057, Germany 3]Department of Computer Science, University of Antwerp,
Middelheimlaan 1, 2020, Antwerp, Belgium 4]Department of Mathematics and
Computer Science, Eindhoven University of Technology, De Zaale, 5600 MB,
Eindhoven, The Netherlands 5]Department of Computer Science, NOVA School of
Science & Technology, Campus de Caparica, 2829-516 Caparica, Portugal
6]Institute of Software Engineering and Languages, Ulm University, James-
Franck-Ring, 89081, Ulm, Germany 7]SMT-EMI6, Carl Zeiss SMT GmbH, Rudolf-Eber-
Straße 2, 73447, Oberkochen, Germany 8]XITASO GmbH, Austraße 35, 86153,
Augsburg, Germany 9]Instituto Universitario Mixto de Tecnología Informática,
Universitat Politècnica de València, Camino de Vera s/n, 46022 Valencia, Spain

# Systematizing Modeler Experience (MX) in Model-Driven Engineering Success
Stories

Reyhaneh Kalantari<EMAIL_ADDRESS>Julian Oertel
<EMAIL_ADDRESS>Joeri Exelmans<EMAIL_ADDRESS>Satrio Adi Rukmono<EMAIL_ADDRESS>Vasco Amaral<EMAIL_ADDRESS>Matthias Tichy<EMAIL_ADDRESS>Katharina Juhnke
<EMAIL_ADDRESS>Jan-Philipp Steghöfer  jan-
<EMAIL_ADDRESS>Silvia Abrahão<EMAIL_ADDRESS>[  [  [  [
[  [  [  [  [

###### Abstract

Modeling is often associated with complex and heavy tooling, leading to a
negative perception among practitioners. However, alternative paradigms, such
as everything-as-code or low-code, are gaining acceptance due to their
perceived ease of use. This paper explores the dichotomy between these
perceptions through the lens of “modeler experience” (MX). MX includes factors
such as user experience, motivation, integration, collaboration & versioning
and language complexity. We examine the relationships between these factors
and their impact on different modeling usage scenarios. Our findings highlight
the importance of considering MX when understanding how developers interact
with modeling tools and the complexities of modeling and associated tooling.

###### keywords:

MDE, user experience, UX

##  1 Introduction

Model-driven engineering (MDE) is recognized as an established approach for
developing complex software systems [1] bringing advantages during software
system’s development. However, its adoption is currently hindered by a range
of factors [2], including poor tool support and its usability [3], social and
organizational issues, and a mismatch between technical and research
requirements [2].

As developers engage in the intricate task of modeling, whether for data,
systems, or simulations, evidence from practice shows that their experiences
diverge from conventional academic practices or guidelines. In [4], the
authors first introduce the term User eXperience (UX) for MDE or _Modeler
Experience (MX)_. MX goes beyond the traditional definition of usability to
include experience that includes individual feelings, such as emotions,
affects, motivations, and values in the process of modeling, playing a crucial
role in the success and adoption of MDE approaches. This paper takes the
initial steps towards developing a theory of MX, as called for in the original
work by Abrahão et al. [4].

Taking the above definition one step further, we argue that MX is not only
about the modeling language, tools or individual perspectives, but also about
how modeling is embedded in the organization and the mindset of the
individuals. It can, therefore, be a tool to address the mindset barriers
reported by Kalantari and Lethbridge [5].

A fundamental insight is that modeler experience depends on the concrete
context and circumstances in which modeling is used. This is in line with the
principles of Context-Driven Software Engineering, where Briand et al. [6]
advocate for the importance of considering contextual factors, whether human
(e.g., modelers background and experience), organizational (e.g., time and
cost constraints) or domain-related (e.g., level of criticality, compliance
with standards) when introducing a specific approach in an industrial setting.
For example, organizations that use model-based systems engineering (MBSE),
e.g., to build automotive products, have a very different approach and mindset
towards modeling than organizations where modeling is only done informally and
not enforced by process descriptions or similar measures. Therefore, another
objective of this work is to identify scenarios where modeling has proven
successful, based on existing literature and our collective experience on the
topic, and to distill future usage scenarios based on successful industrial
practices.

Based on the work of Bucchiarone et al. [7], we regard the modeling success
stories of MBSE, low-code, and informal modeling and add infrastructure-as-
code as an additional success story. To gain a better understanding of
informal modeling, we differentiate semi-formal modeling from it. Overall, we
are thus regarding five success stories in this paper:

  * •

Infrastructure-as-Code (IaC) aligns with the definition of modeling as the
creation of system representations, where the models are embedded within the
code itself. According to Madni et al. [8], a model can take various forms,
including modeling languages, algorithms, equations, and parametric curves.
This perspective offers a unified approach to both modeling and programming,
suggesting that “programs are models,” where code is viewed as a less
abstract, textual model [9]. In this context, users are not necessarily aware
that they are modeling. Domain-Specific Languages (DSLs) are mostly
implemented as textual languages and take advantage of features of the usual
tools/IDEs for programming, like automation and version control. Although
these languages are not agnostic of the specificities of different tools, one
might argue that IaC is already an abstraction with inherent structure and
intentionality, reflecting a specific system deployment. We add IaC as it is a
success story for the use of domain-specific languages, especially in a
programming context.

  * •

Low-code is an emerging paradigm combining modeling and graphical programming.
There are claims that Low-code is not MDE according to [10], or that it is
[11]. In this work, we follow the latter. Low-code platforms are modeling
environments in which a user combines different pre-defined building blocks
into an overall workflow. They are often used to model and automate simple
processes or to create dashboards to visualise data. Examples of such
platforms are Node-RED111https://nodered.org or
Outsystems222https://www.outsystems.com/.

  * •

MBSE in the Automotive Domain uses models intensively for systematically
developing and analyzing complex automotive systems architectures with
dedicated modeling frameworks. In this domain, the most commonly used
languages are UML and SysML to represent the structure of the software
architecture at a high level of abstraction and to describe the system’s
behaviour via state machines. Stateflow/Simulink models are also used to
represent subsystems which involve I/O and control design.

  * •

Informal Modeling produces models which are sketches with no or little
structure that have no direct or automatic translation to code. The main
objective is to gain a collective understanding of some problem domain, while
engaging in intensive communication.

  * •

Semi-formal Modeling produces models which are possibly created with CASE
tools or diagrammatic tools such as draw.io, sometimes with limited automatic
analysis or code generation capabilities.

The primary objective of this expert voice is to introduce factors that
contribute to MX and their interrelations in the four identified modeling
success stories. Moreover, it outlines how the identified factors impact the
modeling success stories. This work results from the week-long GI-Dagstuhl
Seminar on “Human Factors in Model-driven Engineering” attended by researchers
and practitioners experts in the topics of model-driven engineering and human
factors [12]. The ultimate objective of this work is to contribute to
designing and developing better MDE tools by understanding the MX factors that
ultimately hinder MDE adoption.

This paper is structured as follows. In Section 2, we define and detail the
five modelling success stories mentioned before. In Section 3, we introduce
the relevant factors that influence MX. In Section 4, we analyze the five
success stories in light of the factors identified. Finally, in Section 5, we
discuss the results and outline the research challenges and opportunities
related to MX.

##  2 Selected Modeling Success Stories

Bucchiarone et al. [7] introduce three modeling success stories as diverse but
archetypal instances of successful applications of modeling. Due to their
diversity, they exhibit a broad set of characteristics that influence the
modeler’s experience differently. Therefore, it is important to elicit the
characteristics of each success story and analyze the extent to which they
influence MX. As stated above, we also consider infrastructure-as-code as a
modeling success story and consider it as such in the following.

Table LABEL:tab:modeling-workflows presents the characteristics that define
each modeling success story. These characteristics help to understand the
differences and commonalities of the identified success stories. At this
stage, we do not consider the list of characteristics to be complete but
sufficient to show that the success stories are different enough to warrant a
separate treatment.

The mapping in Table LABEL:tab:modeling-workflows shows that the chosen
success stories already provide a significant diversity in terms of the
characteristics we have selected. This means they provide a sufficient
difference regarding what modeler experience means in each of them and,
ultimately, how they impact the factors of modeler experience as we describe
in Section 4.

##  3 Factors of Modeler Experience

In this section, we first describe the methodology we have followed to
identify a set of factors that affect the modeler’s experience. We then
present these factors grouped by inherent factors, technical factors, and non-
technical factors.

#### Methodology

We conducted a focus group with ten modeling experts from academia and
industry to better understand the factors contributing to MX. The starting
point of the focus group was a discussion of modeling success stories that can
be observed in the industry. These success stories were defined in smaller
groups consisting of two to three focus group participants. Each group
identified several characteristics they deemed relevant for the success story
described in Section 2.

While these characteristics were useful to distinguish the success stories and
are used in Section 2, the group quickly realized that they are not suitable
as descriptors of modeler experience since they are not focused on the
modeler. Therefore, as a second step, the group engaged in a discussion that
yielded factors more tailored towards the modeler: required training,
maintainability, immediate benefits, integration in the programming ecosystem,
and reduced friction between modeling and programming. Upon further
reflection, the group identified that some of them were goals and others were
very hard to measure, even qualitatively.

Therefore, the group engaged in a brainstorming session using the “1-2-4-all”
technique: first, individuals brainstormed relevant factors on their own;
second, two individuals came together as a group, discussed their respective
factors, and consolidated them into a new list; third, four participants got
together and consolidated again; and finally, the entire group discussed the
different lists of factors and agreed on a final list of factors.

As an additional step, the focus group participants then discussed how the
different factors relate to each other (cf. Figure 1). While originally trying
to identify positive and negative influences, this idea was abandoned at one
point in favor of a more generic notion of relationship. It is unnecessary to
distinguish cases in which a factor can positively or negatively influence
another.

Figure 1: MX factors and their relations

The result of these intense discussions during the focus groups is the set of
factors described below.

#### Inherent Factors

An inherent factor is based on the characteristics of the problem to address.
The complexity of the language is inherent in the complexity of the problem.
Language choice is also based on the domain and, ultimately, on the problem
that needs to be solved. The chosen language needs to be able to address that
problem and needs to have the necessary complexity to describe relevant issues
in the problem domain.

  * •

Language Complexity is a measure of effort to solve a modeling problem using a
modeling language. Perceived language complexity has been listed as an
impacting factor in [4]. In their seminal work, France et al. [13] highlight
the challenge of _Managing Language Complexity_ faced by practitioners.
Researchers have subsequently employed this classification to assess and
prioritize challenges practitioners encounter in software modeling [14].

  * •

Language Choice is the process of selecting, extending, or defining a set of
modeling languages that provide suitable domain-specific abstractions. Vendor
lock-in creates barriers to MX since it limits interoperability. It should,
therefore, be included as a criterion in the selection process. Language
choice is also influenced by the system domain, “a sphere of knowledge,
influence, or activity. The subject area to which the user applies a program
is the domain of the software.” [15] According to a literature review [16],
the language used directly influences MX. Modeling Languages usually also
cover multiple view points [17]. The need for modeling viewpoints was
emphasized for practitioners and is evaluated based on its support for
multiple viewpoints and large viewpoint management [18].

#### Technical Factors

These factors concern the way modelers work with the chosen languages and
integrate them into their workflows. Specifically, we identified four
technical factors:

  * •

Integration is the conceptual and technical capability of the modeling
approach to fit into existing development processes and development platforms.
Whittle et al. [19] categorize this issue under “Practical
Applicability/Challenges of Applying Tools in Practice.” This is captured in
two sub-factors: 1) chaining tools together, addressing the ease or difficulty
of using multiple tools for end-to-end functionalities, and 2) flexibility of
tools, evaluating a tool’s adaptability to various processes, tools, and
working methods without imposing strict processes or requiring additional
tools [19]. Mohagheghi et al. [20] report that three of four companies
mentioned significant efforts to integrate MDE into the existing processes.
The domain was identified as a contributing factor towards adoption.
Participants voiced that MDE seems most beneficial for bigger companies,
projects, or companies with product lines or similar projects. The vision
paper [21] identifies integration into DevOps workflows as an important step
towards adopting MDE. They focused specifically on the domain of cyber-
physical systems, which would include the automotive industry.

  * •

Tool UX: “A person’s perceptions and responses that result from the use and/or
anticipated use” of the modeling tool [22]. Ease of use and maturity of tools
are two aspects mentioned by Mohagheghi et al. [20]. Both aspects can be
categorized as Tool UX, where tool maturity is likewise closely related to
integration and technical features. Interestingly, the authors found that
companies with lower adoption of MDE considered maturity of tools to be worse
than those with higher adoption. Some participants suggested enhancing the UI
of modeling software to improve Tool UX. In their systematic literature
review, Kalantari and Lethbridge [16] classified and documented MX issues into
five distinct categories: utility, usability, reliability, emotional, and
marketing. Utility and usability are related to ease of use, while reliability
corresponds with the maturity of tools.

  * •

Versioning is the ability to track and merge model changes, facilitating model
maintenance, and is one of the main enablers of Collaboration, as stated by
Pietron [23]. This suggests that versioning is also an important factor of MX.
The inadequacy of version management support has been identified as a drawback
of Model-Based Engineering (MBE) tools within the embedded systems domain
[24]. The technical challenge of combining versioning with blended modeling is
addressed by Exelmans et al. [25]. Collaboration typically alternates between
two modes: asynchronous collaboration, where the work is divided, and
synchronous collaboration, to obtain a shared understanding [26]. In the
literature, support for collaboration has consistently emerged as a desired
attribute of modeling tools for practitioners [18, 27, 28, 29, 30]. In the
more general field of software engineering, collaborative tools positively
impact productivity [31, 32].

  * •

Technical Capabilities result from the combination of modeling language and
modeling tool. They describe how the models can be used in the development
process, e.g., reason about properties of the modeled system via simulation or
formal analysis or to generate downstream artifacts. For example, Liebel et
al. [33] present results from a survey about the technical capabilities used
in model-based engineering in the embedded systems domain. Störrle [34]
presents results on a survey for which purposes models are used when modeling
informally.

#### Non-technical Factors

These factors relate to modeling outside the problem domain and its technical
use. Specifically, we identified four non-technical factors:

  * •

Modeler-Intrinsic Motivation are those factors that lead modelers to use
modeling, in particular, the perceived benefits and positive emotions they
experience. Intrinsic motivation is the inherent motivational source that
drives individuals to engage in activities they personally find compelling.
This stands in contrast to extrinsic motivation, where the incentive
originates from an external source rather than the inherent appeal of the task
[35]. In software development, empirical research suggests that intrinsic
motivation significantly predicts developers’ overall experience [36]. On the
other hand, a lack of perceived benefit of modeling has been noted as one of
the key mindset barriers for adopting MDE [5].

  * •

Organization-Intrinsic Motivation are the factors inside the organization that
lead the organization and the modelers to adopt and foster modeling, in
particular, because of perceived benefits for productivity, product quality,
cost, or collective well-being. The benefits of software modeling practices
have been widely discussed in the literature. A survey on modeling practices
in the embedded software industry underscores cost savings, shortened
development time, reusability, and improved quality as key motivations for
adopting MDE [37]. An empirical assessment noted the benefits of MDE in
communication and control within a project [38]. The assessment also noted
that MDE adoption is affected by culture, expertise, and evangelism within the
organization. MDE adoption requires organizational changes, notably, the need
for a modeling ‘champion’ and carefully choosing initial projects for applying
MDE [38]. Vogelsang et al. [39] noted the importance of managing expectations
when adopting MDE.

  * •

Organization-Extrinsic Motivation are the factors outside the organization
which influence adoption, maturity, and approach of/to modeling, e.g.,
existing standards, regulations, tool availability and maturity, or customer
demands. Adhering to regulations is one of the strong drivers for MDE adoption
in the embedded systems industry [39]. The Unified Modeling Language (UML) has
been cited as _de facto_ standard for software modeling, with a lot of tools
available that support not only model creation and code generation but also
viewpoint management, verification, etc. [18]. However, it has been noted that
existing research on modeling does not address quality issues reported in
industrial context [40].

  * •

Training includes all factors that are related to the skills and knowledge of
modelers in using the selected modeling languages and the tools used to
create, manipulate, analyze, and use the models. Training and education have
been mentioned as an important factor affecting MDE adoption [38].
Insufficient training resources and support, on the one hand, [5], and the
substantial effort required for developer training on the other [41, 39], are
two significant factors in this context. Lack of fundamentals in MDE and
education issues have been noted as major current problems in MDE [1].
Moreover, perceived competence, defined as an individual’s subjective judgment
regarding their own skills and performance, is identified as a crucial factor
contributing to intrinsic motivation [36]. This recognition underlines the
interconnected nature of factors in this domain, emphasizing that effective
training impacts proficiency and influences individuals’ intrinsic motivation
in model-driven practices.

An important aspect of the different motivations is the willingness to take
risks on the individual and organizational level. A small organization might
be more willing to take a risk with its modeling approach and the tools used
than a larger organization because it is more driven by the need to innovate
and cannot afford a less risky but more expensive solution.

##  4 Applying MX to the Modeling Success Stories

In this section we highlight how the different MX factors apply to the
modeling success stories introduced previously. We structure each section
according to the different groups of factors. Table LABEL:tab:mapping-factors-
workflows also shows the importance of the different factors to the different
sucess stories.

###  4.1 Infrastructure as Code

Inherent Factors Infrastructure as Code is typically used at the beginning of
the development process when an infrastructure is needed to execute a
developed software. This infrastructure is often managed by a single or only a
few DevOps Engineers and evolves as the development process continues. The
language depends on the chosen cloud provider or container orchestration tool,
so the choice is limited. While it is simple to configure a CRUD web
application, due to re-usability, community support, and extensive
documentation, configuring specialized distributed systems may require more
complex features of IaC languages.

Technical Factors As IaC is usually written in an IDE (with additional
language support), it directly benefits from many features such as versioning,
auto-completion, formatting, and testability. IaC is, therefore, highly
integrated into the development workflow. Command line interfaces or simple
graphical interfaces are then used for provisioning and setting up
infrastructure from IaC-configurations, which provides developers with a
familiar tool’s UX.

Non-Technical Factors Infrastructure as code is adopted by DevOps engineers to
reduce repeated work, improve debugging capabilities, and improve consistency
across similar software systems. Organizations further aim to reduce costs,
gain flexibility, and improve documentation of their systems. However,
depending on previous workflows and infrastructure management, the change to
IaC can be demanding and requires training for operations engineers and
developers.

###  4.2 Low-Code

Inherent Factors Mature low-code platforms support the entire application
lifecycle management. They do use proprietary modeling languages, though, so
language choice is limited by the chosen tool. Different platforms specialize
in different use cases: Node-RED, e.g., is marketed as a tool for data
processing and visualization for embedded systems whereas Microsoft’s PowerBI
platform is geared towards business process automation and visualization. With
these use cases come different feature sets, different language complexity,
different levels of extensibility and different support options that modelers
have to take into consideration.

Technical Factors Low-code platforms provide their own development
environment. In many cases, these environments include collaboration and
versioning features as well as features to automatically run, test, provision,
and deploy the application using cloud-native concepts. They are separate from
other IDEs developers might be using for other parts of the system, however.
Usability of these tools is generally quite good [42] since the visual aspect
of the environment is one of the most important features and many low-code
platforms are specifically aiming at non-professionals.

Non-Technical Factors The switch to low-code platforms is often motivated by
organization-wide decisions, e.g., to move to Microsoft PowerBI to modernize
legacy systems. We cannot discern situations in which organisation would be
pushed to adopt such systems due to external circumstances. Depending on the
use case, the barrier of entry for such platforms can be significant, but
documentation and training material are exhaustive and there are a variety of
training options.

###  4.3 MBSE

Inherent Factors The modeling success story in the Model-Based Systems
Engineering domain is characterized by extensively using highly sophisticated
and standardized modeling languages. Examples are AUTOSAR for modeling the
hardware/software architecture, and Matlab/Simulink/Stateflow for modeling the
software’s behavior. Due to the ability to generate production code from the
models, the modeling languages are highly complex and provide many technical
features. The language choice in that domain is restricted as complex value
networks between OEMs and suppliers require extensive artifact exchange and,
thus, language standardization.

Technical Factors In addition to the code generation capabilities, the tools
also provide extensive analyses and simulation capabilities. Furthermore, the
tools support versioning and integrating software artifacts, e.g., an OEM
integrates components from various suppliers. Tool UX is often rather low as
the tools are expert and niche tools in addition to the complex languages and
the number of technical features.

Non-Technical Factors The restrictions of the domain highly influence the non-
technical factors of the modeling experience in the MBSE success story.
Modeling languages and the modeling success story are restricted by
organization-extrinsic motivation, e.g., standards or clients require
companies to use certain modeling languages and corresponding tools.
Furthermore, the company-internal and company-external collaboration is
dependent on using the same modeling languages and conforming modeling tools.

###  4.4 Informal and Semi-Formal Modeling

Inherent Factors Informal Modeling mostly occurs early in the design process,
where conformance to any standardized notation is of minimal concern, as
opposed to (creative) expressiveness and a free flow of ideas. Often, the
created sketches evolve into (semi-)formal models later on.

Technical Factors Much of the informal modeling occurs with analog media such
as pen and paper or whiteboards. Although digital alternatives (e.g.,
electronic whiteboards) exist, their adoption rate remains low in practice,
despite technical advantages such as automated persistence and remote
collaboration. We think this remains due to poor Tool UX (e.g.,
responsiveness, viewing angles, accuracy, …) of these solutions compared to
analog media, and we conclude this factor is of utmost importance for informal
modeling.

Non-Technical Factors Informal modeling, and its low-tech nature, comes
natural to engineers, and has been done even since before it was considered a
form of ‘modeling’. Workforce is intrinsically motivated, and this motivation
does not depend on organization-intrinsic or -extrinsic factors. It is often a
collaborative activity.

###  4.5 Comparing the success stories

When comparing the different modeling success stories, we see they are in
different places on the spectrum of MX factors. We illustrate the diversity of
modeling success stories w.r.t. language complexity and technical capability
of the tooling as an example. We believe there are different sweet spots for
different modeling workflows: for instance, model-based systems engineering
reaps benefits from being formal and, therefore, having high language
complexity; this requires tools with high technical capability, which are also
very complex to use. Informal modeling, on the other hand, uses languages with
very low complexity and requires tools with less technical capabilities, e.g.,
to reason about models. Both modeling success stories are in stark contrast to
UML and its tools in the early days when language complexity was high, but at
the same time, rather informal, and the tools had low technical capability.

When using other factors, the different success stories will be positioned
differently. For instance, when contrasting language choice and organisation-
external motivation, MBSE with a high motivation and few available languages
poses fewer issues than informal modelling where languages are often made-up
on the spot and syntax might not be understood between different companies nor
even across teams. This illustrates that our factors are able to capture
interesting trade-offs and that a more systematic investigation of these
trade-offs in future research is necessary.

##  5 Conclusion and Future Work

We defined and explored the concept of Modeler Experience (MX) in the context
of different modeling success stories: infrastructure-as-code, model-based
systems engineering (MBSE), and informal and semi-formal modeling. MX, which
encompasses factors such as usability, motivation, integration, and language
complexity, highlights the dynamics between practitioners and modeling tools.
One of the contributions of this paper is the delineation of technical and
non-technical MX factors and the characterization of these factors in
different modeling success stories. In addition, we show how the proposed MX
factors differ between those modeling stories. By examining these sucess
stories in the light of MX factors, the paper underscores the contextual
nature of modeling practices and the need for tailored approaches to
effectively address modelers’ needs.

Although this paper lays a solid foundation for understanding MX, there are
still many potential research paths to be explored in the future:

The interplay between MX factors and the success of modeling activities
suggests the need for a holistic approach to tool design and workflow
integration. Moving forward, research should focus on empirically validating
the identified MX factors across diverse contexts and exploring the impact of
different workflows on adopting and sustaining modeling practices.

Further empirical studies are essential to quantify the relative importance of
each MX factor and how they interact with one another. These studies could
take the form of longitudinal research within organizations that are
transitioning to or already utilizing model-driven approaches, as well as
experimental studies comparing different tool sets and methodologies.
Additionally, there is an opportunity to conduct cross-sectional analyses
comparing MX across domains, such as automotive, aerospace, healthcare, and
finance, where modeling plays a crucial role.

Another promising direction is the development and refinement of modeling
tools that incorporate the principles of human-centered design. By focusing on
the end-user experience, tool developers can create more intuitive interfaces,
improve the integration with existing development ecosystems, and enhance
collaborative features. This direction also calls for an iterative design
process, where feedback from modelers is continuously incorporated into tool
enhancements.

Case studies can provide in-depth insights into the practical challenges of
addressing MX in specific contexts and the benefits of modeling in industry.
By examining specific cases in detail, researchers can identify best
practices, common pitfalls, and innovative uses of modeling tools that may not
be evident through other research methods.

In conclusion, by continuing to explore and address the various dimensions of
MX, we will serve both academic research and practical tool development,
guiding efforts toward powerful models and tools that are a pleasure to use,
thereby enhancing productivity and satisfaction for modelers worldwide.

Acknowledgments

This work is an outcome of the GI-Dagstuhl-Seminar 23473 “Human Factors in
Model-driven Engineering”. The authors are grateful to the Leibniz Center for
Informatics and the seminar’s organizers for the opportunity to collaborate
and produce these results. Abrahão’s contributions were partially supported by
the State Research Agency (AEI) under the UCI-Adapt project
(PID2022-140106NB-I00). Amaral’ contribution was partially supported by FCT -
Fundação para a Ciência e Tecnologia (Grant Number: 2021.08371.BD).

## References

  *   * Mussbacher et al. [2014] Mussbacher, G., Amyot, D., Breu, R., Bruel, J.-M., Cheng, B.H., Collet, P., Combemale, B., France, R.B., Heldal, R., Hill, J., et al.: The relevance of model-driven engineering thirty years from now. In: Model-Driven Engineering Languages and Systems: 17th International Conference, MODELS 2014, Valencia, Spain, September 28–October 3, 2014. Proceedings 17, pp. 183–200 (2014). Springer
  * Whittle et al. [2013] Whittle, J., Hutchinson, J.E., Rouncefield, M., Burden, H., Heldal, R.: Industrial adoption of model-driven engineering: Are the tools really the problem? In: Moreira, A., Schätz, B., Gray, J., Vallecillo, A., Clarke, P.J. (eds.) Model-Driven Engineering Languages and Systems - 16th International Conference, MODELS 2013, Miami, FL, USA, September 29 - October 4, 2013. Proceedings. Lecture Notes in Computer Science, vol. 8107, pp. 1–17. Springer, ??? (2013). https://doi.org/10.1007/978-3-642-41533-3_1 . https://doi.org/10.1007/978-3-642-41533-3_1
  * Pourali [2018] Pourali, P.: Tooling advances inspired to address observed challenges of developing uml-like models when using modelling tools. Proceedings of the 21st ACM/IEEE International Conference on Model Driven Engineering Languages and Systems: Companion Proceedings (2018)
  * Abrahão et al. [2017] Abrahão, S., Bordeleau, F., Cheng, B.H.C., Kokaly, S., Paige, R.F., Störrle, H., Whittle, J.: User experience for model-driven engineering: Challenges and future directions. In: 20th ACM/IEEE International Conference on Model Driven Engineering Languages and Systems, MODELS 2017, Austin, TX, USA, September 17-22, 2017, pp. 229–236. IEEE Computer Society, ??? (2017). https://doi.org/10.1109/MODELS.2017.5 . https://doi.org/10.1109/MODELS.2017.5
  * Kalantari and Lethbridge [2023] Kalantari, R., Lethbridge, T.C.: Unveiling developers’ mindset barriers to software modeling adoption. In: 2023 ACM/IEEE International Conference on Model Driven Engineering Languages and Systems Companion (MODELS-C), pp. 737–746 (2023). https://doi.org/10.1109/MODELS-C59198.2023.00120
  * Briand et al. [2017] Briand, L.C., Bianculli, D., Nejati, S., Pastore, F., Sabetzadeh, M.: The case for context-driven software engineering research: Generalizability is overrated. IEEE Softw. 34(5), 72–75 (2017) https://doi.org/10.1109/MS.2017.3571562
  * Bucchiarone et al. [2021] Bucchiarone, A., Ciccozzi, F., Lambers, L., Pierantonio, A., Tichy, M., Tisi, M., Wortmann, A., Zaytsev, V.: What is the future of modeling? IEEE software 38(2), 119–127 (2021)
  * Madni and Sievers [2018] Madni, A., Sievers, M.: Model-Based Systems Engineering: Motivation, Current Status, and Needed Advances, pp. 311–325 (2018). https://doi.org/10.1007/978-3-319-62217-0_22
  * Haxthausen and Peleska [2016] Haxthausen, A.E., Peleska, J.: On the feasibility of a unified modelling and programming paradigm. In: Margaria, T., Steffen, B. (eds.) Leveraging Applications of Formal Methods, Verification and Validation: Discussion, Dissemination, Applications. Lecture Notes in Computer Science, vol. 9952, pp. 32–49. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-47169-3_3
  * Di Ruscio et al. [2022] Di Ruscio, D., Kolovos, D., Lara, J., Pierantonio, A., Tisi, M., Wimmer, M.: Low-code development and model-driven engineering: Two sides of the same coin? Software and Systems Modeling 21(2), 437–446 (2022)
  * Bucaioni et al. [2022] Bucaioni, A., Cicchetti, A., Ciccozzi, F.: Modelling in low-code development: a multi-vocal systematic review. Software and Systems Modeling 21(5), 1959–1981 (2022)
  * [12] Hebig, R., Klünder, J., Liebel, G.: GI-Dagstuhl Seminar 23473 – Human Factors in Model-Driven Engineering. accessed Feb. 8, 2024. https://www.dagstuhl.de/seminars/seminar-calendar/seminar-details/23473
  * France and Rumpe [2007] France, R., Rumpe, B.: Model-driven development of complex software: A research roadmap. In: Future of Software Engineering (FOSE ’07), pp. 37–54 (2007). https://doi.org/10.1109/FOSE.2007.14
  * Ozkaya and Erata [2020] Ozkaya, M., Erata, F.: Understanding practitioners’ challenges on software modeling: A survey. Computer Languages 58, 100963 (2020) https://doi.org/10.1016/j.cola.2020.100963
  * Evans [2014] Evans, E.: Domain-Driven Design Reference: Definitions and Pattern Summaries. Dog Ear Publishing, Alaska, USA (2014)
  * Kalantari and Lethbridge [2022] Kalantari, R., Lethbridge, T.C.: Characterizing ux evaluation in software modeling tools: A literature review. IEEE Access 10, 131509–131527 (2022) https://doi.org/10.1109/ACCESS.2022.3227504
  * González-Huerta et al. [2013] González-Huerta, J., Insfrán, E., Abrahão, S.: Defining and validating a multimodel approach for product architecture derivation and improvement. In: Model-Driven Engineering Languages and Systems: 16th International Conference, MODELS 2013, Miami, FL, USA, September 29–October 4, 2013. Proceedings 16, pp. 388–404 (2013). Springer
  * Ozkaya [2019] Ozkaya, M.: Are the uml modeling tools powerful enough for practitioners? a literature review. IET Software 13 (2019) https://doi.org/10.1049/iet-sen.2018.5409
  * Whittle et al. [2015] Whittle, J., Hutchinson, J., Rouncefield, M., Burden, H., Heldal, R.: A taxonomy of tool-related issues affecting the adoption of model-driven engineering. Software & Systems Modeling 16 (2015) https://doi.org/10.1007/s10270-015-0487-8
  * Mohagheghi et al. [2013] Mohagheghi, P., Gilani, W., Stefanescu, A., Fernandez, M.A.: An empirical study of the state of the practice and acceptance of model-driven engineering in four industrial cases. Empirical Software Engineering 18(1), 89–116 (2013) https://doi.org/10.1007/s10664-012-9196-x
  * Combemale and Wimmer [2020] Combemale, B., Wimmer, M.: Towards a model-based devops for cyber-physical systems. In: Bruel, J.-M., Mazzara, M., Meyer, B. (eds.) Software Engineering Aspects of Continuous Development and New Paradigms of Software Production and Deployment, pp. 84–94. Springer, Cham (2020)
  * Technical Committee ISO/TC 159/SC 4 [2019] Technical Committee ISO/TC 159/SC 4: ISO 9241-210:2019 Ergonomics of human-system interaction – Part 210: Human-centred design for interactive systems. Technical report, International Organization for Standardization (ISO) (2019). https://www.iso.org/standard/77520.html
  * Pietron [2020] Pietron, J.: Enhancing collaborative modeling. In: Proceedings of the 23rd ACM/IEEE International Conference on Model Driven Engineering Languages and Systems: Companion Proceedings. MODELS ’20. Association for Computing Machinery, New York, NY, USA (2020). https://doi.org/10.1145/3417990.3419490 . https://doi.org/10.1145/3417990.3419490
  * Liebel et al. [2014] Liebel, G., Marko, N., Tichy, M., Leitner, A., Hansson, J.: Assessing the state-of-practice of model-based engineering in the embedded systems domain, pp. 166–182 (2014). https://doi.org/10.1007/978-3-319-11653-2_11
  * Exelmans et al. [2022] Exelmans, J., Pietron, J., Raschke, A., Vangheluwe, H., Tichy, M.: Optimistic versioning for conflict-tolerant collaborative blended modeling. In: FPVM 2022: 2nd International Workshop on Foundations and Practice of Visual Modeling, July 4–8, 2022, Nantes, France, vol. 3250, pp. 1–12 (2022)
  * Conway et al. [2008] Conway, A.P., Giess, M.D., Lynn, A., Ding, L., Goh, Y.M., McMahon, C.A., Ion, W.J.: Holistic engineering design: A combined synchronous and asynchronous approach. In: International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, vol. 43277, pp. 1227–1236 (2008)
  * Badreddin et al. [2018] Badreddin, O., Khandoker, R., Forward, A., Masmali, O., Lethbridge, T.: A decade of software design and modeling: A survey to uncover trends of the practice, pp. 245–255 (2018). https://doi.org/%****␣mx-factors.bbl␣Line␣500␣****10.1145/3239372.3239389
  * Bordeleau et al. [2017] Bordeleau, F., Liebel, G., Raschke, A., Stieglbauer, G., Tichy, M.: Challenges and research directions for successfully applying mbe tools in practice. In: Burgueño, L., Corley, J., Bencomo, N., Clarke, P.J., Collet, P., Famelis, M., Ghosh, S., Gogolla, M., Greenyer, J., Guerra, E., Kokaly, S., Pierantonio, A., Rubin, J., Ruscio, D.D. (eds.) Proceedings of MODELS 2017 Satellite Event: Workshops (ModComp, ME, EXE, COMMitMDE, MRT, MULTI, GEMOC, MoDeVVa, MDETools, FlexMDE, MDEbug), Posters, Doctoral Symposium, Educator Symposium, ACM Student Research Competition, and Tools and Demonstrations Co-located with ACM/IEEE 20th International Conference on Model Driven Engineering Languages and Systems (MODELS 2017), Austin, TX, USA, September, 17, 2017. CEUR Workshop Proceedings, vol. 2019, pp. 338–343. CEUR-WS.org, ??? (2017). http://ceur-ws.org/Vol-2019/mdetools_1.pdf
  * David et al. [2023] David, I., Aslam, K., Malavolta, I., Lago, P.: Collaborative model-driven software engineering—a systematic survey of practices and needs in industry. Journal of Systems and Software 199, 111626 (2023)
  * Franzago et al. [2017] Franzago, M., Di Ruscio, D., Malavolta, I., Muccini, H.: Collaborative model-driven software engineering: a classification framework and a research map. IEEE Transactions on Software Engineering 44(12), 1146–1175 (2017)
  * Hidayanto and Setyady [2014] Hidayanto, A.N., Setyady, S.T.: Impact of collaborative tools utilization on group performance in university students. Turkish Online Journal of Educational Technology-TOJET 13(2), 88–98 (2014)
  * UR RAHMAN et al. [2020] UR RAHMAN, A., Khan, K., Kamal, S.W., Naveed, H., Bacha, M.: Use of collaborative tools and modern technologies as critical success factor in global software development. Journal on Software Engineering 15(1) (2020)
  * Liebel et al. [2018] Liebel, G., Marko, N., Tichy, M., Leitner, A., Hansson, J.: Model-based engineering in the embedded systems domain: an industrial survey on the state-of-practice. Softw. Syst. Model. 17(1), 91–113 (2018) https://doi.org/10.1007/S10270-016-0523-3
  * Störrle [2017] Störrle, H.: How are conceptual models used in industrial software development?: A descriptive survey. In: Mendes, E., Counsell, S., Petersen, K. (eds.) Proceedings of the 21st International Conference on Evaluation and Assessment in Software Engineering, EASE 2017, Karlskrona, Sweden, June 15-16, 2017, pp. 160–169. ACM, ??? (2017). https://doi.org/10.1145/3084226.3084256 . https://doi.org/10.1145/3084226.3084256
  * Ryan and Deci [2000] Ryan, R., Deci, E.: Intrinsic and extrinsic motivations: Classic definition and new directions. Contemporary Educational Psychology 25, 54–67 (2000) https://doi.org/10.1006/ceps.1999.1020
  * Kuusinen et al. [2016] Kuusinen, K., Petrie, H., Fagerholm, F., Mikkonen, T.: Flow, intrinsic motivation, and developer experience in software engineering, pp. 104–117 (2016). https://doi.org/10.1007/978-3-319-33515-5_9
  * Akdur et al. [2018] Akdur, D., Garousi, V., Demirors, O.: A survey on modeling and model-driven engineering practices in the embedded software industry. Journal of Systems Architecture 91 (2018) https://doi.org/10.1016/j.sysarc.2018.09.007
  * Hutchinson et al. [2011] Hutchinson, J., Whittle, J., Rouncefield, M., Kristoffersen, S.: Empirical assessment of mde in industry. In: Proceedings of the 33rd International Conference on Software Engineering. ICSE ’11, pp. 471–480. Association for Computing Machinery, New York, NY, USA (2011). https://doi.org/10.1145/1985793.1985858 . https://doi.org/10.1145/1985793.1985858
  * Vogelsang et al. [2018] Vogelsang, A., Amorim, T., Pudlitz, F., Gersing, P., Philipps, J.: Erratum to: Should I Stay or Should I Go? On Forces that Drive and Prevent MBSE Adoption in the Embedded Systems Industry: 18th International Conference, PROFES 2017, Innsbruck, Austria, November 29–December 1, 2017, Proceedings, pp. 3–3 (2018). https://doi.org/10.1007/978-3-319-69926-4_57
  * Giraldo et al. [2018] Giraldo, F.D., Espana, S., Pastor, O., Giraldo, W.J.: Considerations about quality in model-driven engineering: Current state and challenges. Software Quality Journal 26, 685–750 (2018)
  * Liebel et al. [2018] Liebel, G., Marko, N., Tichy, M., Leitner, A., Hansson, J.: Model-based engineering in the embedded systems domain: an industrial survey on the state-of-practice. Software & Systems Modeling 17 (2018) https://doi.org/10.1007/s10270-016-0523-3
  * Pinho et al. [2023] Pinho, D., Aguiar, A., Amaral, V.: What about the usability in low-code platforms? a systematic literature review. Journal of Computer Languages 74, 101185 (2023)