capbtabboxtable[][] 11institutetext: 1Hasso Plattner Institute, University of
Potsdam, Potsdam, Germany 11email<EMAIL_ADDRESS>
2Free University of Bozen-Bolzano, Bolzano, Italy
11email<EMAIL_ADDRESS>
# Technical Report: Refining Case Models Using Cardinality Constraints

Stephan Haarmann1 Marco Montali2 Mathias Weske1

###### Abstract

Traditionally, business process management focuses on structured, imperative
processes. With the increasing importance of knowledge work, semi-structured
processes are entering center stage. Existing approaches to modeling
knowledge-intensive business processes use data objects but fail to
sufficiently take into account data object cardinalities. Hence, they cannot
guarantee that cardinality constraints are respected, nor use such constraints
to handle concurrency and multiple activity instances during execution. This
paper extends an existing case management approach with data object
associations and cardinality constraints. The results facilitate a refined
data access semantics, lower and upper bounds for process activities, and
synchronized processing of multiple data objects. The execution semantics is
formally specified using colored Petri nets. The effectiveness of the approach
is shown by a compiler translating case models to colored Petri nets and by a
dedicated process execution engine.

##  1 Introduction

Organizations apply Business Process Management (BPM) to specify, organize,
analyze, and enact business processes. Models play an important role in
documenting, improving, configuring, and monitoring these processes. Control
flow-oriented process modeling languages, such as BPMN [20], are suited for
well-structured processes. However, they lack support for semi-structured ones
often required for knowledge work [5]. When executing knowledge-intensive
processes, knowledge workers make informed decisions choosing from a set of
possible continuations for a process. Thereby, they consult and maintain data
objects.

Effective models of knowledge-intensive processes must capture flexible and
data-centric behavior concisely and comprehensibly. Still, knowledge workers
must decide how to progress each case in an ad-hoc manner. To address these
requirements, among others, declarative [23, 12, 1] and artifact-centric
modeling approaches [14] have been proposed. Declarative approaches concisely
define processes with many variants through rules that eliminate undesired
behavior. Artifact-centric models decompose processes based on data objects,
called artifacts, or states thereof and combine the parts dynamically at run-
time.

There also exist hybrid approaches such as fragment-based Case Management
(fCM) [17, 11]. fCM combines traditional BPMN-like control flow with a
stronger focus on data objects. Processes are defined through multiple
activity-centric process fragments. Each case manages a set of data objects,
which can be accessed by all fragments of a given case. Consequently, the data
requirements for process activities can lead to sophisticated dependencies
among fragments. Data objects and their states are not only used for
determining the process execution semantics but also for defining the goal of
a case.

While previous works on fCM have focused on the approach from a conceptual
perspective, process execution semantics have only been investigated
informally. Behavior is specified in fragments, which are loosely coupled
through data requirements and shared objects. Notably, these dependencies are
not merely based on data objects and their states but also by their mutual
associations and their cardinalities. In this paper, we focus on the following
research question:

> _RQ:_ How can we formally characterize the execution of fCM models while
> considering data associations and cardinality constraints?

We present a thorough execution semantics for fCM case models, which takes
into account process fragments and data objects with their respective states.
Cardinality constraints of data objects are captured in the domain model and
considered in activities’ enablement conditions. The formalization is
expressed as a translational semantics mapping fCM case models to colored
Petri nets (CPN). It allows us to describe the process behavior precisely, to
verify models formally, and to provide IT support during execution. In this
regard, we present prototypes of a compiler (fCM to CPN) and a dedicated
execution engine.

In Section 2, we present the fCM language conceptually and by an example. We
specify the execution semantics in Section 3. We present our prototypes and a
discussion in Section 4. Section 5 discusses related work. We conclude our
paper in Section 6.

##  2 Concepts and Running Example

An fCM case model contains a domain model, an object life cycle (OLC) for each
class in the domain model, process fragments, and termination conditions [11].
We extend case models with data associations and cardinality constraints and
thus get a full-fledged but non-hierarchical data model to represent
structural aspects. In this section, we define case models formally and
illustrate the concepts with an example.

There is exactly one domain model (1) for each case model. It includes
classes, associations, and cardinality constraints. For the sake of the
mapping’s brevity, we do not consider generalization and specialization. We
depict domain models as UML class diagrams [22] with two sets of cardinality
constraints. _Global cardinality constraints_ must always hold. They are
analogue to UML’s multiplicities. _Goal cardinality constraints_ must only
hold when the case terminates—in the diagram, they are preceded with
$\diamond$. Each domain model has a single dedicated class for case objects.
This class is instantiated once and only once for each case.

Consider the process of submitting and reviewing papers at an academic
conference. The domain model (Fig. 1) contains classes for the conference, the
papers, author teams, reviews, and decisions, as well as the depicted
associations. Cardinality constraints refine the association: a conference may
have up to 1000 papers, and for each paper, there is exactly one conference
(global constraints). Likewise, the goal cardinality constraints define ranges
that eventually must be satisfied: although a conference does not require any
papers, it must eventually have 50 or more. A goal cardinality constraint may
only refine the lower bound of the respective global cardinality constraint.
Due to the fact that objects cannot be deleted (in fCM), the upper bound is
the same for both types of constraints. Note, we only support binary
associations and only one association between a pair of classes. Furthermore,
all associations must be existential. This means given two classes $c_{1}$ and
$c_{2}$ it holds that if $u(c_{1},c_{2})>0\Rightarrow l(c_{1},c_{2})>1\vee
l(c_{2},c1)>1$. Finally, we do not support many to many associations:

$u(c_{1},c_{2})>1\Rightarrow u(c_{2},c_{1})=1$

Incompatible domain models can be made compliant using standard reification
techniques (see Section 3).

######  Definition 1 (Domain Model)

A domain model is a tuple $D=(C,c_{co},l,\diamond l,u)$ where

  * •

$C$ is a finite non-emtpy set of classes for the involved data objects;

  * •

$c_{co}\in C$ is the case class describing the case object identifying a case;

  * •

$l,\diamond l,$ and $u$ are functions mapping a pair of classes to an unsigned
integer specifying the domain model’s cardinality constraints’ global lower
bound, goal lower bound, and global upper bound, respectively.

Given two classes $c_{1},c_{2}\in C$, $l(c_{1},c_{2})$ specifies the number of
$c_{1}$ objects each $c_{2}$ object is associate to at least _(_ lower bound
of the global cardinality constraint _)_. The value $u(c_{1},c_{2})$ specifies
the corresponding upper bound. The two classes are associated if
$u(c_{1},c_{2})>0$ _(_ and $u(c_{2},c_{1})>0$_)_. The function $\diamond l$
specifies the goal cardinality constraint. The value $\diamond l(c_{1},c_{2})$
defines the number of $c_{1}$ objects every $c_{2}$ object must be associated
to eventually _(_ goal lower bound _)_. For all classes $c_{1},c_{2}\in C$ the
following properties must hold:

  * •

$u(c_{1},c_{2})>0\Leftrightarrow u(c_{2},c_{1})>0$

  * •

$l(c_{1},c_{2})\leq\diamond l(c_{1},c_{2})\leq u(c_{1},c_{2})$

Figure 1: A class diagram describing the domain model of the submission and
reviewing phase of an academic conference. Pairs of classes with positive
upper bounds for the corresponding cardinality constraints are associated in
the class diagram. The corresponding cardinality constraints are annotated.
Goal cardinality constraints are annotated with a leading $\diamond$ if and
only if they refine the corresponding global constraints.

For each class in the domain model, the case model has one object life cycle
(OLC) (2). An OLC is a state transition system containing a finite set of
states and state transitions. The OLC defines a space in which activities can
be defined: they may alter multiple data objects according to the respective
OLCs. We visualize OLCs as graphs (cf. Fig. 2). The OLC for the class
Conference in the example contains the states scheduled, open for submission,
closed for submissions, and reviewing closed arranged in a sequence. OLCs may
also branch, in case of alternative state progressions, or contain
disconnected parts, in case of alternative initial states. We do not define
initial and final states as they can be inferred from the case model’s
fragments.

######  Definition 2 (Object Life Cycle)

Let $Q$ be a set of states and $\xrightarrow{Q}\subseteq Q^{2}$ a set of state
transitions. Then $(Q,\xrightarrow{Q})$ is a state transition system. An
object life cycle is a state transition system for objects of a specific
class. $U_{Q}$ denotes the universe of all state transition systems.

Data objects and their states play a fundamental role in fCM. We call a pair
of a class and a corresponding state an _object configuration_. Based on these
configurations, we define _data conditions_ (3), which are used to specify
preconditions of activities and the case models’ termination conditions.

######  Definition 3 (Object Configuration, Data Condition)

Let $C$ be a set of classes and $\lambda_{C}:C\to U_{Q}$ a function assigning
each class an object life cycle. Given a class $c\in C$ we write
$\lambda_{C}(c).Q$ to denote the set of states for $c$. For a state
$q\in\lambda_{C}(c).Q$, $(c,q)$ is called an object configuration. We also
write $c[q]$ do denote such a pair. A data condition $d\subseteq\bigcup_{c\in
C}(\\{c\\}\times\lambda(c).Q)$ is a set of object configurations. We write
$U_{d}(C,\lambda_{C})$ to denote the universe of data conditions for a set of
classes $C$ with the object life cycle assignment $\lambda_{C}$.

Figure 2: Object life cycles for each class (see Fig. 1) in the conference
example depicted as graphs. Each object life cycles consists of a set of
states and state transitions between these states. States are represented by
labeled circles and transitions by unlabeled arcs.

