Complexity

Definition of Complexity starting with an Example

A definition for complexity in the context of semantification of workflows is not easy to find or create. "Complexity" is a broad term used in different contexts and needs disambiguation.

Let's start with a simple naive example: a simple versus a complex relationship. We would assume that simplicity correlates with small size and complexity with large size. The more people (nodes) involved in a relation the more effort it is to keep the state of the network in order. In a knowledgegraph G=(V,E) it might therefore make sense to count the nodes and edges and the depth and breadth of the structure the graph might build (e.g. if it is a tree).

The cost of traversing the network and the benefit of doing so will most likely also influence the complexity.

So a first step in this train of source is: simple relations have few participants, low transaction costs and high transaction benefits. E.g. buying an ice cream in summer might lead to a good relation to the ice cream vendor if the price is low and the ice most tasty and the ice cream parlor was only a walk away on a hot summer day - you did not have to wait in line and the person selling was kind to you (and of course so have you been).

Formally ... Let's test whether an AI can derive a proper complexity formalization for us ...

AI Generated Complexity Definition

Prompt

For my PhD thesis i would like to test ... (above text) ... give me a formulazation and explanation a) in mediawiki markup b) in latex

Complexity Formalization for Semantification of Workflows

Let G = (V, E) be a knowledge graph where V is the set of nodes (vertices) and E is the set of edges.

Complexity Measure

We define the complexity C of a workflow as: [math]C = \alpha \cdot |V| + \beta \cdot |E| + \gamma \cdot d + \delta \cdot b + \frac{\epsilon \cdot T_c}{T_b}[/math] Where:

|V| is the number of nodes |E| is the number of edges d is the depth of the graph structure b is the breadth of the graph structure T_c is the transaction cost T_b is the transaction benefit α, β, γ, δ, and ε are weighting factors

\section{Complexity Formalization for Semantification of Workflows}

Let $G = (V, E)$ be a knowledge graph where $V$ is the set of nodes (vertices) and $E$ is the set of edges.

\subsection{Complexity Measure}

We define the complexity $C$ of a workflow as:

\begin{equation}
C = \alpha \cdot |V| + \beta \cdot |E| + \gamma \cdot d + \delta \cdot b + \frac{\epsilon \cdot T_c}{T_b}
\end{equation}

Where:
\begin{itemize}
    \item $|V|$ is the number of nodes
    \item $|E|$ is the number of edges
    \item $d$ is the depth of the graph structure
    \item $b$ is the breadth of the graph structure
    \item $T_c$ is the transaction cost
    \item $T_b$ is the transaction benefit
    \item $\alpha, \beta, \gamma, \delta,$ and $\epsilon$ are weighting factors
\end{itemize}

\subsection{Interpretation}

\begin{itemize}
    \item The first four terms ($|V|, |E|, d, b$) represent the structural complexity of the workflow.
    \item The last term ($T_c / T_b$) represents the efficiency of the workflow.
    \item Lower values of $C$ indicate simpler, more efficient workflows.
    \item Higher values of $C$ indicate more complex, potentially less efficient workflows.
\end{itemize}

\subsection{Example: Ice Cream Purchase}

Consider a simple ice cream purchase scenario:

\begin{itemize}
    \item $|V| = 2$ (customer, vendor)
    \item $|E| = 1$ (transaction)
    \item $d = 1$ (single-level interaction)
    \item $b = 2$ (two parties involved)
    \item $T_c$ is low (short distance, no waiting, kind interaction)
    \item $T_b$ is high (tasty ice cream on a hot day)
\end{itemize}

This scenario would result in a low complexity value $C$, indicating a simple and efficient workflow.

⚠️ LLM-generated content notice: Parts of this page may have been created or edited with the assistance of a large language model (LLM). The prompts that have been used might be on the page itself, the discussion page or in straight forward cases the prompt was just "Write a mediawiki page on X" with X being the page name. While the content has been reviewed it might still not be accurate or error-free.

Interpretation

The first four terms (|V|, |E|, d, b) represent the structural complexity of the workflow. The last term (T_c / T_b) represents the efficiency of the workflow. Lower values of C indicate simpler, more efficient workflows. Higher values of C indicate more complex, potentially less efficient workflows.

Example: Ice Cream Purchase

Consider a simple ice cream purchase scenario:

|V| = 2 (customer, vendor) |E| = 1 (transaction) d = 1 (single-level interaction) b = 2 (two parties involved) T_c is low (short distance, no waiting, kind interaction) T_b is high (tasty ice cream on a hot day)

This scenario would result in a low complexity value C, indicating a simple and efficient workflow.

Literature

• https://scholar.google.de/scholar?hl=de&as_sdt=0%2C5&q=complexity+of+workflows+&btnG=

Business process quality metrics: Log-based complexity of workflow patterns

J Cardoso - OTM Confederated International Conferences" On the …, 2007 - Springer

High complexity in workflows may result in poor quality. The major goal of this paper is to describe a quality metric to analyze the complexity of workflow patterns.

Approaches to compute workflow complexity

J Cardoso - 2006 - drops.dagstuhl.de

This paper discusses various methods that can be devised to measure workflow complexity. It explores the complexities that arise in the development of workflows and suggests the adaptation of complexity metrics.

Resolution of geochemical and lithostratigraphic complexity: a workflow for application of portable X-ray fluorescence to mineral exploration

L Fisher, MF Gazley, A Baensch… - Geochemistry …, 2014 - lyellcollection.org

This paper provides a workflow for pXRF data acquisition that incorporates key issues to be considered when developing this workflow, including sample type and preparation.

Progress and prospects for accelerating materials science with automated and autonomous workflows

HS Stein, JM Gregoire - Chemical science, 2019 - pubs.rsc.org

This paper illustrates the continuum of materials workflows in terms of scientific complexity and workflow automation complexity. It elucidates the intended meaning of scientific complexity in this context.

Complexity metrics for workflow nets

KB Lassen, WMP van der Aalst - Information and Software Technology, 2009 - Elsevier

This paper presents three complexity metrics for workflow nets. It focuses on measuring the complexity of workflow models, recognizing that the complexity of the model directly impacts its readability and quality.