Objects are created and updated by activities. Activities are contained in
process fragments (4). Fragments are acyclic control flow graphs similar to
BPMN processes. A fragment contains a set of activities, XOR-gateways, and
optionally a start event connected through control flow. Fragments with a
start event are initial: the event starts a new case. Although loops and AND-
gateways are not supported as direct constructs, concurrency, loops, and even
decisions can be realized by multiple concurrent, repeatable, and alternative
fragments, respectively. This is a deliberate design decision of fCM, since
knowledge-intensive processes may differ from case to case. For each case,
knowledge workers decide which activities need to be executed, in which order,
and how often. Traditional notations, such as BPMN, often produce labyrinthine
models when faced with so many decisions. In fCM, activities read and write
data objects in specific configurations partitioned into input and output
sets, respectively. Furthermore, activities can read sets of objects of the
same class and in the same state.

######  Definition 4 (Fragment)

Given a set of classes $C$ and a function $\lambda_{C}$ assigning object life
cycles to the classes. A fragment is a tuple $f=(N,\xrightarrow{CF},i,o)$
where

  * •

$N=A\cupdot G\cupdot S$ is the set of control flow nodes partitioned into a
non-empty finite set of activities $A$, a finite set of exclusive gateways
$G$, and a finite set of start events $S$. The sets $A$, $G$, and $S$ are
pairwise disjoint.

  * •

$\xrightarrow{CF}\subset(S\times(G\cup A))\cup(A\cup G)^{2}$ is the control
flow relation. For a control flow node $n\in N$, we write $\bullet n$ to
denote the set of predecessors $\bullet n=\\{n^{\prime}\in
N|(n^{\prime},n)\in\xrightarrow{CF}\\}$ and $n\bullet$ to denote the set of
successors.

  * •

$i:A\to 2^{IO}$ assigns each activity a set of input sets. The set
$\bigcup_{c\in C}(\\{c\\}\times\lambda_{C}(c).Q\times\\{true,f\\!alse\\})$
contains object configurations with additional set identifiers. If the boolean
is true, the tuple refers to a list of objects in the specified configuration
otherwise to a single object. A single input- or output set $s$ is a subset
$s\subseteq\bigcup_{c\in
C}(\\{c\\}\times\lambda_{C}(c).Q\times\\{true,false\\})$. $IO$ is the set of
such subsets (power set).

  * •

$o:(S\cup A)\to 2^{IO}$ assigns each activity and start event a set of output
sets.

Furthermore, every fragment must have the following properties:

  * •

$\xrightarrow{CF}$ is acyclic111Loops can be realized through repeatable
fragments

  * •

$\forall a\in A:|\bullet a|\leq 1$ activities have at most one incoming
control flow;

  * •

$\forall n\in(A\cup S):|n\bullet|\leq 1$ start events and activities have at
most one outgoing control flow;

  * •

$\forall g\in G:|\bullet g|>0$ fragments do not start with gateways;

  * •

$|S|\leq 1$ a fragment has at most one start event;

  * •

$S=\emptyset\Rightarrow\exists!a\in A:\bullet a=0$ if there is no start event,
the fragment starts with a single activity.

The fragments for the example are depicted in Fig. 3. _fa_ is the initial
fragment reflecting important milestones of a case, _fb_ is for submissions,
_fc_ for assigning reviewers, _fd_ for creating reviews, _fe_ for deciding on
a paper, and _ff_ for sending notifications. Fragment _fb–ff_ can be repeated
multiple times. Instances of fragment _fc–ff_ can run concurrently and in
various orders.

Figure 3: Process fragments for the conference example. Each fragment is
depicted as graph consisting of BPMN elements. If an activity $a$ has more
than one input- or output set ($|i(a)|>1$ or $|o(a)|>1$), we added markers to
the object nodes to indicate the sets (this is represented by attributes in
BPMN [20]), e.g., submit paper has the input sets $\square=${(conference,open
for submissions,false)} and $\circ=${(conference,open for
submissions,false),(authorTeam,signed_up,false)} differentiating between an
author team’s first and any consecutive submission. This is visually indicated
by the markers $\square$ and $\circ$, respectively.

A case can terminate if one of the termination conditions and the goal
cardinality constraints are satisfied. A termination condition is a data
condition (see 3). Each case model has a non-empty set of termination
conditions. The example has a single termination condition requiring the
conference object in state reviewing closed:

$\\{\\{(Conference,reviewing~{}closed)\\}\\}$

A case model (5) consists of a domain model, a set of fragments, an OLC for
each class in the domain model, and a set of termination conditions. The
domain model is a central element defining the classes of data objects and
additional constraints for all other parts.

######  Definition 5 (Case Model)

A case model is a tuple $M=(D,\lambda_{C},F,T)$ where

  * •

$D=(C,c_{co},l,\diamond l,u)$ is a domain model;

  * •

$\lambda_{C}:C\to U_{Q}$ assigns each class of $D$ an object life cycle;

  * •

$F$ is a set of fragments defined over $C$ and $\lambda_{C}$; and

  * •

$T\subseteq U_{d}(C,\lambda_{C})$ is a non-empty set of data conditions called
termination conditions that specify the goal of every case.

We, furthermore, define criteria for well-formed models that assert that
activities can be executed. An object of $c_{2}$ depends on another object of
$c_{1}$ if $l(c_{1},c_{2})>0$. We call the object of class $c_{2}$ a
_dependent_ and the object of $c_{1}$ a _supporter_. The _dependent_ object
must be created within the context of the _supporter_. This means, that the
_supporter_ object must be read or co-created when the _dependent_ object is
created. It can be that two objects mutually depend on one another (1-to-1
associations). In this case, they must be co-created. Activities that would
create a _dependent_ without its _supporter_ would violate global cardinality
constraints and could not be executed.

Consider the classes Conference and Paper. Paper is the _dependent_ and
Conference the _supporter_. In case of AuthorTeam and Paper, AuthorTeam can be
both _supporter_ and _dependent_. This is reflected in the two input sets of
activity “submit paper‘”: if a new AuthorTeam object is created, the paper is
co-created (both are dependent/supporter of the other). However, future
submissions of the same team can be created without instantiating the
AuthorTeam again.

If two classes $c_{s}$ and $c_{r}$ have a lower bound greater than one,
$l(c_{s},c_{r})>1$ then $c_{r}$ requires a set of $c_{s}$ objects. This must
be respected by the fragments: an activity that instantiates $c_{r}$ must read
a set of $c_{s}$ objects. While sets of objects can be read, objects of a
specific type can only be created one at a time. In the example, a decision
depends on three to four reviews. Thus “decide on paper” must read a list of
review objects.

Whenever a set of data objects is read, there must be a single reference
object. A reference object is an object (not a set thereof) associated with
all the objects consumed in a set. We use the associations to selectively
operate on those objects associated with the reference object. In case of
activity “decide on paper” the paper is the reference object. Sets can also be
used for batch processing apart from lower bounds greater than one. In the
example, the activity “close submission” reads all papers for a given
conference and updates them respectively.

##  3 Execution Semantics

Formal execution semantics are the foundation for execution engines and
process verification, monitoring, and analysis. In this section, we provide a
formalization of fCM case models by means of a translational semantics to
colored Petri nets (CPNs). However, first, we walk through an execution of the
example process. Next, we provide the formal semantics.

###  3.1 Walk-Through

A new case of the example in Section 2 begins once a conference is scheduled
(_fa_). The start event creates the case object (conference). In general, non-
initial fragments can begin after the start event; in the example, however, no
fragment can be instantiated yet because the data prerequisites of their
respective first activities are not satisfied. Thus, the conference must be
opened for submissions first (_fa_) to fulfill the requirements of “submit
paper” (_fb_).

When an author team submits their first paper (input set $\bullet$), a paper
object and an author team object are created. Both get associated since
objects that are created together and whose classes are associated get
associated. Papers also get associated with the conference data object since
objects read get associated with newly created objects if their classes are
associated. Global cardinality constraints must still hold, i.e., an author
team may submit multiple papers but not more than ten. Papers can be submitted
concurrently (multiple instances of _fb_), but an instance of _fb_ handles the
submission and notification of only one paper.

The submission is closed eventually (_fa_). Since no new papers can be
accepted anymore, the conference-to-paper associations must meet the goal
cardinality constraint. So, activity “close submission” requires 50 or more
papers and updates all papers for the conference.

After the submission has been closed, reviews for each paper are assigned
(_fc_) and subsequently created (_fd_). At most four reviews can be assigned
to each paper (global cardinality constraint). Once all reviews for a given
paper have been created, fragment _fe_ can be executed: if there are less than
three reviews, the outcome is an additional required review (output set
$\blacktriangle$); if there are three reviews, the knowledge workers may
decide that an additional review is needed or accept/reject the paper (output
sets $\bullet$ and $\blacksquare$, respectively); if there are already four
reviews, the first option ($\blacktriangle$) is no longer applicable. Once a
decision for the paper has been created, a notification is sent to the authors
(_ff_). Once notifications for all papers have been sent, the reviewing phase
is closed (_fa_). The whole case can be closed when the termination condition
_conference_[_reviewing closed_] is fulfilled and all goal cardinality
constraints are satisfied.

###  3.2 Formalization

The behavior of a case model is defined jointly by all its parts: the
fragments layout the general behavior, which is refined with constraints from
the OLCs and the domain model; eventually, a case meets a termination
condition and can be closed. We map fCM models to CPNs to describe the
execution semantics formally.

##### Assumptions & Preprocessing.

We require that domain models satisfy certain constraints. Every association
is existential (A1). An association is existential when at least one of the
corresponding global cardinality constraints has a positive lower bound. So,
an object of one class cannot be created without an object of the other. We
call the objects _dependent_ and _supporter_ , respectively. Furthermore,
many-to-many associations are not supported (A2). A domain model
$D=(C,c_{co},l,\diamond l,u)$ meets the assumptions if the following
properties are satisfied:

A1

$\forall c_{1},c_{2}\in C:u(c_{1},c_{2})>0\Rightarrow l(c_{1},c_{2})>0\vee
l(c_{2},c_{1}>0)$

A2

$\forall c_{1},c_{2}\in C:u(c_{1},c_{2})>1\Rightarrow u(c_{2},c_{1})=1$

By definition (cf. 1), at most one association exists between two classes
(A3), and only binary associations are supported (A4).

Domain models that break these assumptions can be transformed into compliant
ones through reification. An association violating the constraints is replaced
by multiple classes and associations (see Fig. 4). For example, a many to many
association $A$ linking the classes $c_{1}$ and $c_{2}$ can be reified into a
class $c_{A}$ associated with both $c_{1}$ and $c_{2}$. This comes at the
price of enriching the vocabulary of the domain; thus, reification is best
performed by domain experts, who provide meaningful names, cardinality
constraints, and states for the added classes and who adapt the fragments
accordingly.

Figure 4: A paper is written by multiple authors, which may write multiple
papers. This many-to-many association can be reified: we introduce a class
AuthorTeam and a class Membership. An author has a membership for an author
team.

Besides these assumptions, we perform a preprocessing step before translating
the case model. During preprocessing, we augment state transitions with guards
asserting goal cardinalities. As described, associations may be finalized
before the case terminates. In the moment of finalization, goal cardinality
constraints must hold, e.g., a conference must have at least 50 associated
papers when it is closed for submissions. Associations are established when
one object (dependent) is created in the context of another (supporter). This
is done by activities which make assumptions about the supporter’s state,
i.e., “submit paper” must read the conference in the state “open for
submission”. If an activity changes the state irreversibly the goal
cardinality must hold. For each state of a supporter, we check whether the
fragments allow adding associations (for a specific dependent). If so, we
check in the OLC for the outgoing state transitions whether the target state
or any state reachable supports adding further associations. If not, we add a
guard to the state transitions that requires the object (of the supporter) to
satisfy the goal cardinality constraint (see Fig. 5).

Figure 5: OLC of the conference augmented with a guard. The conference can
only change to the state “closed for submissions” if there are at least 50
associated papers. This requirement arises from the goal cardinality
constraints and the fragments: eventually, there must be 50 papers, and the
fragments forbid adding papers for a conference once it is in the state
“closed for submissions”.

##### Translation.

A CPN is a Petri net with typed places and tokens. The enablement of
transitions may depend on the value of tokens, and the firing may derive new
tokens. As such, CPNs can represent data-based systems, i.e., fCM case models.

Types in CPNs are called colorsets. We represent an object by an identifier
(ID), which consists of a class and an integer (i.e., the number of existing
objects of the same class at the point of creation). An association is an
unordered pair of IDs. We further have types for sets of IDs (Set<ID>) and
sets of associations (Set<Association>). A colorset ControlFlow for the
control flow maps each class to an ID or NULL. We further use places of
colorset INT (integer numbers) and Unit (blank tokens). Formally coloresets
are defined as:

$\displaystyle ID$ $\displaystyle=Classes\times\mathbb{N}$ $\displaystyle
Association$ $\displaystyle={{o_{1},o_{2}}\subset ID|o_{1}\neq o_{2}}$
$\displaystyle Set<ID>$ $\displaystyle=P(ID)$ $\displaystyle Set<Association>$
$\displaystyle=P(Association)$ $\displaystyle ControlFlow$
$\displaystyle=Classes\rightarrow ID$

Algorithm 1 outlines the mapping. We created places for abstract states of the
case (l. 1), class-specific counters (l. 3), and object configurations (l. 5).
Transitions are added for all control flow nodes (l. 12–29) and each
termination condition (l. 31). We present each of these steps, both in text
and visually, in the remainder of this section.

Data: $((C,c_{co},l,\diamond l,u),\lambda_{C},F,T)$

createGlobalPlaces();

/* Fig. 6 */

1 foreach  _c $\in$ C_ do

createCounterPlace(c);

/* Fig. 7 */

2 foreach  _q $\in$ $\lambda_{C}(c).Q$_ do

createObjectConfigurationPlace(c,q);

/* Fig. 7 */

3

4 end foreach

5

6 end foreach

7foreach  _$(N,\xrightarrow{CF},i,o)\in F$_ do

8 foreach  _$(n,n^{\prime})\in\xrightarrow{CF}$_ do

createControlFlowPlace($(n,n^{\prime})$);

/* Fig. 8 */

9

10 end foreach

11 foreach  _$n\in N$_ do

12 if  _$n$ is gateway_ then

13 foreach  _$(n^{\prime},n),(n,n^{\prime\prime})\in\xrightarrow{CF}$_ do

createGatewayTransition($n,n^{\prime},n^{\prime\prime}$);

/* Fig. 9 */

14

15 end foreach

16

17 else if  _$n$ is start event_ then

18 foreach  _$\blacksquare\in o(n)$_ do

createStartEventTransition($n,\blacksquare$);

/* Fig. 10 */

19

20 end foreach

21

22 else

23 foreach  _$\blacksquare\in o(n)$_ do

24 foreach  _$\square\in i(n)$_ do

createActivityTransition($n,\square,\blacksquare$);

/* Fig. 11,12 */

25

26 end foreach

27

28 end foreach

29

30 end if

31

32 end foreach

33

34 end foreach

35foreach  _$t\in T$_ do

createTerminationConditionTransition(t);

/* Fig. 13 */

36

37 end foreach

Algorithm 1 Algorithm for translating a case model to a CPN. Details are given
in the figures (see comments). Figure 6: Global places that are created for
each case model: i) an initial place _i_ , which holds a single token until a
case is started; a place _r_ , which holds a single token when the case is
running; and a final place _o_ that holds a token after the case has been
closed. Furthermore, we ii) add a place associations of type
Set$<$Association$>$ and a place _objects_ of type Set$<$ID$>$. Figure 7: To
support data two sets of places are added: the first set contains a place with
colorset INT for each class; the second set contains a place of colorset ID
for each object configuration. Figure 8: For each control flow arc, a
ControlFlow place is created.

The state of a CPN is defined by its current marking, the value and position
of tokens in the net. We, thus, require places for the different aspects of a
case’s state. First, we distinguish between three abstract states initial,
running, and terminated of the case. We add three Unit places _i_ , _r_ , and
_o_ , respectively (Fig. 6). We furthermore add a single place labeled
_associations_ with colorset Set<Associations> holding a single token
containing all associations, and one place _objects_ of type Set<Object>
holding a single token containing IDs of all data objects (Fig. 6).
Furthermore, a place typed ID for each object configuration is added (Fig. 7).
Additionally, we add a place of type INT for each class (Fig. 7). These places
each hold a token with initial value 0 and are labeled “cnt_$<$Class$>$”,
e.g., _cnt_Conference_. They are used to count the number of objects for the
respective class. Finally, a ControlFlow place (n,n’) is added for each
control flow $(n,n^{\prime})\in\xrightarrow{CF}$ in each fragment (Fig. 8).

Transitions are added for each control flow node and for each termination
condition (Algorithm 1, l. 8–32). A gateway is translated to one transition
for each combination of incoming and outgoing control flow (l. 13–16). A start
event is translated to a transition for each of its output sets222A start
event without a data output has an empty output set. (l. 17–21). For an
activity, a transition for each combination of an input set and an output set
is added (l. 22–27). Finally, a transition for each termination condition is
created (l. 30–32).

A transition for a gateway (Fig. 9) moves a token from the place representing
the respective incoming control flow to the place representing the respective
outgoing one. The value is not changed, and the transition has no guards.

Figure 9: For each gateway we consider every combination of an incoming and an
outgoing control flow. The CPN has a transition that passes the control flow
for each such combination.

A transition representing a start event (Fig. 10), takes a token from _i_ and
produces one in _r_. If the output set represented by the transition is non-
empty, counters for all objects in the output set are read and incremented.
Based on the original value of the counter new ID tokens for the objects are
created and i) added to a set stored on the place objects and ii) as a single
token stored on the place representing the respective object configuration.
The set of associations is initialized: a Set$<$Association$>$ token
containing associations among the created objects (if applicable) is created.
Also, if the event has an outgoing control flow, a new ControlFlow token is
produced on the corresponding place. The token’s fields for the objects in the
output set reference the created objects.

Figure 10: We create a transition for each output set ($\blacksquare$) of each
start event (s). The transition moves a token from _i_ to _r_ , creates a data
object for each configuration (c[q]) in the output set. In the process, the
corresponding counter is incremented. The set of associations and objects is
updated, and a ControlFlow token referencing all created objects is created.
_O_ is a set of all objects created by the start event for the output set. _A_
is the set of all associations that are established.

A transition for an activity (Fig. 11), consumes a token for each data object
that is read. It re-produces consumed tokens for each data object that is read
or updated in the same or a different place, respectively. Furthermore, new ID
tokens are produced for newly created data objects, this includes an update of
the corresponding counters, the set of objects, and the set of associations
(if applicable). New objects that may be associated (according to the domain
model) to objects in the input or outputs set will be associated. Transitions
for activities without incoming control flow require a token on place _r_ ,
but the token is not removed when the transition fires. Other activities are
triggered via their incoming control flow and the respective transition
require a corresponding ControlFlow token.

Figure 11: An activity reads objects of one input set
($\square=\\{c1[q1],c2[q2]\\}$) and writes objects for one output set
($\blacksquare=\\{c2[q2^{\prime}],c3[q3]\\}$). We assume $q2\neq q2^{\prime}$.
This means objects can be read (c1,c2), updated (c2), or created (c3). The
associations and references to all objects are read and updated. In this case,
we assume an association between c3 and c2 but none between c1 and c3. The CPN
transition consumes and produces the required tokens. The guard asserts that
(i) inputs are associated if applicable, (ii) upper cardinality bounds are not
exceeded, (iii) lower bounds of global cardinality constraints are satisfied,
and (iv) state changes are possible. If the activity has an incoming control
flow, additional guard conditions assert that data objects are consumed
according to the references in the ControlFlow token (not depicted).

A transition representing an activity has a guard to assert

i)

inputs that can be associated are associated

ii),iii)

associations that will be established by the transition do not violate
cardinality constraints

iv)

the guards of the state transitions realized by the activity are satisfied

v

bindings in the control flow are not violated (not included in Fig. 11)

Activities may also represent batch behavior (Fig. 12). They read and possibly
update multiple objects of the same type, e.g., all papers. As described
above, the set of objects is qualified by an associated reference object. Let
$\square$ be an input set containing an entry $(c_{1},q_{1},true)$ (a set of
$c_{1}$ objects in state $q_{1}$ is read), then there exists an entry
$(c_{2},q_{2},false)$ in $\square$ so that $u(c_{1},c_{2})>1$ (the two classes
are associated). If $A$ is the set of associations and $(c_{2},n_{2})$ the ID
of the reference object, then the set $O_{1}$ is the set of $c_{1}$ objects
associated with $(c_{2},n_{2})$:

$O_{1}=\\{(c_{1},n_{1})|\\{(c_{2},n_{2}),(c_{1},n_{1})\\}\in A\\}$

Figure 12: An activity may read and update a set of data objects. In the
depicted case, a set of $c2$ objects associated with the object $ID_{c1}$ is
read and updated. Furthermore, a $c3$ object is created and associated with
all elements of the set. The guard asserts, that neither the global upper
bounds nor the global lower bounds are violated.

Furthermore, a transition for each termination condition is created (Fig. 13).
The transition moves a token from r to o terminating the case. Furthermore, a
token for each required object configuration as well as the tokens for the set
of all objects and the set of associations are consumed. Such a transition has
a guard asserting that the goal cardinality constraints are met. Let $O$ be
the set of object identifiers and $A$ the set of associations. Furthermore,
let $D=(C,c_{co},l,\diamond l,u)$ be the domain model. The formal guard
condition is

$\forall(c_{1},n_{1})\in O,\forall c\in C:\diamond
l(c,c_{1})\leq\\{n\in\mathbb{N}|\\{(c_{1},n_{1}),(c,n)\\}\in A\\}$

Figure 13: A termination condition $t$ contains a set of object configurations
$\\{c[q]\\}$. The corresponding transition moves the token from _r_ to _o_ ,
consumes a token for every object configuration, one for the set of objects,
and one for the set of associations. The transition has a guard asserting that
the goal cardinality constraints are satisfied.

###  3.3 Formalization of the Example

Next, we formalize the example (Section 2). We present the formalization one
fragment at a time. Places with the same label represent the same place, e.g.,
both the CPN for _fa_ and the one for _fb_ have a place labeled
“conference[open for submissions]”, but the place is created only once.

Figure 14: The formalization of fragment _fa_ with transitions for the start
event and the subsequent activities as well as places for the general state
and data objects. Places of type Unit have no colorset annotated. The
transition “close submission” has a guard asserting goal cardinalities, the
transitions “close submission” and “close reviewing” access a list of IDs by
querying the set of associations.

The formalization of fragment _fa_ (Fig. 14) contains four transitions: one
transition for the start event and one for each activity. Neither the start
event nor the activities have multiple input or output sets. The formalization
of the fragments contains places for the object configurations accessed by the
control flow nodes, the counter of conference object, which is created by the
start event, control flow places for all control flow arcs in _fa_ , and the
places _i_ and _r_ denoting the abstract states initial and running,
respectively.

The firing of the start event starts a new case. In the CPN, a token is moved
from _i_ to _r_. Furthermore, an ID token for the conference object in state
_scheduled_ is created. For this purpose, the counter on _cnt Conference_ is
read and incremented. The transition also initializes the set of associations
and the set of objects (including the conference ID). Since the start event
has an outgoing control flow, the transition produces a control flow token
referencing the conference. The label of ControlFlow places is omitted.

The control flow leads to the activity “open submission”, which updates the
state of the conference object. The corresponding transition consumes the
ControlFlow token and the ID token of the conference. A guard asserts that the
ID is referenced in the ControlFlow. Both tokens are reproduced on the places
for conference[open for submissions] and the outgoing control flow,
respectively.

The next activity, “close submission”, reads a list of papers in addition to
the conference. The corresponding transition (Fig. 14), accesses the list of
associations to find all the papers associated with the conference. All papers
in the list and the conference are updated. Therefore, the transition moves
the respective ID tokens to the places for the corresponding object
configuration. The activity can only be executed if all papers of the
conference are in state _submitted_ and if there are at least 50 associated
papers. This is represented in the transition’s guard. Activity “close
reviewing” is mapped analogously. However, it has no successor; thus, the
ControlFlow token is consumed but not produced.

Figure 15: The formalization of fragment _fb_ has two transitions for activity
“submit paper” and one for “send submission notification”. “Submit paper” is
mapped to two transitions because it has two input sets ($\circ$ and
$\square$) and one output set. The ControlFlow token, that is passed from
“submit paper” to “send submission notification” references the conference,
author team, and paper.

The formalization of fragment _fb_ (Fig. 15) contains two alternative
transitions for “submit paper” and a subsequent transition for “send
submission notification”. It further contains places for the control flow, the
set of associations, the set of objects, and the object configurations
accessed by the activities. The transitions for the fragment’s first activity
require a token on _r_ (the case must be running), but the token is not
removed. They, furthermore, consume and reproduce a token for a conference
object in state _open for submission_. Both transitions create ControlFlow
token that references the three involved objects: conference, author team, and
paper. Transition “$\circ$submit paper” represents the first submission of an
author team. An ID token for the author team and one for the paper is created,
the IDs are added to the list of objects (O), and the pair of IDs is added to
the set of associations (A). Furthermore, an association between the
conference and paper is established. Transition “$\square$submit paper” is
similar, but an ID of an author team is consumed and reproduced instead of
created. Both transitions must not violate cardinality constraint (see
guards). Since neither transition invalidates its precondition, _fb_ can be
executed multiple times. The number of executions is only limited by the upper
bound of the corresponding global cardinality constraint: if 1000 papers have
been submitted, the “submit paper” transitions are disabled.

The transition “send submission notification” consumes the previously created
ControlFlow token. It also consumes ID tokens for the referenced author team
and paper (see guard). The guard asserts that both objects are associated.
However, neither of the objects is updated; thus, the ID tokens are reproduced
on the place they have been consumed from. Also, neither the list of objects
nor the list of associations is changed. However, the former is accessed to
check that the two objects are associated.

Figure 16: The CPN for fragment _fc_ has a single transition “assign
reviewer”. It can be executed up to four times for every submission and
assigns a review to the paper.

Fragment _fc_ has a single activity with one input set and one output set. It
is mapped to a single transition (Fig. 16). The transition requires that the
case is running (token on _r_). It consumes and produces an ID token from the
place “paper[in_review]” and creates a new ID token on “review[required]”
(incrementing the corresponding counter on _cnt Review_). The guard asserts
that the global cardinality constraints are not violated by preventing that
more than four reviews are created for each paper.

Figure 17: Formalization of fragment _fd_. Reviews that are required must be
created. The transition “create review” updates the the state of a review by
moving the corresponding ID token from place “review[required]” to place
“review[available]”.

Fragment _fd_ updates a review object (Fig. 17). Its state changes from
_required_ to _available_. The transition “review paper” consumes ID tokens
for the review and the associated paper (see guard). While the latter remains
unchanged, the ID token for the review is produced on the place
“review[available]” The transition also consumes and produces a token on _r_
(the case must be running).

Fragment _fe_ contains a single activity with three output sets. It is mapped
to three repsective transitions (Fig. 18). Each transition represents one of
the output sets of activity “decide on paper”. They each consume an ID token
for a paper in the state _in_review_ and a set of IDs for the associated
reviews in the state _available_. Transition “decide on paper$\blacktriangle$”
represents the decision outcome of an additional required review. The
transition reproduces the set of IDs on place “review[available]” and the
paper ID on place “paper[in_review]”. It also creates a novel ID for a new
review object on place “review[required]”. Since a new review for the paper is
created, the corresponding global cardinality constraint is checked (see
guard). Furthermore, the set of object IDs and the set of associations is
updated, respectively.

Figure 18: Formalization of fragment _fe_ : while the fragment has a single
activity “decide on paper”, the CPN has three corresponding transitions—one
for each output set. Transition “decide on paper$\blacktriangle$” requires an
additional review, “decide on paper$\blacksquare$” accepts the paper, and
“decide on paper$\bullet$” rejects the paper. In case of acceptance or
rejection, a decision object is created.

In case three or four reviews exist for a particular paper, it can be rejected
or accepted. These outcomes are represented by transitions “decide on
paper$\bullet$” and “decide on paper$\blacksquare$”, respectively. Both
transitions move the set of ID tokens for the reviews to the place
“review[considered]” (updating the state of each object in the set). Likewise,
the paper’s ID token is moved to “paper[reviewed]”. A new ID is created for
the decision and the corresponding counter (token on “cnt Decision”) is
consumed and incremented. The ID is added to the set of objects (O) and the
set of associations (A) is updated: the decision is associated with the paper
and to each review that was considered.

Fragment _fe_ is a knowledge-intensive task. The involved knowledge workers
have to decide which variant fits the particular case best: e.g., which paper
can be rejected or accepted, and which paper requires an additional review.
However, the cardinality constraints limit the options for the knowledge
workers: papers cannot be rejected/accepted if not enough reviews exist. On
the contrary, only four reviews for a paper may exist, limiting the execution
of transition “decide on paper$\blacktriangle$”. A semantics that does not
consider cardinality constraint would allow infinite reviews and not support
knowledge workers during the decision.

Figure 19: Formalization of fragment _ff_. The two transition represent the
sending of an acceptance and rejection notification ($\square$ and $\circ$).
Objects are updated but not created. The set of associations is consulted to
assert that the decision is associated with the paper and that the paper is
associated with the author team (guard).

Fragment _ff_ contains an activity for sending notifications to the authors of
a paper. The activity updates a paper object and reads an author team object.
Furthermore, it reads the respective decision which is either in state
accepted or rejected. This is represented by two corresponding transition
(Fig. 19). They consume and produce ID tokens for the objects read, and their
guards assert that the activity operates only on associated objects.

Figure 20: A transition for the termination condition
$\\{con\\!f\\!erence[reviewingClosed]\\}$. Firing the transition closes the
case by moving a token from _r_ to _o_. The guard asserts all goal cardinality
constraints. $C$ is the set of classes in the domain model (e.g., _Conference,
Paper, AuthorTeam, Review_ , and _Decision_).

The case can terminate once the conference is in state reviewing closed and
all goal cardinalities are satisfied (Fig. 20). This is represented by one
transition that moves a token from _r_ (case is running) to _o_ (case has been
closed). It furthermore _consumes_ the set of objects and associations, as
well as a token for the required object configuration _conference_[_reviewing
closed_]. Since no further activities should be executed, the tokens are not
reproduced. The guard checks the associations (A) of each object (in O) and
verifies whether the goal cardinality constraints are met.

##  4 Implementation and Discussion

The encoding of case models into CPNs detailed in Section 3 provides a basis
for full-fledged enactment of fCM models. In this respect, we present
prototypes of i) a compiler translating fCM models to CPNs compatible with
CPNTools and of ii) an execution engine. Prototypes, instructions, and
screencast are available at https://github.com/bptlab/fcm2cpn/tree/caise and
https://github.com/bptlab/fCM-Engine/tree/caise.

Figure 21: FMC model of the architecture. The compiler reads a case model
consisting of a UML class diagram and BPMN file containing fragments and
produces a CPN. The engine uses CPNTools to execute cases. Additional
information, such as detailed information about classes and attribute
information, are stored in the state.

Figure 21 shows the architecture of our implementation. Case models can be
created using common tools for BPMN and UML modeling. Given a BPMN file
describing a set of fragments and a domain model (UML Class diagram without
hierarchies) describing the classes of objects used in the case model, the
compiler creates a CPN file using Access/CPN. It established a connection
between the two inputs by matching the names of data objects in the fragments
to the names of classes in the domain model. We assume that the fragments
conform to the OLC,s enabling us to extract the OLCs from the fragments.

r | ()
---|---
paper[in_review] | (Paper, 0)
review[available] | (Review, 0)
| (Review, 1)
associations | [((Paper, 0), (Review, 0)),
| ((Paper, 0), (Review, 1))]
objects | [(Paper, 0), (Review, 0),
| (Review, 1)]
cnt review | 1

Figure 22: Relevant marking for CPN, see Fig. 18 for place names.

Figure 23: The engine depicting the state from Fig. 23. A new review is created. Table 1: Requirements of knowledge-intensive processes [5] fully (+) or partly ($\circ$) satisfied by fCM ($+$). We do not include requirements regarding user management and adaptability. R1 | Data Modeling | $+$
---|---|---
R4 | Synchronized Data Access | $\circ$
R5 | Data-driven Actions | $+$
R7 | Formalized Rules and Constrains | $\circ$
R9 | Goal Modeling | $+$
R11 | Support for Different Modeling Styles | $+$
R12 | Visibility of the Process Knowledge | $+$
R13 | Flexible Process Execution | $+$
R24 | Capture and Model External Events | $+$

The fCM engine takes the CPN and the corresponding domain model. The engine
communicates with CPNTools to determine the enabled activity and event
instances. CPNTools has tokens as described in Section 3. However, it does not
hold any information about data objects’ attributes and their values. This
information is stored separately in the engine. The domain model is parsed to
generate forms for data objects. When a user selects an enabled activity, the
engine displays the available input-output set combinations. The user can
choose one, and the corresponding form is displayed (see Fig. 23). Once the
user completes an action, the engine updates the objects and instructs
CPNTools to execute the respective transition. Currently, valuations and
tokens are volatile; once the engine is closed, all progress will be lost. We
made this decision to keep the engine simple. However, persistent storage,
such as a relational database, could be used to store both the state of the
CPN and attributes with their values.

Tools are important to deal with the complexity of the approach and the
domain. Our version of fCM contains additional hidden dependencies [9]:
changing one part of a domain model (e.g., cardinality constraints) may
require adaptation of other parts (e.g., the inputs of activities).
Additionally, the execution of fragments depends implicitly on the effects
that other fragments induce over data objects and their associations. Well-
designed tools for modeling, verification, and execution can compensate for
some challenges posed by the language [9]. The presented engine guides users
and makes it optional to interpret the intricate models manually at run-time.
Furthermore, fCM with its details may prove to be a proper low-code solution
used by trained engineers rather than business users to design, implement, and
monitor knowledge-intensive processes. However, this work focuses on the
concepts and semantics. Notation and usability are left for future work. We
added domain models with associations and cardinality constraints to case
models satisfying requirements for knowledge-intensive processes (cf. [5],
Table 1): the process model integrates different perspectives each can be used
according to their strengths. Furthermore, the process is data-
driven—available objects and cardinality constraints determine the enabled
activities. Finally, data objects are captured in detail with states,
associations, and constraints.

Data cardinality constraints are crucial for formal verification. In general,
verifying models combining processes and data is undecidable [4], in
particular, because the process may operate on unboundedly many data objects.
As shown in [18], a data-aware version of soundness and other data-aware
temporal properties can be verified if cardinality constraints with suitable
upper bounds and adequately restructured queries are employed. This work takes
a first step towards applying techniques studied in [18] and related
approaches to the verification of fCM models, which is one of the next steps
we want to take.

##  5 Related Work

We briefly present related work in three categories: fragment-based case
management, alternative modeling approaches, and formal models/execution
semantics.

fCM is a production case management approach introduced by Meyer et al. [17].
Hewelt and Weske describe fCM, focusing on the language and syntax [11].
Consecutive works propose methods for eliciting [10] and verifying [13] case
models. These works do not consider associations or cardinality constraints.
We add these to fCM, strengthening the link between data and behavior.

Data-centric process modeling approaches have a long history. Recently,
Steinau et al. provided an overview of such approaches [27]. An early approach
is MERODE, which interprets data models with existential associations as a
behavioral specification [25]. Guard stage milestone [15] and CMMN [21]
arrange activities in stages with data pre- and post-conditions.
PHILharmonicFlows [16] models OLCs, which can be orchestrated into larger
processes. Associations and cardinalities can be used to synchronize
transitions between sets of objects [26] In contrast to PHILharmonicFlows and
MERODE, fCM focuses on case management. It is a hybrid approach that separates
domain and process modeling.

Rather than specifying process variants imperatively, declarative models
define constraints to capture multi-variant processes concisely. Two prominent
declarative languages are DECLARE [23] and DCR-Graphs [12], both use variants
of linear temporal logics. While declarative modeling is powerful to model
constraints from laws, guidelines, and other rules, imperative models are
preferred when explicit control and data flow are important. DCR-KiPM [24] is
a hybrid approach combining declarative DCR-Graphs with an imperative notion
called KiPM to model knowledge-intensive processes. Object-centric behavioral
constraints combine declarative process models with data models [1].
Activities and LTL rules over finite traces are quantified based on data
objects and their associations Cardinality constraints exist in two flavors:
they have to hold globally or eventually. However, no case exists. fCM
achieves flexibility by combining fragments, modeled using elements within the
BPMN tradition, dynamically. In fCM, declarative rules can be asserted through
compliance checking [13].

Formal execution semantics are broadly applied in BPM. Dijkman et al. present
a Petri net formalization for BPMN models enabling analysis and verification
[6]. Proclets [2] are an extension of Petri nets: a process is composed of
multiple workflow modules that contain synchronization points. They allow
modeling various kinds of processes, such as choreographies and data-centric
processes. Fahland introduces cardinality constraints for the synchronization
points enabling many-to-many interactions [7]. DB-Nets assure that a process
adheres to constraints given by a database (such as primary and foreign key
constraints), by incorporating transactional semantics [19]. Catalog nets
combine Petri nets with queryable read-only databases to support
synchronization among cases [8]. Translating fCM to these formalisms would be
interesting to connect the two trends of research. Object-centric Petri nets
have been used to describe processes mined from object-centric event logs[3].
It would be interesting to see mining algorithms targeting fCM. Our semantics
are defined using Petri nets, but users only interact with the fCM model,
which hides the formalism’s complexity.

##  6 Conclusion

Knowledge-intensive processes demand flexibility and data-driven actions.
Also, modeling approaches should incorporate various perspectives through
suited languages [5]. In this paper, we integrated activity-centric process
fragments with domain models comprising associations and cardinality
constraints. While we use fCM models, our work can be applied to traditional
processes (e.g., modeled using BPMN) to determine bounds for loops and multi-
instance activities.

We showed that object cardinalities influence the behavior of processes.
Activities are enabled depending on whether certain cardinality constraints
hold. For example, a paper may only be rejected or accepted if three reviews
exist (requirement). On the other hand, only one decision is made for each
paper (bound). Furthermore, cardinality constraints may require batch
processing where multiple objects of the same type are accessed
simultaneously. Additionally, cardinality constraints can refine the goal
definition of a case. Not only do objects need to progress into specific
states, but they also need to exist in specified quantities. This allows
defining knowledge-intensive processes more comprehensively.

We provide a formal semantics using CPNs respecting the behavioral
implications of cardinalities. The semantics is the underpinning for many BPM
related tasks, such as process execution, verification, modeling, and mining.
Due to the intricate nature of knowledge-intensive processes, tools are
important. During modeling, a tool may highlight hidden dependencies and aid
with the verification. At run-time, engines may guide the knowledge workers
making it unnecessary to interpret the model manually. Alternatively, process
monitoring may check compliant actions. While we only focus on the definition
of the formal semantics, we lay an important foundation for these future
tasks.

We do not consider inheritance. Class hierarchies where associations and
cardinality constraints are the same on all levels do not require any changes.
However, specializing and generalizing associations including cardinality
constraints and advanced modeling concepts, e.g., the phase pattern, are
interesting for future work and require investigation of conceptual models and
algorithms.

Future work may also investigate the role of knowledge workers in detail: they
may require relaxed constraints or the ability to adapt the process ad hoc.

####  6.0.1 Acknowledgments.

We thank Leon Bein for his work on the prototypes.

## References

  * [1] van der Aalst, W.M.P., Artale, A., Montali, M., Tritini, S.: Object-centric behavioral constraints: Integrating data and declarative process modelling. In: Proceedings of the 30th International Workshop on Description Logics, Montpellier, France, July 18-21, 2017 (2017), http://ceur-ws.org/Vol-1879/paper51.pdf
  * [2] van der Aalst, W.M.P., Barthelmess, P., Ellis, C.A., Wainer, J.: Workflow modeling using proclets. In: Cooperative Information Systems, 7th International Conference, CoopIS 2000, Eilat, Israel, September 6-8, 2000, Proceedings. pp. 198–209 (2000), https://doi.org/10.1007/10722620_20
  * [3] van der Aalst, W.M.P., Berti, A.: Discovering object-centric Petri nets. Fundam. Informaticae 175(1-4), 1–40 (2020), https://doi.org/10.3233/FI-2020-1946
  * [4] Calvanese, D., De Giacomo, G., Montali, M.: Foundations of data aware process analysis: A database theory perspective. In: pods-13. pp. 1–12. ACM Press (2013)
  * [5] Ciccio, C.D., Marrella, A., Russo, A.: Knowledge-intensive processes: Characteristics, requirements and analysis of contemporary approaches. J. Data Semant. 4(1), 29–57 (2015), https://doi.org/10.1007/s13740-014-0038-4
  * [6] Dijkman, R.M., Dumas, M., Ouyang, C.: Semantics and analysis of business process models in BPMN. Inf. Softw. Technol. 50(12), 1281–1294 (2008), https://doi.org/10.1016/j.infsof.2008.02.006
  * [7] Fahland, D.: Describing behavior of processes with many-to-many interactions. In: Application and Theory of Petri Nets and Concurrency - 40th International Conference, PETRI NETS 2019, Aachen, Germany, June 23-28, 2019, Proceedings. pp. 3–24 (2019), https://doi.org/10.1007/978-3-030-21571-2_1
  * [8] Ghilardi, S., Gianola, A., Montali, M., Rivkin, A.: Petri nets with parameterised data - modelling and verification. In: Business Process Management - 18th International Conference, BPM 2020, Seville, Spain, September 13-18, 2020, Proceedings. pp. 55–74 (2020), https://doi.org/10.1007/978-3-030-58666-9_4
  * [9] Green, T.R.: Cognitive dimensions of notations. People and computers V (1989)
  * [10] Hewelt, M., Pufahl, L., Mandal, S., Wolff, F., Weske, M.: Toward a methodology for case modeling. Softw. Syst. Model. 19(6), 1367–1393 (2020), https://doi.org/10.1007/s10270-019-00766-5
  * [11] Hewelt, M., Weske, M.: A hybrid approach for flexible case modeling and execution. In: Business Process Management Forum - BPM Forum 2016, Rio de Janeiro, Brazil, September 18-22, 2016, Proceedings. pp. 38–54 (2016), https://doi.org/10.1007/978-3-319-45468-9_3
  * [12] Hildebrandt, T.T., Mukkamala, R.R.: Declarative event-based workflow as distributed dynamic condition response graphs. In: Proceedings Third Workshop on Programming Language Approaches to Concurrency and communication-cEntric Software, PLACES 2010, Paphos, Cyprus, 21st March 2010. pp. 59–73 (2010), https://doi.org/10.4204/EPTCS.69.5
  * [13] Holfter, A., Haarmann, S., Pufahl, L., Weske, M.: Checking compliance in data-driven case management. In: Business Process Management Workshops - BPM 2019 International Workshops, Vienna, Austria, September 1-6, 2019, Revised Selected Papers. pp. 400–411 (2019), https://doi.org/10.1007/978-3-030-37453-2_33
  * [14] Hull, R.: Artifact-centric business process models: Brief survey of research results and challenges. In: On the Move to Meaningful Internet Systems: OTM, Monterrey, Mexico, November 9-14, 2008, Proceedings, Part II. pp. 1152–1163 (2008), https://doi.org/10.1007/978-3-540-88873-4_17
  * [15] Hull, R., Damaggio, E., Fournier, F., Gupta, M., Heath III, F., Hobson, S., Linehan, M.H., Maradugu, S., Nigam, A., Sukaviriya, P., Vaculín, R.: Introducing the guard-stage-milestone approach for specifying business entity lifecycles. In: Web Services and Formal Methods - 7th International Workshop, WS-FM 2010, Hoboken, NJ, USA, September 16-17, 2010. Revised Selected Papers. pp. 1–24 (2010), https://doi.org/10.1007/978-3-642-19589-1_1
  * [16] Künzle, V., Reichert, M.: PHILharmonicFlows: towards a framework for object-aware process management. J. Softw. Maintenance Res. Pract. 23(4), 205–244 (2011), https://doi.org/10.1002/smr.524
  * [17] Meyer, A., Herzberg, N., Puhlmann, F., Weske, M.: Implementation framework for production case management: Modeling and execution. In: 18th IEEE International Enterprise Distributed Object Computing Conference, EDOC, Ulm, Germany, September 1-5, 2014. pp. 190–199 (2014), https://doi.org/10.1109/EDOC.2014.34
  * [18] Montali, M., Calvanese, D.: Soundness of data-aware, case-centric processes. Int. J. on Software Tools for Technology Transfer 18(5), 535–558 (2016)
  * [19] Montali, M., Rivkin, A.: DB-Nets: On the marriage of colored Petri nets and relational databases. Trans. Petri Nets Other Model. Concurr. 12, 91–118 (2017), https://doi.org/10.1007/978-3-662-55862-1_5
  * [20] Object Management Group (OMG): Business process management (BPMN) (January 2014), https://www.omg.org/spec/BPMN
  * [21] Object Management Group (OMG): Case management model and notation (CMMN) (December 2016), https://www.omg.org/spec/CMMN
  * [22] Object Management Group (OMG): Unified modeling language (UML) (December 2017), https://www.omg.org/spec/UML
  * [23] Pesic, M., Schonenberg, H., van der Aalst, W.M.P.: DECLARE: full support for loosely-structured processes. In: 11th IEEE International Enterprise Distributed Object Computing Conference (EDOC 2007), 15-19 October 2007, Annapolis, Maryland, USA. pp. 287–300 (2007), https://doi.org/10.1109/EDOC.2007.14
  * [24] Santoro, F.M., Slaats, T., Hildebrandt, T.T., Baião, F.A.: DCR-KiPN a hybrid modeling approach for knowledge-intensive processes. In: Conceptual Modeling - 38th International Conference, ER 2019, Salvador, Brazil, November 4-7, 2019, Proceedings. pp. 153–161 (2019), https://doi.org/10.1007/978-3-030-33223-5_13
  * [25] Snoeck, M.: Enterprise Information Systems Engineering - The MERODE Approach. The Enterprise Engineering Series, Springer (2014), https://doi.org/10.1007/978-3-319-10145-3
  * [26] Steinau, S., Andrews, K., Reichert, M.: The relational process structure. In: Advanced Information Systems Engineering - 30th International Conference, CAiSE 2018, Tallinn, Estonia, June 11-15, 2018, Proceedings. pp. 53–67 (2018), https://doi.org/10.1007/978-3-319-91563-0_4
  * [27] Steinau, S., Marrella, A., Andrews, K., Leotta, F., Mecella, M., Reichert, M.: DALEC: a framework for the systematic evaluation of data-centric approaches to process management software. Softw. Syst. Model. 18(4), 2679–2716 (2019), https://doi.org/10.1007/s10270-018-0695-0


#  Literature Survey on Finding Influential Communities in Large Scale
Networks

Prakhar Ganesh  2015CS10245  Rahul Agarwal  2015CS10247  Saket Dingliwal
2015CS10254

###### Abstract

Community or modular structure is considered to be a significant property of
large scale real-world graphs such as social or information networks.
Detecting influential clusters or communities in these graphs is a problem of
considerable interest as it often accounts for the functionality of the
system. We aim to provide a thorough exposition of the topic, including the
main elements of the problem, a brief introduction of the existing research
for both disjoint and overlapping community search, the idea of influential
communities, its implications and current state of the art and finally provide
some insight on possible directions for future research.

##  I Introduction

Many large scale real-world networks like social networks consist of community
structures. Disciplines where systems are often represented as graphs, such as
sociology, biology and computer science contain examples of such large scale
networks and community structures present in them [1]. The problem of
discovering communities in a large scale network is a problem which has
attracted much attention in recent years [2, 3]. A similar problem is
community search where the goal is to find the most likely community that
contains an input query node [4, 5]. The community discovery problem is
focused on identifying all communities present in a network [2]. On the other
hand, the community search problem is a query-dependent variant of the
community discovery problem, which aims to find the community that contains
the query node [4].

An important aspect of communities, which is ignored by the older community
detection algorithms, and have been very recently introduced in these field is
the influence of a community [1]. Finding the ’r’ most influential communities
in a network has widespread applications and has fueled a lot of recent
research in this area. The common approaches used in this field includes index
based search [1], heuristics based on common graph structures like cliques
[6], k-cores [7], multi-values graphs [8], online searches, both global [1]
and local [9] and introduction of novel data structures [7] among many others.
We try to cover them all and also provide a quantitative, as well as a
qualitative, comparison between the two, along with directions for future
research.

##  II Motivation

The problem of community search over very large graphs is a fundamental
problem is graph analysis. However certain applications require us to find the
’r’ most influential communities in the graph. Consider the following examples
as described in Bi et al. [9]. Assume that Alice is a database researcher. She
may want to identify the most influential research groups from the co-
authorship network of the database community, so as to be aware of the recent
trends of database research from those influential groups. Another frequently
encountered example is in online social network domain. Suppose that Bob is an
online social network user. He may want to follow the most influential groups
in the social network, so as to track the recent activities from those
influential groups.

Both of these issues are common in the sense that they need to find
communities in a graph with an additional property of having high influence. A
possible definition of influence value can be defining it as the minimum
weight of the nodes in that community [1]. An influential community is the one
which has a large influence value, which in this case would mean every member
of the community is highly influential (since we are taking the minimum).

There has been a sudden outburst of different techniques in this field in the
last few years, both in terms of new heuristics in the detection of most
influential communities and in terms of speeding up the search algorithms. We
aim to provide a thorough survey of the current progress as an entry point for
future researchers and insights on possible future research directions.

##  III Problem Statement

Consider a Graph $G(V,E)$ where V is the set of vertices and E is the set of
edges. Let $d(v,G)$ be defined as the degree of vertex v in graph G i.e number
of edges coming out of v. A graph $H(V_{h},E_{h})$ is defined as an induced
subgraph of G if $V_{h}\subseteq V$ and $E_{h}=\\{(u,v):u,v\in V_{h},(u,v)\in
E\\}.$ A k-core is an induced subgraph where the degree of each node is
atleast k ( $d(v,H)\geq k$). A maximal k-core is a k-core which is not a
subset of any other k-core. Clearly, every graph will have a unique maximal
k-core for every values of ’k’.

To introduce the concept of influence we assign a weight to each node which
can be interpreted as its influence (such as PageRank, h-index etc). A weight
vector of a Graph is the set of all weights assigned to the nodes.

Given a graph $G(V,E)$ and an induced graph $H(V_{h},E_{h})$, we define a
function to compute the influence of this induced subgraph. One possible
definition, as discussed earlier, could be taking the minimum weight present
in the induced subgraph. The intuition behind it is that an induced subgraph
is as influential as its least influential member [1]. Another way could be
taking the average of all the weights present in the subgraph or even a more
complex function can be defined.

A k-influential community [1] is an induced subgraph $H_{k}=(V_{k},E_{k})$ of
G that :-

  1. 1.

Is connected

  2. 2.

Each node has degree atleast k

  3. 3.

Is maximal

Problem : Given a graph $G=(V,E)$, a weight vector W, and two parameters k and
r, the problem is to find the top-r k-influential communities with the highest
influence value. [1]

##  IV Algorithms Used

The problem statement for finding the most influential communities was first
formulated by Li et al [1]. They developed a formal definition of influence of
an individual and a community, and suggested various methods and optimization
to solve the problem. The idea behind their algorithm is to start with the
maximal k-core of the graph and then remove nodes from it one at a time,
following a certain rule, which will give us the communities present in the
graph in an increasing order of influence. The details of the algorithm are
discussed below.

k-core : The first step is to calculate the maximal k-core of the graph. This
will contain disjoint sets of connected components, each of them satisfying
the definition of a community. We then remove a node, present in the k-core,
which has the least influence and store its parent community. The maximal
k-core of this new graph (formed after removing the node as mentioned above)
is calculated and the whole process is repeated again, until we find no
maximal k-core.

The authors defined the influence of a community equal to the least
influential node present in the community. Due to the use of this definition,
the influence value of the community stored at any iteration will be the least
among all the communities present in the k-core at that iteration, since it
contains the node with the least influence. This ensures that the influence
value of communities stored at every iteration keeps on increasing. The final
output of the algorithm, i.e. the top-r k-influential communities, are the
communities stored in the last r iterations.

Calculating k-core for every iteration was identified by the authors as the
costliest part of the algorithm. In a graph with $m$ edges, the time taken by
the algorithm to perform $n_{k}$ iterations is $O(n_{k}m)$ [1]. It is easy to
notice that the only change between the maximal k-core of two consecutive
iterations occurs in the community from which the least influential node was
removed. Thus, as suggested by Li et al [1], we can easily avoid recalculating
the k-core at every iteration by using the k-core of the previous iteration,
and removing certain nodes from it which are not a part of the k-core anymore.
These nodes can be easily identified by performing DFS from the removed node
[1]. The optimization proposed above reduces the time complexity of our
algorithm to $O(m+n)$, where m and n represent the edges and vertices present
in the graph respectively.

ICPS : The method of using DFS is sufficiently fast when dealing with only a
single query of finding the top-r k-influential communities. However,
repeating the same process for different values of k becomes infeasible for
large graphs. A naive approach to overcome this could be to store the top-r
k-influential communities for every value of k upto some $k_{max}$. The time
complexity now will be $O(k_{max}(m+n))$ for any number of queries. An obvious
limitation to this method is the amount of space required to store the answers
for every value of k.

To counter this limitation, Li et al [7] introduced a novel data structure,
called influential community-preserved structure (ICPS). This structure
compresses and stores the top-r k-influential communities for all values of k
upto $k_{max}$ in space complexity $O(m)$. Once this data structure is
created, it takes time $O(n_{a})$, where $n_{a}$ represents the number of
vertices in the answer, to extract the answer for any query. Li et al [7] also
suggested an optimization to this precomputation, reducing the time complexity
to $O(pm)$, where p is the arboricity of the graph, m total number of edges.
The arboricity of an undirected graph is the minimum number of forests into
which its edges can be partitioned.

Forward / Backward Algorithm : Chen et al [10] provided two important
extensions to the above algorithm, namely forward and backward algorithms.
They identified the computation of Maximal Connected Component (MCC) as the
slow step of the algorithm. MCC computation is done at the end of each
iteration, to find the parent community of the deleted node. The forward
algorithm, maintain a hash table to keep track of the deleted nodes and then
computes the MCCs later in the reverse order, thereby ensuring that only the
top-r most influential communities are computed.

The backward algorithm, start with the most influential node present in the
graph and then adds nodes in decreasing order of influence. After every
addition, the algorithm checks whether the k-core property is satisfied, thus
finding the top-r k-influential communities from most influential to least.
The process is rather slow as compared to forward algorithm, however
outperforms it for very small values of r. Thus, for smaller values of r,
backward algorithm should be used, and switch to forward algorithm when the
value of r increases. Chen et al [10] also used WebGraph [11], a graph
compression framework to reduce the space complexity of the compressed graph
storage.

LocalSearch : Bi et al [9] introduced LocalSearch, a novel algorithm that
works by reducing the community search problem to a local area in a subgraph
containing only the nodes with influence greater than a threshold. The
threshold influence is chosen such that it is the minimum influence at which
there are atleast r k-influential communities in the subgraph. Any
k-influential community not found in this subgraph, but actually present in
the original graph, will have influence less than any community found in this
subgraph (since it will contain atleast one node with influence less than the
threshold). This way, the top-r k-influential communities found in this
subgraph will be the top-r k-influential communities of the complete graph.

The algorithm proposed starts with a heuristically chosen threshold and then
expands the graph until there are at least r k-influential communities in the
sub graph. To speed up the calculation of the number of k-influential
communities in a subgraph, the authors define a new term, keynode, which is
simply the least influential node of a k-community. The advantage of finding
just the keynodes is that we do not need to calculate the MCCs of the graph.
While removing least influential nodes from the k-core, as done in the forward
algorithm by Chen et al [10], the algorithm also maintains an array of all the
nodes deleted during DFS at each iteration. After all the iterations, instead
of calculating MCCs for the top r keynodes, it introduces a different
recursive method of identifying the communities. We start with all the nodes
deleted at the $(T-p)^{th}$ iteration, where T is the total number of
iterations. These are extended to include all the nodes in the $(p+1)^{th}$
k-influential community which are connected to them, thus resulting in the
$p^{th}$ k-influential community. The first k-influential community is simply
all the nodes deleted in the last iteration. The proof of correctness can be
found in [9].

kr-clique : We have been discussing till now the optimizations for the
algorithm defined by Li et al [1]. However, the definition by Li et al [1] is
not universally accepted. Wang et al [6] recently introduced a new definition
of influence, and focused on the idea of using kr-clique rather than the
traditional k-core for finding top-r k-influential communities. We will not be
discussing the definition used by them, however will discuss the algorithms
they used, since their proposed solutions can be easily translated to our
problem statement. A kr-clique is defined such that every node has k edges and
every nodes is reachable in atmost r hops from any node. This ensures more
cohesiveness in the community than a k-core, since in a k-core two nodes can
be very far from each other, which is not true in a kr-clique.

Wang et al [6] first provides a baseline algorithm for their influence model.
The algorithm iterates through all the nodes in the graph, computing maximal
kr-clique for that node and then calculating its influence. This is clearly a
brute force algorithm, not suitable for large graphs. To improve the
performance of the algorithm, the authors introduce a novel data structure,
namely C-tree, which indexes maximal r-cliques generated by the graph. C-trees
are space and time efficient when it comes to generating kr-cliques. The
authors list four methods of searching through the C-tree, sequential-order
based (SO) search, improved sequential-order based (SO+) search, best-first
based (BF) search, and fast best first based (BF+) search.

Progressive Approach : All the algorithms discussed above outputs the final
answer, i.e all the top-r k-influential communities, in one go. This leads to
a significant latency between the query and the result. To handle this Bi et
al [9] suggests a progressive approach in which the communities are generated
in decreasing order one after the other. In the first iteration, the problem
statement is finding the top-1 k-influential community. The threshold and
subgraph is selected, as mentioned in LocalSearch, and the top-1 k-influential
community is provided as the output. Now, the threshold is shifted, so as to
double the size of the subgraph. The LocalSearch now outputs another set of
k-communities. This process is repeated until the require number of
k-communities are provided.

##  V Datasets

Bi et al [9] provides an extensive comparison between the algorithms discussed
in this survey [1, 7, 9, 10] by doing experiments across a variety of
datasets. All the experimentation results presented here were taken from Bi et
al [9]. The algorithms compared are,

  1. 1.

OnlineAll :- DFS and ICPS based algorithm by Li et al [1, 7].

  2. 2.

Forward Algorithm :- Calculating MCCs for only the relevant communities, by
Chen et al [10].

  3. 3.

Backward ALgorithm :- Iterating through the most influential nodes in a
decreasing order, outperforming forward algorithm for smaller values of r, by
Chen et al [10].

  4. 4.

LocalSearch :- Local Search Algorithm as presented by Bi et al [9]

  5. 5.

LocalSearch-OA :- Local Search Algorithm presented by Bi et al [9]. But using
OnlineAll, instead of keynodes. (For comparison purpose)

  6. 6.

LocalSearch-P :- Local Algorithm algorithm with the progressive approach
integrated as shown by Bi et al [9].

Figure 1: Statistics of real graph. Image courtesy Bi et al [9]

All algorithms were implemented in C++ and compiled in GNU GCC 4.8.2 with the
-O3 flag. The experiments were conducted on Intel i5 3.20GHz CPU and 16GB main
memory [9].

Graphs : The dataset contains eight real graphs, Email, Youtube, Wiki, LiveJ,
Orkut, Arabic, UK and Twitter. The first five are from the Stanford Network
Analysis Platform [12], and the last three are from the Laboratory of Web
Algorithmics [13]. The variability across different graphs can be found in Fig
1. The two parameters r and k were varied as follows, r chosen from {5, 10,
20, 50, 100} and k chosen from {5, 10, 20, 50}. For every query the algorithms
were run three times and the average CPU time in milliseconds was reported.

Note : The running convention used by Bi et al [9] is finding the top-k
$\gamma$-influential communities, which conflicts with the conventions used in
all the papers covered in this survey. We will be sticking to our convention,
however the graphs depicted in the later sections, courtesy Bi et al [9],
contains the conventions used by them, which should not be correlated with the
variables of our convention. Each graph is provided with a descriptive label
to avoid any confusion.

Figure 2: A brief comparison across all the datasets. Value of r is varied
keeping k=10. Courtesy Bi et al [9] Figure 3: A brief comparison across all
the datasets. Value of k is varied keeping r=10. Courtesy Bi et al [9] Figure
4: Comparison of Forward Algorithm and LocalSearch-P for higher values of k
and r. Courtesy Bi et al [9] Figure 5: Comparison of Backward Algorithm and
LocalSearch-P for varying values of k and r. Courtesy Bi et al [9] Figure 6:
Comparison between LocalSearch-OA and LocalSearch-P for varying values of r,
keeping k = 10. Courtesy Bi et al [9] Figure 7: Comparison of different of
values of the ratio at which the graph is grown in LocalSearch-P, for k=10 and
r=10. Courtesy Bi et al [9] Figure 8: Comparison between LocalSearch and
LocalSearch-P for r=128, k=10 and 50. Courtesy Bi et al [9]

##  VI Comparative Analysis

The OnlineAll and Forward algorithms work on the whole graph for any value of
k and r and hence there is very little change in the total time taken for
processing queries when the values of k or r are varied. The forward algorithm
performs slightly better than the OnlineAll algorithm because of the reduced
number of Maximal Connected Component(MCC) computations. (refer to Fig 2,3,4)

The Backward algorithm starts from the most influential community and stops
when the top-r most influential communities have been found. Hence the time
taken by Backward algorithm increases with the increase in the value of r
(refer to Fig 5).

The total time for LocalSearch algorithm increases as we increase r keeping k
constant. This can be easily explained, since at a higher value of r, the
subgraph formed will be larger in size and hence the time taken will be more.
Similar reasoning can be given for varying k and keeping r constant. The
increase in the value of k means a larger sub graph is required to satisfy the
stronger cohesive property and hence an increase in total time can be seen
(refer to Fig 8).

LocalSearch-P outperforms every algorithm that we have discussed in this
paper, including the variations LocalSearch and LocalSearch-OA (refer to Fig
2,3,4,5,6,8).

A comparison was done for the time taken to output top-p k-influential
communities, p varying for 0 to r. Since LocalSearch gives the complete output
in one go, the time for every value of p is the same. However, the progressive
approach delivers the initial results almost immediately and then the time
taken gradually increases (refer to Fig 8).

##  VII Extensions

In this section we will discuss a few extensions to the problem statement as
discussed in this survey.

###  VII-A Non-containment Community Search

Following the definition of k-communities, it is possible that an influential
k-community is a subgraph of another influential k-community. However, for
most of the practical applications, one would prefer to not have such
relations present in the output. Thus the problem statement of finding top-r
non-containment influential k-communities was introduced.

OnlineAll [1] checks for every community generated whether it contains a
k-core or not and only those are considered for the final output which have no
k-cores present in it. Forward Algorithm [10] uses an additional array to
store the degree of a node and then used its value to check for non-
containment. A slight modification in LocalSearch [9] was also suggested in
the algorithm to tackle the above task. To summarize we can say that the
modified problem statement can be easily solved by providing slight
modifications to the existing algorithms.

###  VII-B Other Cohesiveness Measures

In this survey we came across two structures which were used to define
cohesiveness in a graph, the k-core definition [10, 1, 9] to ensure that each
node is connected to at least k different nodes and kr-clique [6] to
concentrate more on the compactness in a graph. The kr-clique structure puts a
limit to the maximum distance between two nodes in a community thereby
ensuring more compactness. This also results in lesser number of
k-communities. The definition of cohesiveness can depend on our need or on the
problem statement we are trying to solve and different algorithms may be
experimented with to get the best results.

###  VII-C Mutli-dimensional Influence value

Till now in our discussion, the influence of a node is a single numerical
attribute associated with it. For many practical purposes however, one single
numerical value might not be enough to represent the influence of a node. For
example, in a collaboration network every author can have multiple attributes
like number of published papers, sociability, diversity, activity etc. The
simplest approach might be to take a linear function of these attributes as
the one numerical attribute and use the algorithms discussed above but this
might not capture the details as desired. A novel community model, named the
skyline community model, was introduced recently Li et al [8] to solve this
specific problem.

##  VIII Conclusion and Future Work

We have produced a survey that can be used to get familiar with the domain of
influential community search and get the reader acquainted with the research
already done in this field. We provide an analysis of the basic k-core
algorithm used and several optimization proposed over the years. In this
survey we cover several methods for searching the top-r k-influential
communities, comparing various optimizations, and touching on the varying
definition of influence.

One possible direction of future work can be exploring even more definitions
of cohesiveness in order to obtain tightly knit communities. The other
possible direction of future work is to explore the possibility of updating of
influence of nodes online and to integrate the existing algorithms into
compressed graphs that fit in the memory. These are all interesting areas of
future work.

## References

  * [1] Rong-Hua Li, Lu Qin, Jeffrey Xu Yu, and Rui Mao.  Influential community search in large networks.  Proc. VLDB Endow., 8(5):509–520, January 2015.
  * [2] Santo Fortunato.  Community detection in graphs.  Physics Reports, 486(3):75 – 174, 2010.
  * [3] Jierui Xie, Stephen Kelley, and Boleslaw K. Szymanski.  Overlapping community detection in networks: The state-of-the-art and comparative study.  ACM Comput. Surv., 45(4):43:1–43:35, August 2013.
  * [4] Mauro Sozio and Aristides Gionis.  The community-search problem and how to plan a successful cocktail party.  In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’10, pages 939–948, New York, NY, USA, 2010. ACM.
  * [5] Wanyun Cui, Yanghua Xiao, Haixun Wang, Yiqi Lu, and Wei Wang.  Online search of overlapping communities.  In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, SIGMOD ’13, pages 277–288, New York, NY, USA, 2013. ACM.
  * [6] Jianxin Li, Xinjue Wang, Ke Deng, Xiaochun Yang, Timos Sellis, and Jeffrey Yu.  Most influential community search over large social networks.  pages 871–882, 04 2017.
  * [7] Rong-Hua Li, Lu Qin, Jeffrey Xu Yu, and Rui Mao.  Finding influential communities in massive networks.  The VLDB Journal, 26(6):751–776, December 2017.
  * [8] Rong-Hua Li, Lu Qin, Fanghua Ye, Jeffrey Xu Yu, Xiaokui Xiao, Nong Xiao, and Zibin Zheng.  Skyline community search in multi-valued networks.  In Proceedings of the 2018 International Conference on Management of Data, SIGMOD ’18, pages 457–472, New York, NY, USA, 2018. ACM.
  * [9] Fei Bi, Lijun Chang, Xuemin Lin, and Wenjie Zhang.  An optimal and progressive approach to online search of top-k influential communities.  Proc. VLDB Endow., 11(9):1056–1068, May 2018.
  * [10] Shu Chen, Ran Wei, Diana Popova, and Alex Thomo.  Efficient computation of importance based communities in web-scale networks using a single machine.  In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, pages 1553–1562. ACM, 2016.
  * [11] Prasant Mohapatra and Huamin Chen.  Webgraph: A framework for managing and improving performance of dynamic web content.  IEEE Journal On Selected Areas in Communications, 20(7):1414–1425, 2002.
  * [12] http://snap.stanford.edu/.
  * [13] http://law.di.unimi.it/datasets.php.