11institutetext: Chair of Computer Architecture and Parallel Systems,
Technical University of Munich, Germany, 11email:
{paolo.notaro<EMAIL_ADDRESS>22institutetext: Ultra-scale AIOps Lab,
Huawei Munich Research Center, Germany, 22email<EMAIL_ADDRESS>33institutetext: Department of Informatics Engineering/CISUC, University of
Coimbra, Portugal

# A Systematic Mapping Study in AIOps

Paolo Notaro 1122 0000-0003-3567-864X Jorge Cardoso 2233 Michael Gerndt 11

###### Abstract

IT systems of today are becoming larger and more complex, rendering their
human supervision more difficult. Artificial Intelligence for IT Operations
(AIOps) has been proposed to tackle modern IT administration challenges thanks
to AI and Big Data. However, past AIOps contributions are scattered,
unorganized and missing a common terminology convention, which renders their
discovery and comparison impractical. In this work, we conduct an in-depth
mapping study to collect and organize the numerous scattered contributions to
AIOps in a unique reference index. We create an AIOps taxonomy to build a
foundation for future contributions and allow an efficient comparison of AIOps
papers treating similar problems. We investigate temporal trends and classify
AIOps contributions based on the choice of algorithms, data sources and the
target components. Our results show a recent and growing interest towards
AIOps, specifically to those contributions treating failure-related tasks
(62%), such as anomaly detection and root cause analysis.

###### Keywords:

AIOps Operations & Maintenance Artificial Intelligence

##  1 Introduction

Modern society is increasingly dependent on large-scale IT infrastructures. At
the same time, the latest IT challenges impose higher levels of reliability
and efficiency on computer systems. Because of the large increase in size and
complexity of these systems, IT operators are increasingly challenged while
performing tedious administration tasks manually. This has sparked in recent
years much interest towards the study of self-managing and autonomic computing
systems to improve efficiency and responsiveness of IT services. While many
static algorithmic solutions have been proposed, these automated solutions
often show limitations in terms of adaptiveness and scalability. The presence
of large data volumes in different modalities motivates the investigation of
intelligent learning systems, able to adapt their behavior to new observations
and situations.

Artificial Intelligence for IT Operations (AIOps) investigates the use of
Artificial Intelligence (AI) for the management and improvement of IT
services. AIOps relies Machine Learning, Big Data, and analytic technologies
to monitor computer infrastructures and provide proactive insights and
recommendations to reduce failures, improve mean-time-to-recovery (MTTR) and
allocate computing resources efficiently [3]. AIOps offers a wide, diverse set
of tools for several applications, from efficient resource management and
scheduling to complex failure management tasks such as failure prediction,
anomaly detection and remediation [13, 23]. However, being a recent and cross-
disciplinary field, AIOps is still a largely unstructured research area. The
existing contributions are scattered across different conferences and apply
different terminology conventions. Moreover, the high number of application
areas renders the search and collection of relevant papers difficult. Some
previous systematic works only treat single tasks or subareas inside AIOps
[20, 31]. This motivates the need for a complete and updated study of AIOps
contributions.

In this paper, we present in-depth analysis of AIOps to cover for these
limitations. We have identified and extracted over 1000 AIOps contributions
through a systematic mapping study, enabling us to delineate common trends,
problems and tools. First, we provide an in-depth description of the
methodology followed in our mapping study (Section 2), reporting and
motivating our planning choices regarding problem definition, search,
selection and mapping. Then, we present and discuss the results drawn from our
study, including the identification of most common topics, data sources, and
target components (Section 3). Finally, Section 4 summarizes the outcomes and
conclusions treated in this work.

##  2 Methodology

###  2.1 Systematic Mapping Studies

A systematic mapping study (SMS) is a research methodology widely adopted in
many research areas, including software engineering [34]. The ultimate goal of
a SMS is to provide an overview of a specific research area, to obtain a set
of related papers and to delineate trends present inside such area. Relevant
papers are collected via predefined search and selection techniques and
research trends are identified using categorization techniques across
different aspects of the identified papers, e.g. topic or contribution type.
We choose to perform a SMS because we are interested in gathering
contributions and obtaining statistical insights about AIOps, such as the
distribution of works in different subareas and the presence of temporal
trends for particular topics. SMSs have also been shown to increase the
effectiveness of follow-up systematic literature reviews [34]. To this end, we
have also used our systematic mapping study to collect references for a survey
on failure management in AIOps separately published.

###  2.2 Planning

According to the step outline followed in [34], a systematic mapping study is
composed of:

  * •

Formulation, i.e. express the goals intended for the study through research
questions. Equally important is to clearly define the scope of investigation;

  * •

Search, i.e. define strategies to obtain a sufficiently high number of papers
within the scope of investigation. This comprises the selection of one or more
search strategies (database search, manual search, reference search, etc.);

  * •

Selection (or screening), i.e. define and apply a set of inclusion/exclusion
criteria for identifying relevant papers inside the search result set;

  * •

Data Extraction and Mapping, i.e. gather the information required to map the
selected papers into predefined categorization scheme(s). Finally, results are
presented in graphical form, such as histograms or bubble plots.

The next sections illustrate and motivate our choices regarding these four
steps for our systematic mapping study in AIOps.

###  2.3 Formulation

The main goal of this mapping study is to identify the extent of past research
in AIOps. In particular, we would like to identify a representative set of
AIOps contributions which can be grouped based on the similarity of goals,
employed data sources and target system components. We also wish to understand
the relative distribution of publications within these categories and the
temporal implications involved. Formally, we articulate the following research
questions:

RQ1. What categories can be observed while classifying AIOps contributions in
scientific literature?

RQ2. What is the distribution of papers in such categories?

RQ3. Which temporal trends can be observed for the field of AIOps?

In terms of scope, we express the boundaries of AIOps as the union of goals
and problems in IT Operations when dealt with AI techniques. To circumvent
ambiguity about the term AI, we adopt an inclusive convention where we
consider AI both date-driven approaches, such as Machine Learning and data
mining, as well as goal-based approaches, such as reasoning, search and
optimization approaches. However, we mostly concentrate our efforts on the
first category due to its stronger presence and connection to AIOps
methodologies (e.g. data collection).

###  2.4 Search and Selection

####  2.4.1 Selection Criteria

We start illustrating the selection principles beforehand, so that the
discussion will appear clearer when we describe our result collection
strategy, composed of search and selection altogether. In terms of inclusion
criteria, we define only one relevance criterion, based on the main topic of
the document. Following from our discussion on scoping such inclusion
criterion comprises two necessary conditions:

  * •

The document references one or more AI methods. These mentions can either be
part of the implementation or as part of its discussion/analysis (e.g. in a
survey). Any mention to AI algorithms employed by others (i.e. mentioned in
the related work section or as baseline comparison) that is not strictly the
focus of the document, is not considered valid;

  * •

The document applies its concepts to some kind of IT system management. We
therefore exclude papers with no specific target domain or with a target
domain outside of IT Operations.

In terms of exclusion criteria, we define the following as exclusion rules:

  * •

The language of the document is not English;

  * •

The document is not accessible online;

  * •

The document does not belong to the following categories: scientific article
(conference paper, journal article), book, white paper;

  * •

The main topic of the document is one of the following: cybersecurity,
industrial process control, cyber-physical systems, and optical sensor
networks.

For the special case of survey and review papers, we consider them relevant as
long while carrying out our mapping study, but we then exclude them from our
final result set, as these articles are useful to find other connected works
through references, but they do not constitute novel contributions to the
field.

####  2.4.2 Database Search

AI Keywords | IT Operations Keywords
---|---
(“AI” OR “artificial intelligence”) “classification” “clustering” “logistic regression” “regression” (“DL” OR “deep learning”) (“ML” OR “Machine Learning”) (“inference” OR “logic” OR “reasoning) (“supervised” OR “unsupervised” OR “semi-supervised” OR “reinforcement”) AND (“learning”) (“support vector machine” OR “SVM”) (“tree” OR “tree-based” OR “trees” OR “forest”) ((“bayesian” OR “neural”) AND “network”) (((“hidden” AND “markov”) OR (“gaussian” AND “mixture”)) AND “model”) ((“datacenter” OR “data center”) AND “management”) |  (“DevOps” OR “site reliability engineering” OR “SRE”) (“IT operations”) (“anomaly detection” OR “outlier detection”) (“cloud computing”) (“cloud”) (“fault detection” OR “failure detection”) (“fault localization” OR “failure localization”) (“fault prediction” OR “failure prediction”) (“fault prevention” OR “failure prevention”) (“log” OR “logs” OR “log analysis”) (“metrics” OR “KPI” OR “key performance indicator”) (“remediation” OR “recovery”) (“root-cause analysis” OR “root cause analysis”) (“service desk automation”) (“tracing” OR “trace” OR “traces”)

Table 1: The two keyword sets obtained via PICO used for database search.

For the search process, database search represents the first and most
important step, as it aims to provide the highest number of results and
perform an initial screening of irrelevant papers. We perform database search
in three steps: keywording, query construction and result polling. For
keywording we use the PICO technique presented in [34] to derive a set of
keywords for AI and a set of keywords for IT Operations. The keywords are
listed in Table 1. Then, following our scoping considerations, we construct
queries so that they return results where both AI and IT Operations are
present. In particular, we apply logic conjunction of keywords across all
combinations of the two keyword sets (e.g. “logistic regression” and “cloud
computing”). This helps enforcing precision in our search results. For
keywords with synonyms and abbreviations, we allow all equivalent expressions
via OR disjunction. We also perform general search queries, related to the
topic as a whole (e.g. “AIOps”). Finally, we group some queries with common
terms to reduce the number of queries.

We select three online search databases that are appropriate for the scope of
investigation: IEEE Xplore, ACM Digital Library and arXiv. For each query we
restrict our analysis to the top 2000 results returned. We aggregate results
from all searches in one large set of papers, removing duplicates and
annotating for each item corresponding search metadata (e.g. number of hits,
index position in corresponding searches, etc.). The result from this step
consists of 83817 unique articles. For each item we collect the title,
authors, year, publication venue, contribution type and citation count (from
Google Scholar).

####  2.4.3 Preliminary Filtering and Ranking-based Selection

In the filtering step we start improving the quality of our selection of
papers. First, papers are automatically excluded based on publication venue,
for those venues that are clearly irrelevant for topic reasons (e.g.
meteorology). We also exclude based on the year of publication (year $<1990$)
as it precedes the advent of large-scale IT services. By doing so, we can
exclude approximately 8000 elements.

Usually at this point, a full-text analysis would be performed on all the
available papers to screen relevant contributions using the above cited
selection rules. Although we partly filtered results, it is still not feasible
to perform an exhaustive selection analysis, even as simple as filtering by
title. It is also impractical to attempt an automated selection by content, as
it is not clear how to perform an efficient, high-recall, high-precision text
classification without supervision. Therefore, before proceeding with the rest
of the search and selection steps, we apply a ranking procedure on these
intermediate results, so that we can prioritize investigation of more relevant
papers. We apply the exclusion and inclusion rules of Section 2.4.1 to the
papers examined in ranking order.

This approximate procedure however raises the question of when it is
convenient to stop our selection and discard the remaining items. To solve
this, we develop a new approach from our observations of ranked items. We base
the method on the following assumption: a considerable ratio of relevant
papers can be identified by ranking and selecting top results using different
relevance criteria (conference, position index in the query result set, number
of hits in all queries, etc.), but in this sorting scenario we also observe a
long-tail distribution of relevant documents, i.e. some relevant papers appear
in the last positions even after sorting with our relevance heuristics (see
Figure 1). This is coherent with the known impossibility of performing
exhaustive systematic literature reviews and mapping studies, as completing
the long tail provides less results at the expense of a larger research
effort. We assume the ratio of relevant papers in the long tail to be constant
and comparable in magnitude to the number of relevant papers when sampled
randomly from the result set. Based on this assumption, we proceed as follows:

  * •

We start screening all papers in the result set, ranked according to different
relevance heuristics (e.g. number of hits in queries), and we observe the
ratio of relevant papers identified over time;

  * •

We examine the same papers in random order, and measure the same ratio;

  * •

When the two ratios are comparable, we assert we reached the tail of the
distribution of relevant papers and stop examining and selecting new papers.

As sorting criteria, we use the number of hits in the search performed in the
previous step, as well as other more complex heuristics, taking into account
the index position in result sets and the number of citations. When examining
a paper, we look into the full content to identify concepts related to our
selection criteria previously illustrated. As done previously with search
results, we gather relevant papers in one unique group. Using this stopping
criterion, we conclude this selection step when we have identified 430
relevant papers.

(a)

(b)

Figure 1: Estimated relevance probability for collected papers (y-axis), as a
function of the index in the result set (x-axis, in thousands), with paper
arranged: (a) in random order (b) using a relevance heuristic based on search
hits. We can observe how, thanks to the heuristic (b), the majority of
relevant papers can be identified by examining only a small fraction of the
set (the top results on the left side).

###  2.5 Additional Search Techniques

The “early stopping” criterion previously described, while allowing a feasible
and comprehensive selection strategy across thousands of contributions, has a
natural tendency towards discarding relevant papers. We also expect to miss
other relevant papers, not present in the initial set of 83817, because they
were not identified by our database search. To cover for these limitations, we
apply other search techniques in addition to database search. Differing from
before, we here apply our selection criteria exhaustively for each document
retrieved.

####  2.5.1 Reference Search

For each of the 430 relevant papers identified in the previous step, we search
inside their cited references. In particular, we adopt backward snowball
sampling [18]: we include in our relevant set all papers previously cited by a
relevant paper whenever they fulfill the selection requirements mentioned
above. By doing so, we obtain 631 relevant elements, for a total of 1061.

####  2.5.2 Conference Search

Reference search allows to identify prominent contributions frequently
mentioned by other authors. A drawback is the introduction of bias towards
specific research groups and authors. We also observed how reference search
rewards specific tasks and research fields as they are typically more cited.
We therefore apply other search techniques to compensate for these facts. We
perform a manual search by inspecting papers published in relevant
conferences. These relevant conferences are identified via correlation with
other relevant papers and have also been confirmed by experts in the field. We
look at the latest 3 editions of each conference, in an effort to compensate
the sampling of dated papers performed by reference search. We obtain 5 more
papers with this method.

####  2.5.3 Iterative Search Improvement

k=1 | k=2 | k=3
---|---|---
tpc-w, 1.00 (13) log-based, 0.92 (11) sla, 0.84 (48) stragglers, 0.83 (10) vm, 0.83 (59) |  defect prediction, 1.00 (34) (work)load prediction, 1.00 (32) software aging, 1.00 (13) resource allocation, 1.00 (6) hardware failures, 0.89 (8) |  software defect prediction, 1.00 (22) disk failure prediction, 1.00 (8) failure prediction model, 1.00 (7) cloud resource provisioning, 1.00 (5) automatic anomaly detection, 0.88 (7)

Table 2: Sample $k$-shingles with relevance probability (and total
occurrences).

To conclude our search, we attempt at improving our initial guess on IT
Operations keywords via analysis of the available text content (text and
abstract). Using our relevant paper set as positive samples, we perform a
statistical analysis to identify $k$-shingles (sets of $k$ consecutive tokens)
that appear often in relevant documents (Table 2). In particular, we measure
the document relevance probability given the set of shingles observed in the
available text content. We choose $k=1,\dots,5$. We use these shingles as
keywords to construct new queries along with previously used AI keywords. We
here limit the collection to 20 results per query. Thanks to this step, we
identify 20 new relevant papers. As a by-product, we get in contact with
frequently cited concepts and keywords in AIOps, later useful for taxonomy and
classification.

###  2.6 Data Extraction and Categorization

After obtaining the result set of relevant papers (counting 1086
contributions), we analyze the available information to draw quantitative
results and answer our research questions. We describe here the data
extraction process and the analysis techniques employed to gather insights and
trends for the AIOps field.

First, we classify the relevant papers according to target components and data
sources. Target components indicate a high-level piece of software or hardware
in an IT system that the document tries to enhance (e.g. hard drive for hard
disk failure prediction). We group components in five high-level categories:
code, application, hardware, network and datacenter. Data sources provide an
indication of the input information of the algorithm (such as logs, metrics,
or execution traces). Data sources are categorized in source code, testing
resources, system metrics, key performance indicators (KPIs), network traffic,
topology, incident reports, logs and traces. the “AI Method” axis denotes the
actual algorithm employed, with similar methods aggregated in bigger classes
to avoid excessive fragmentation (e.g. ‘clustering’ may contain both k-means
and agglomerative hierarchical clustering approaches). Table 3 presents a
selection of papers from the result set with the corresponding target, source
and category annotation.

Ref. Data Sources Targets Cat. Source Code Testing Resources System Metrics
KPIs/SLO data Network Traffic Topology Incident Reports Event Logs Execution
Traces Source Code Application Hardware Network Datacenter [27] $\bullet$
$\bullet$ 1.1 [32] $\bullet$ $\bullet$ $\bullet$ 1.2 [16] $\bullet$ $\bullet$
$\bullet$ 1.3 [41] $\bullet$ $\bullet$ $\bullet$ $\bullet$ 1.3 [29] $\bullet$
$\bullet$ 1.4 [47] $\bullet$ $\bullet$ 2.1 [14] $\bullet$ $\bullet$ $\bullet$
2.1 [12] $\bullet$ $\bullet$ $\bullet$ 2.1 [46] $\bullet$ $\bullet$ $\bullet$
2.1 [8] $\bullet$ $\bullet$ $\bullet$ 2.2 [11] $\bullet$ $\bullet$ $\bullet$
2.2 [17] $\bullet$ $\bullet$ $\bullet$ $\bullet$ 2.2 [35] $\bullet$ $\bullet$
$\bullet$ $\bullet$ 2.2 [24] $\bullet$ $\bullet$ $\bullet$ 2.2 [37] $\bullet$
$\bullet$ $\bullet$ $\bullet$ $\bullet$ 2.2 [45] $\bullet$ $\bullet$ 2.2 [43]
$\bullet$ $\bullet$ $\bullet$ 3.1 [42] $\bullet$ $\bullet$ 3.1 [40] $\bullet$
$\bullet$ $\bullet$ $\bullet$ 3.1 [21] $\bullet$ $\bullet$ $\bullet$ 3.1 [22]
$\bullet$ $\bullet$ $\bullet$ $\bullet$ 3.1

Ref. Data Sources Targets Cat. Source Code Testing Resources System Metrics
KPIs/SLO data Network Traffic Topology Incident Reports Event Logs Execution
Traces Source Code Application Hardware Network Datacenter [15] $\bullet$
$\bullet$ 3.1 [10] $\bullet$ $\bullet$ $\bullet$ $\bullet$ 3.1 [6] $\bullet$
$\bullet$ $\bullet$ 3.1 [28] $\bullet$ $\bullet$ 3.1 [30] $\bullet$ $\bullet$
$\bullet$ 3.2 [49] $\bullet$ $\bullet$ $\bullet$ 3.3 [1] $\bullet$ $\bullet$
$\bullet$ $\bullet$ 4.1 [33] $\bullet$ $\bullet$ $\bullet$ $\bullet$ 4.1 [5]
$\bullet$ $\bullet$ $\bullet$ 4.1 [44] $\bullet$ $\bullet$ $\bullet$ 4.2 [4]
$\bullet$ $\bullet$ $\bullet$ $\bullet$ 4.2 [19] $\bullet$ $\bullet$ $\bullet$
4.2 [9] $\bullet$ $\bullet$ $\bullet$ 4.2 [36] $\bullet$ $\bullet$ $\bullet$
4.3 [7] $\bullet$ $\bullet$ $\bullet$ $\bullet$ 4.3 [26] $\bullet$ $\bullet$
$\bullet$ 4.3 [2] $\bullet$ $\bullet$ $\bullet$ 4.3 [39] $\bullet$ $\bullet$
$\bullet$ 5.1 [48] $\bullet$ $\bullet$ $\bullet$ 5.2 [25] $\bullet$ $\bullet$
$\bullet$ $\bullet$ 5.2 [38] $\bullet$ $\bullet$ $\bullet$ $\bullet$ 5.3

(Sub)Category Legend 1.1 Software Defect Prediction 2.2 System Failure
Prediction 4.2 Root Cause Diagnosis 1.2 Fault Injection 3.1 Anomaly Detection
4.3 RCA - Others 1.3 Software Rejuvenation 3.2 Internet Traffic Classification
5.1 Incident Triage 1.4 Checkpointing 3.3 Log Enhancement 5.2 Solution
Recommendation 2.1 Hardware Failure Prediction 4.1 Fault Localization 5.3
Recovery

Table 3: Selection of result papers grouped by data sources, targets and
(sub)categories.

Then, we use the result set to infer a taxonomy based on tasks and target
goals. The taxonomy is depicted in Figure 2. We divide in AIOps contributions
in failure management (FM), the study on how to deal with undesired behavior
in the delivery of IT services; and resource provisioning, the study of
allocation of energetic, computational, storage and time resources for the
optimal delivery of IT services. Within each of these macro-areas, we further
distinguish approaches in categories based on the similarity of goals. In
failure management, these categories are failure prevention, online failure
prediction, failure detection, root cause analysis (RCA) and remediation. In
resource provisioning, we divide contributions in resource consolidation,
scheduling, power management, service composition, and workload estimation. We
further choose to expand our analysis of FM (red box of Figure 2) by applying
for this macro-area an additional subcategorization based on specific
problems. Examples of subcategories are checkpointing for failure prevention,
or fault localization for root cause analysis (see also Table 3).

Figure 2: Taxonomy of AIOps as observed in the identified contributions

##  3 Results

Figure 3: Left: distribution of AIOps papers in macro-areas and categories.
Right: percent distribution of failure management papers by category in
corresponding sub-categories.

Figure 4: Published papers in AIOps by year and categories from the described
taxonomy.

We now discuss the results of our mapping study. We first analyze the
distribution of papers in our taxonomy. The left side of Figure 3 visualizes
the distribution of identified papers by macro-area and category. Excluding
papers treating AIOps in general (8), we observe that more the majority of
items (670, 62.1%) are associated with failure management (FM), with most
contributions concentrated in online failure prediction (26.4%), failure
detection (33.7%), and root cause analysis (26.7%); the remaining resource
provisioning papers support in large part resource consolidation, scheduling
and workload prediction. On the right side, we can observe that the most
common problems in FM are software defect prediction, system failure
prediction, anomaly detection, fault localization and root cause diagnosis. To
analyze temporal trends present inside the AIOps field, we measured the number
of publications in each category by year of publication. The corresponding bar
plot is depicted in Figure 4. Overall, we observe a large, on-growing number
of publications in AIOps. We can observe how failure detection has gained
particular traction in recent years (71 publications for the 2018-2019 period)
with a contribution size larger than the entire resource provisioning macro-
area (69 publications in the same time frame). Failure detection is followed
by root cause analysis (39) and online failure prediction (34), while failure
prevention and remediation are the areas with the smallest number of attested
contributions (11 and 5, respectively).

##  4 Conclusion

In this paper, we presented our contribution towards better structuring the
AIOps field. We planned and conducted a systematic mapping study by means of
pre-established formulation, search, selection, and categorization techniques,
thanks to which we collected more than 1000 contributions and grouped into
several categories thanks to our proposed taxonomy, and differing
substantially in terms of goals, data sources and target components. In our
result section, we have shown how the majority of papers address failures in
different forms. From a time perspective, we observed a generalized on-growing
research interest, espcially for tasks such as anomaly detection and root
cause analysis.

## References

  * [1] Abreu, R., Zoeteweij, P., Gemund, A.J.v.: Spectrum-Based Multiple Fault Localization. In: IEEE/ACM International Conference on Automated Software Engineering (Nov 2009). https://doi.org/10.1109/ase.2009.25
  * [2] Aguilera, M.K., Mogul, J.C., Wiener, J.L., Reynolds, P., Muthitacharoen, A.: Performance debugging for distributed systems of black boxes. ACM SIGOPS Operating Systems Review 37(5), 74–89 (Dec 2003). https://doi.org/10.1145/1165389.945454
  * [3] Andrew Lerner: AIOps Platforms (Aug 2017), https://blogs.gartner.com/andrew-lerner/2017/08/09/aiops-platforms/
  * [4] Attariyan, M., Chow, M., Flinn, J.: X-ray: automating root-cause diagnosis of performance anomalies in production software. In: Proceedings of the 10th USENIX conference on Operating Systems Design and Implementation. pp. 307–320. OSDI’12, Hollywood, CA, USA (Oct 2012). https://doi.org/10.5555/2387880.2387910
  * [5] Bahl, P., Chandra, R., Greenberg, A., Kandula, S., Maltz, D.A., Zhang, M.: Towards highly reliable enterprise network services via inference of multi-level dependencies. In: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications - SIGCOMM (2007). https://doi.org/10.1145/1282380.1282383
  * [6] Barham, P., Isaacs, R., Mortier, R., Narayanan, D.: Magpie: online modelling and performance-aware systems. In: Proceedings of the 9th conference on Hot Topics in Operating Systems - Volume 9. p. 15. HOTOS’03, Lihue, Hawaii (May 2003). https://doi.org/10.5555/1251054.1251069
  * [7] Bodik, P., Goldszmidt, M., Fox, A., Woodard, D.B., Andersen, H.: Fingerprinting the datacenter: automated classification of performance crises. In: Proceedings of the 5th European conference on Computer systems - EuroSys ’10 (2010). https://doi.org/10.1145/1755913.1755926
  * [8] Chalermarrewong, T., Achalakul, T., See, S.C.W.: Failure Prediction of Data Centers Using Time Series and Fault Tree Analysis. In: IEEE 18th International Conference on Parallel and Distributed Systems (Dec 2012). https://doi.org/10.1109/icpads.2012.129
  * [9] Chen, M., Kiciman, E., Fratkin, E., Fox, A., Brewer, E.: Pinpoint: problem determination in large, dynamic Internet services. In: Proceedings of IEEE International Conference on Dependable Systems and Networks (Jun 2002). https://doi.org/10.1109/dsn.2002.1029005
  * [10] Chow, M., Meisner, D., Flinn, J., Peek, D., Wenisch, T.F.: The Mystery Machine: End-to-end Performance Analysis of Large-scale Internet Services. In: OSDI’14: Proceedings of the 11th USENIX conference on Operating Systems Design and Implementation. pp. 217–231 (2014). https://doi.org/10.5555/2685048.2685066
  * [11] Cohen, I., Goldszmidt, M., Kelly, T., Symons, J., Chase, J.S.: Correlating instrumentation data to system states: a building block for automated diagnosis and control. In: Proceedings of the 6th USENIX Conference on Symposium on Operating Systems Design & Implementation. OSDI’04 (2004). https://doi.org/10.5555/1251254.1251270
  * [12] Costa, C.H., Park, Y., Rosenburg, B.S., Cher, C.Y., Ryu, K.D.: A System Software Approach to Proactive Memory-Error Avoidance. In: SC14: International Conference for High Performance Computing, Networking, Storage and Analysis (Nov 2014). https://doi.org/10.1109/sc.2014.63
  * [13] Dang, Y., Lin, Q., Huang, P.: AIOps: Real-World Challenges and Research Innovations. In: IEEE/ACM 41st International Conference on Software Engineering: Companion (May 2019). https://doi.org/10.1109/icse-companion.2019.00023
  * [14] Davis, N.A., Rezgui, A., Soliman, H., Manzanares, S., Coates, M.: FailureSim: A System for Predicting Hardware Failures in Cloud Data Centers Using Neural Networks. In: IEEE 10th International Conference on Cloud Computing (CLOUD) (Jun 2017). https://doi.org/10.1109/cloud.2017.75
  * [15] Du, M., Li, F., Zheng, G., Srikumar, V.: DeepLog: Anomaly Detection and Diagnosis from System Logs through Deep Learning. In: Proceedings of ACM SIGSAC Conference on Computer and Communications Security (Oct 2017). https://doi.org/10.1145/3133956.3134015
  * [16] Garg, S., van Moorsel, A., Vaidyanathan, K., Trivedi, K.: A methodology for detection and estimation of software aging. In: Proceedings Ninth International Symposium on Software Reliability Engineering (Cat. No.98TB100257). IEEE Comput. Soc (1998). https://doi.org/10.1109/issre.1998.730892
  * [17] Islam, T., Manivannan, D.: Predicting Application Failure in Cloud: A Machine Learning Approach. In: 2017 IEEE International Conference on Cognitive Computing (ICCC) (Jun 2017). https://doi.org/10.1109/ieee.iccc.2017.11
  * [18] Jalali, S., Wohlin, C.: Systematic literature studies: Database searches vs. backward snowballing. In: Proceedings of the 2012 ACM-IEEE International Symposium on Empirical Software Engineering and Measurement. pp. 29–38 (Sep 2012). https://doi.org/10.1145/2372251.2372257
  * [19] Kandula, S., Katabi, D., Vasseur, J.P.: Shrink: a tool for failure diagnosis in IP networks. In: Proceedings of the 2005 ACM SIGCOMM workshop on Mining network data - MineNet ’05 (2005). https://doi.org/10.1145/1080173.1080178
  * [20] Kobbacy, K.A.H., Vadera, S., Rasmy, M.H.: AI and OR in management of operations: history and trends. Journal of the Operational Research Society 58(1), 10–28 (Jan 2007). https://doi.org/10.1057/palgrave.jors.2602132
  * [21] Lakhina, A., Crovella, M., Diot, C.: Diagnosing network-wide traffic anomalies. In: Proceedings of the 2004 Conference on Applications, technologies, architectures, and protocols for computer communications - SIGCOMM ’04. ACM Press (2004). https://doi.org/10.1145/1015467.1015492
  * [22] Lakhina, A., Crovella, M., Diot, C.: Mining anomalies using traffic feature distributions. In: Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications - SIGCOMM ’05. ACM Press (2005). https://doi.org/10.1145/1080091.1080118
  * [23] Li, Y., Jiang, Z.M.J., Li, H., Hassan, A.E., He, C., Huang, R., Zeng, Z., Wang, M., Chen, P.: Predicting Node Failures in an Ultra-Large-Scale Cloud Computing Platform: An AIOps Solution. ACM Transactions on Software Engineering and Methodology 29(2) (Apr 2020). https://doi.org/10.1145/3385187
  * [24] Liang, Y., Zhang, Y., Xiong, H., Sahoo, R.: Failure Prediction in IBM BlueGene/L Event Logs. In: Seventh IEEE International Conference on Data Mining (ICDM) (Oct 2007). https://doi.org/10.1109/icdm.2007.46
  * [25] Lin, F., Beadon, M., Dixit, H.D., Vunnam, G., Desai, A., Sankar, S.: Hardware Remediation at Scale. In: 2018 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks Workshops (DSN-W) (Jun 2018). https://doi.org/10.1109/dsn-w.2018.00015
  * [26] Lin, Q., Zhang, H., Lou, J.G., Zhang, Y., Chen, X.: Log clustering based problem identification for online service systems. In: Proceedings of the 38th ACM International Conference on Software Engineering Companion (ICSE) (2016). https://doi.org/10.1145/2889160.2889232
  * [27] Menzies, T., Greenwald, J., Frank, A.: Data Mining Static Code Attributes to Learn Defect Predictors. IEEE Transactions on Software Engineering 33(1), 2–13 (Jan 2007). https://doi.org/10.1109/TSE.2007.256941
  * [28] Mike Y. Chen, Accardi, A., Kiciman, E., Lloyd, J., Patterson, D., Fox, A., Brewer, E.: Path-based failure and evolution management. In: Proceedings of the 1st Conference on Symposium on Networked Systems Design and Implementation - Volume 1. p. 23. NSDI’04, San Francisco, California (Mar 2004). https://doi.org/10.5555/1251175.1251198
  * [29] Moody, A., Bronevetsky, G., Mohror, K., Supinski, B.R.d.: Design, Modeling, and Evaluation of a Scalable Multi-level Checkpointing System. In: 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis (Nov 2010). https://doi.org/10.1109/sc.2010.18
  * [30] Moore, A.W., Zuev, D.: Internet Traffic Classiﬁcation Using Bayesian Analysis Techniques. In: Proceedings of the 2005 ACM International Conference on Measurement and modeling of computer systems - SIGMETRICS ’05 (2005). https://doi.org/10.1145/1064212.1064220
  * [31] Mukwevho, M.A., Celik, T.: Toward a Smart Cloud: A Review of Fault-tolerance Methods in Cloud Systems. IEEE Transactions on Services Computing pp. 1–1 (2018). https://doi.org/10.1109/tsc.2018.2816644
  * [32] Natella, R., Cotroneo, D., Duraes, J.A., Madeira, H.S.: On Fault Representativeness of Software Fault Injection. IEEE Transactions on Software Engineering 39(1), 80–96 (Jan 2013). https://doi.org/10.1109/tse.2011.124
  * [33] Nguyen, H., Shen, Z., Tan, Y., Gu, X.: FChain: Toward Black-Box Online Fault Localization for Cloud Systems. In: IEEE 33rd International Conference on Distributed Computing Systems (Jul 2013). https://doi.org/10.1109/icdcs.2013.26
  * [34] Petersen, K., Vakkalanka, S., Kuzniarz, L.: Guidelines for conducting systematic mapping studies in software engineering: An update. Information and Software Technology 64, 1–18 (Aug 2015). https://doi.org/10.1016/j.infsof.2015.03.007
  * [35] Pitakrat, T., Okanović, D., van Hoorn, A., Grunske, L.: Hora: Architecture-aware online failure prediction. Journal of Systems and Software 137, 669–685 (Mar 2018). https://doi.org/10.1016/j.jss.2017.02.041
  * [36] Podgurski, A., Leon, D., Francis, P., Masri, W., Minch, M., Sun, J., Wang, B.: Automated support for classifying software failure reports. In: Proceedings of IEEE 25th International Conference on Software Engineering (2003). https://doi.org/10.1109/icse.2003.1201224
  * [37] Salfner, F., Malek, M.: Using Hidden Semi-Markov Models for Effective Online Failure Prediction. In: 26th IEEE International Symposium on Reliable Distributed Systems (SRDS) (Oct 2007). https://doi.org/10.1109/srds.2007.35
  * [38] Samir, A., Pahl, C.: A Controller Architecture for Anomaly Detection, Root Cause Analysis and Self-Adaptation for Cluster Architectures. In: Intl Conf Adaptive and Self-Adaptive Systems and Applications (2019). https://doi.org/10993/42062
  * [39] Shao, Q., Chen, Y., Tao, S., Yan, X., Anerousis, N.: Efficient ticket routing by resolution sequence mining. In: Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD (2008). https://doi.org/10.1145/1401890.1401964
  * [40] Sharma, A.B., Chen, H., Ding, M., Yoshihira, K., Jiang, G.: Fault detection and localization in distributed systems using invariant relationships. In: 43rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN) (Jun 2013). https://doi.org/10.1109/dsn.2013.6575304
  * [41] Vaidyanathan, K., Trivedi, K.: A Comprehensive Model for Software Rejuvenation. IEEE Transactions on Dependable and Secure Computing 2(2), 124–137 (Feb 2005). https://doi.org/10.1109/tdsc.2005.15
  * [42] Xu, H., Feng, Y., Chen, J., Wang, Z., Qiao, H., Chen, W., Zhao, N., Li, Z., Bu, J., Li, Z., al, e.: Unsupervised Anomaly Detection via Variational Auto-Encoder for Seasonal KPIs in Web Applications. In: Proceedings of the 2018 World Wide Web Conference on World Wide Web (2018). https://doi.org/10.1145/3178876.3185996
  * [43] Xu, W., Huang, L., Fox, A., Patterson, D., Jordan, M.I.: Detecting large-scale system problems by mining console logs. In: Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles - SOSP ’09 (2009). https://doi.org/10.1145/1629575.1629587
  * [44] Yuan, D., Mai, H., Xiong, W., Tan, L., Zhou, Y., Pasupathy, S.: SherLog: error diagnosis by connecting clues from run-time logs. ACM SIGARCH Computer Architecture News 38(1), 143–154 (Mar 2010). https://doi.org/10.1145/1735970.1736038
  * [45] Zhang, K., Xu, J., Min, M.R., Jiang, G., Pelechrinis, K., Zhang, H.: Automated IT system failure prediction: A deep learning approach. In: IEEE International Conference on Big Data (Dec 2016). https://doi.org/10.1109/bigdata.2016.7840733
  * [46] Zhang, S., Meng, W., Bu, J., Yang, S., Liu, Y., Pei, D., Xu, J., Chen, Y., Dong, H., Qu, X., al, e.: Syslog processing for switch failure diagnosis and prediction in datacenter networks. In: IEEE/ACM 25th International Symposium on Quality of Service (IWQoS) (Jun 2017). https://doi.org/10.1109/iwqos.2017.7969130
  * [47] Zheng, S., Ristovski, K., Farahat, A., Gupta, C.: Long Short-Term Memory Network for Remaining Useful Life estimation. In: IEEE International Conference on Prognostics and Health Management (ICPHM) (Jun 2017). https://doi.org/10.1109/icphm.2017.7998311
  * [48] Zhou, W., Tang, L., Li, T., Shwartz, L., Grabarnik, G.Y.: Resolution recommendation for event tickets in service management. In: IFIP/IEEE International Symposium on Integrated Network Management (IM) (May 2015). https://doi.org/10.1109/inm.2015.7140303
  * [49] Zhu, J., He, P., Fu, Q., Zhang, H., Lyu, M.R., Zhang, D.: Learning to Log: Helping Developers Make Informed Logging Decisions. In: IEEE/ACM 37th IEEE International Conference on Software Engineering (May 2015). https://doi.org/10.1109/icse.2015.60


# Behavior patterns of 15-year-old students in a Digital Storytelling in
Mathematics. A social network analysis

A.Concas Department of Mathematics and Computer Science, University of di
Cagliari, via Ospedale 72, 09123 Cagliari, Italy. E-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS>M. Polo11footnotemark: 1

###### Abstract

This paper presents the preliminary considerations of the application of a
software to an experimental work conducted on the Digital Storytelling in
Mathematics, as part of the project Prin 2015 “Digital Interactive
Storytelling in Mathematics: a competence-based social approach”. An activity
designed for promoting the critical mathematical thinking among the students
that foresees them to participate as active protagonists and as observers of
the protagonists during the problem solving activity, will be illustrated and
then the outcomes will be examined from a numerical analysis point of view. In
particular, the interactions between the partecipants will be investigated by
using a Matlab software for solving the _seriation problem_.

##  1 Introduction

In this paper, the e-learning topic in the mathematical education is addressed
from a point of view of an analysis of the potentiality and also of the
drawbacks of using online platforms as an instrument for helping the learning
process. The aim consists in proving how, also in this context, virtual
interactions between the participants is fundamental. Indeed it can be
observed that the interactions within groups of students or with an expert may
modify the educational development.

In particular, we present some results of an analysis of the social
interactions between the students of a class which took part to a trial
project in January 2020 within the PRIN project titled “Digital Interactive
Storytelling in Mathematics: A Competence-based Social Approach”.

This work refers to an experimentation related to a design online competence-
oriented activities, making use of narrative and social approaches, developed
within the aforementioned PRIN research project.

In this paper we will focus on the analysis of a case study concerning the
analysis, by using numerical techniques in the the complex network theory
framework, of the behaviours of the teacher and the students in an activity
devoted to promote the critical thinking and argumentation in mathematics [6,
8]. The aim of the work is to validate the toolbox [3] in a didactis framework
and shed light on how the analysis of complex networks might be fruitful in a
DIST-M (Digital Interactive Storytelling in Mathematics) environment.

##  2 Theoretical framework

The whole PRIN project is framed in a Vygotskian approach in which social
interaction and communication play a key role in the evolution of students and
language has been widely recognized as fundamental in learning mathematics.
Students’ participation in social interactions and in communication is the key
to their evolution and the appropriation of cultural tools, such as language;
see [16]. According to Sfard [19], thought is a form of communication and
languages do not are just couriers of pre-existing meanings, but they are
builders of meanings themselves.

The idea of implementing a teaching/learning process into a digital
interactive storytelling using Moodle, where students are immersed as actors
or observers, fits the idea of expanding the context of mathematics education
beyond the classroom [14]. This expansion occurs along the layer of bridging
elements from societal practices in mathematics instruction: indeed, students
are more and more involved in digital games/stories outside the school. The
DIST-M would bring such elements into mathematics education practices,
bridging the agency of experts in mathematics knowledge and the motivation of
the students. It also allows to add on the school activity system with new
societal components, such as rules, community and division of labour [18]. In
the presented case study, students and teacher are engaged in a suitable
designed online activity, where the interactions among students and students-
teacher are well organized. The organization of the activity foresees that the
roles can be played as actors or as observers [8]. Nevertheless, “the very
subject of learning is transformed from isolated individuals to collectives”
[15]. Thus learning does not depend on a single role and the related actions,
but on the whole group, as a system. In this paper we will analyze the outcome
of a pilot, with particular reference to the students who played the roles
played as observers.

Following Wegner [7] the learning mechanisms as negotiation, as a response to
the pedagogical intentions of the context, but also considering that the
purpose of educational planning is not to appropriate learning and
institutionalize it in a structured process, but to support the formation of
learning communities.

The learning process is interpreted as a social way of changing the
participation from peripheral to a community practice involvement. This
process develops in a cooperative approach [28, 32] which aims to create a
situation where individual success is determined or influenced by the success
of the group.

This learning view point and the collaborative learning [28] complement each
other even if the intercation roles of equals are not a priori established.

The roles assigned to the actors who participated to the project, allowed the
cohesiveness between the knowledges leading to a real educational organization
[9] and the cohesion between the the different perspectives of the
participants plays a crucial function [10].

In Polo et all. [4, 6] the authors presented a social analysis of the
interactions among the students involved in a trial of the PRIN project
“Digital Interactive Storytelling in Mathematics: a Competence-based Social
Approach”. The project is designed within a digital storytelling framework
where the story follows the interactions among the characters played by the
students and an expert (teacher or researcher). We report the results of a
trial that involved teachers and students from the upper secondary school
analysing from a Social Network Analysis point of view the interventions of
the expert, the involvement / participation of the students and the
interactions among peers and with the expert. We also briefly discuss the
potential and limitations of the currently available tools to perform this
kind of analysis, in view of the much broader perspective offered by the
Learning Analytics approach.

As mentioned previously, this work regards a social network analysis carried
out by modelling the experimentation trial as a seriation problem. Online
communication tools contribute the creation of communities of practice and
learning online allowing the interactions in an online education environment;
see [22] and the references therein. In this framework, the seriation problem
consists in finding an ordering of the set of considered units, which
represent the students in a specific group according to a given correlation
function so that elements with higher similarity in the behaviour are close to
each other in the resulting sequence obtained by applying a toolbox recently
developed in Matlab [3]

##  3 Methodology and research hypothesis

The activities are framed in a narrative, in which there are characters that
will act as avatars for the various participating students. For more details
about the design of the activity see [6, 8]. The activites included in the
trial can be contextualize in the Digital Interactive Storytelling framework
described in [4].

###  3.1 Didactical modeling

The design is structured in such a way that it includes both individual and
collaborative work and discussion with the expert who acts as a mediator by
intervening when necessary. This moderation concerns not only helping the
students with the mathematical problem they have to solve but it affects also
the communicative part when the students have to formalize the solution they
found together. Different tools have been considered in the analysis.
Communication tools, like the chat the students used to communicate within
their group, through which we were able to observe the usage of different kind
of registers (colloquial vs. literate). Tools like shared files allowed the
students to develop a higher collaboration; while supporting tools such as
spreadsheets, CAS, calculators and word blocks have been made available for
inquiry, formalization and proof.

The schema for the entire DIST-M activity evolves into different phases, each
one corresponding to a specific episode in the story. The first phase is the
exploration one where a concise description of what has been observed is
proceduced. The description is then refined in the second phase in order to
obtain a statement that serves as a conjecture. This utterance, is manipulated
in the third phase in order to arrive at its appropriate formalization and to
be adjusted to lead to a proof. In the fourth stage, students are asked to
identify and organize the arguments into an appropriate deductive chain,
justifying each step of the deduction, in order to construct the proof. In the
last phase, reflection is required, both as an evaluation on the cognitive
level -students have to read again the story from the mathematical point of
view- and as a self-assessment, on the metacognitiveand affective level -each
student is asked to think about the roles played as an “actor” or as an
“active observer”.

The instructional activities take place in the context of a narrative, in a
situation that aims to be engaging and familiar to the student. The story
evolves over time and each student is a character in the story (Albano et al.,
2019). Personal and group interaction is moderated by the teacher playing
herself a character in the story. As the narrative progresses, the story
evolves in accordance with the characters’ interaction with it. The genre
chosen was that of science fiction, which sees a group of four friends Marco,
Clara, Federico and Sofia engaged in the challenge of communicating with the
aliens from whom they had received some mysterious messages made of numbers
and operations. Alongside the friends, there is also an adult, who is the
avatar of the teacher/tutor and acts as an expert in the learning path. The
story is organized in 5 episodes, where students play as characters: Marco
(the Boss) is the leader of the group and takes care to organize the tasks
among his peers; Clara (the Pest) intervenes by posing doubts and question
about the mathematical problem; Sofia (the Blogger) loves writing and takes
care to summarizes the answers shared by the group; Federico (the Promoter)
proposes new ideas and paths to follow. They are given a role (which changes
from one episode to the other) and some actions to perform, according to the
role the students are playing in that episode. Some tasks are individual, some
others are collaborative and therefore require a good grade of communication
and coordination (students can talk to each other in a chat). In order to
allow all students to play within the story, we arranged them in teams of 4
members (one for each of the above characters). In each episode, only one team
is actively involved within the story and each member plays a different
character; they can interact among themselves and with the story. In the
meantime, the members of the other teams play as Observers, each member of a
team observing a different character. These are actively involved in taking
notes in their personal logbooks, reporting how (and how well) the observed
active character performed. In the subsequent episode, another team becomes
active and all the roles are switched in turn. In this way all students will
experience all roles and all activities of the story, though not always as an
active player.

###  3.2 Numerical modeling

From a numerical point of view, this paper is related to an application of
seriation to the Social Network Analysis and in particular for analysing the
roles played by students in the digital interactive storytelling pilot project
described above. Seriation is a fundamental combinatorial ordering problem,
asking to find the best enumeration order of a set of units, according to a
given correlation function, so that elements with higher similarity are close
to each other in the resulting sequence. The desired order can be
characteristic of the data, a chronological order, a gradient or any
sequential structure of the data. We will state the seriation problem from the
mathematical point of view by considering it as the arrangement of units in a
sequence according to a “similarity” function. The concept of seriation has
been formulated in many different ways and the seriation problem, along with
seriation methods and algorithms, emerges and finds application in a wide
range of contexts spanning from archaeology, anthropology, to genomics and DNA
sequencing, and, within mathematics, from complexity theory to combinatorial
optimisation, graph theory and operational research. The interested reader can
find an overview on the context and application of seriation in [5] and
references therein. The concept of seriation first arose in the archaeological
field; see [11] for a review on the seriation problem in archaeology with a
mathematical perspective. In all the applications, seriation data are usually
given in terms of a matrix, called _data matrix_ , whose rows or columns (or
both) represent the elements to be ordered. Considering the application in
this research project, the rows of the data matrix represent the partecipants
while the columns represent the features divided, as explained below in
details, into principal and secondary features. Each player is characterized
by the role she/he plays in the considered episodes and by the partecipation
in terms of messages written on chat.

The data matrix will be hereafter named _adjacency matrix_ since it describes
a bipartite graphs which allows to define the interrelationship between the
units/roles we want to rearrange according to the observed variables.

Bipartite graphs, also called “two-mode” networks in the sociology literature,
represent the membership of nodes in groups. Indeed, a graph is bipartite if
its vertices can be split into two disjoint subsets such that only edges
between nodes belonging to different sets can occur. Formally, bipartite
networks can be defined as follows.

######  Definition 1.

A graph $G$ is _bipartite_ if its vertices can be divided into two disjoint
sets $U$ and $V$ containing $n$ and $m$ nodes, respectively, such that every
edge connects a node in $U$ to one in $V$.

In our research environment metaphor, the two disjoint nodes sets $U$ and $V$
represent the players (students and teacher) (i.e. units we want to somehow
rearrange according to the role they play) and the features related to them,
respectively.

In this framework, the adjacency matrix of order $n\times m$ can be
interpreted as the upper-right block of the adjacency matrix of the associated
bipartite graph

$\mathcal{A_{B}}=\begin{bmatrix}0_{n}&A\\\
A^{T}&0_{m}\end{bmatrix}\in{\mathbb{R}}^{(n+m)\times(n+m)},$

with $0_{n}$ and $0_{m}$ null matrices of order $n$ and $m$ respectively and
the adjacency matrix $A\in{\mathbb{R}}^{n\times m}$ describes the connections
between the two node sets and it is obtained by setting

$a_{i,j}=\begin{cases}1\quad\text{\footnotesize{if player $i$ presents
features of type $j$}}\\\ 0\quad\text{\footnotesize{otherwise}}\end{cases}.$

In case of elements $a_{i,j}\neq 1$, then the adjacency matrix is usually
called abundance matrix in the seriation problem. In this case every entry
represents the relative frequency or the number of features (played role and
considered variables) related to the considered player. As stated above, we
will follow the typical terminology used in complex networks theory and we
refer to a binary representation of seriation data as an adjacency matrix.

The first mathematical definition of seriation was based on the construction
of a symmetric matrix $S$ known as _similarity_ matrix, where the element
$s_{i,j}$ describes, in some way, the likeness of the nodes $i,j\in U$
representing two units (i.e. partecipants). One possible definition of the
similarity matrix is through the product $S=AA^{T}$, being $A$ the adjacency
matrix of the considered problem. Even in the presence of abundance data, the
matrix we will consider as adjacency matrix describing the case study will be
binary and constructed by setting equal to 1 every non zero entry. This choice
is required by the fact that the software used for processing the data can
only, up until now, manipulate binary seriation data. In the similarity matrix
the largest value on each row is the diagonal element, which reports the
number of variables associated to each unit/partecipant. By permuting the rows
and columns of $S$ in order to cluster the largest values close to the main
diagonal, one obtains a permutation of the corresponding rows of $A$ that
places the people similar in behaviour closer to each other. Summarizing, one
can map the set of pairwise relative measurements among the objects to a
similarity matrix which represents the information of the objects/units to be
ordered. Then, the seriation problem can be modeled as a discrete optimization
problem, whose goal is to find a permutation of the rows and columns of the
similarity matrix which minimizes a given objective function. Methods based on
the similarity matrix differ from one to another on how the similarity matrix
is constructed or because of different objective functions used for evaluate
the found permutations of the seriation data matrix.

In this paper we applied a Matlab toolbox described in [3] with the aim of
validating the software in a didactical research setting. The toolbox contains
an implementation of a spectral algorithm for obtaining the solution of the
seriation problem based on the use of an eigenvector, called Fiedler vector
and associated to the eigenvalue, called Fiedler value of the Laplacian matrix
associated to the problem. The algorithm, by using the sorted entries of the
Fiedler vector, returns a classification of the ordering permutations in terms
of a compact data structure called PQ-tree briefly described hereafter. The
package, named PQser toolbox, also defines a data structure to store a PQ-tree
and provides the Matlab functions to manipulate and visualize it. The detailed
description of the spectral algorithm is skipped here for the sake of brevity,
but the interested reader can refer to [3]. In the following subsection we
focuse on the outcome of the spectral algorithm that encode all the possible
reorderings of the units/roles.

A PQ-tree is a data structure introduced by Booth and Lueker [13] to encode a
family of permutations of a set of elements and solve problems connected to
finding admissible permutations according to specific rules. A PQ-tree $T$
over a set $U=\\{u_{1},u_{2},\ldots,u_{n}\\}$ is a rooted, ordered tree whose
leaves are in one-to-one correspondence with the elements of $U$ and their
order gives a reordering of the elements of the considered set. The internal
(non-leaf) nodes of $T$ are distinguished as either P-nodes or Q-nodes. The
only difference between them is the way in which their children can be
reordered. Namely, for a P-node, its children may be arbitrarily reordered so
all possible permutations of the children leaves are permitted; for a Q-node
only one order and its reverse are allowed since the children leaves may be
ordered only left-to-right or right-to-left. The root of the tree can be
either a P or a Q-node. We will represent graphically a P-node by a circle,
and a Q-node by a rectangle. The leaves of T will be displayed as triangles,
and labeled by the elements of U. The frontier of T is one possible
permutation of the elements of U, obtained by reading the labels of the leaves
from left to right.

Hence, a PQ-tree represents in a compact way permutations of the elements of a
set through admissible reorderings of its leaves. Each transformation
specifies an allowed reordering of the nodes within a PQ-tree. For example, a
tree with a single P-node represents the equivalence class of all permutations
of the elements of U, while a tree with a single Q-node represents both the
left-to-right and right-to-left orderings of the leaves. A tree with a mixed
P-node and Q-node structure represents the equivalence class of a constrained
permutation, where the structure of the tree determines the constraints on the
admissible permutations. Figure 1 displays a PQ-tree with a P node as root and
all the admissible permutations it represents and encodes. Both the figure and
the permutations encoded in the tree have been obtained by applying specific
functions contained in the PQser toolbox.

1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---
1 | 2 | 3 | 6 | 5 | 4
1 | 3 | 2 | 4 | 5 | 6
1 | 3 | 2 | 6 | 5 | 4
2 | 1 | 3 | 4 | 5 | 6
2 | 1 | 3 | 6 | 5 | 4
2 | 3 | 1 | 4 | 5 | 6
2 | 3 | 1 | 6 | 5 | 4
3 | 1 | 2 | 4 | 5 | 6
3 | 1 | 2 | 6 | 5 | 4
3 | 2 | 1 | 4 | 5 | 6
3 | 2 | 1 | 6 | 5 | 4
4 | 5 | 6 | 1 | 2 | 3
4 | 5 | 6 | 1 | 3 | 2
4 | 5 | 6 | 2 | 1 | 3
4 | 5 | 6 | 2 | 3 | 1
4 | 5 | 6 | 3 | 1 | 2
4 | 5 | 6 | 3 | 2 | 1
6 | 5 | 4 | 1 | 2 | 3
6 | 5 | 4 | 1 | 3 | 2
6 | 5 | 4 | 2 | 1 | 3
6 | 5 | 4 | 2 | 3 | 1
6 | 5 | 4 | 3 | 1 | 2
6 | 5 | 4 | 3 | 2 | 1

Figure 1: On the left, a PQ-tree over the set $U=\\{1,\ldots,6\\}$; on the
right, the 24 admissible permutations encoded in the tree.

Now, we briefly decribe the spectral algorithm we applied for analizing the
case study as described in the following. In case of a reducible similarity
matrix, it can be proved that the seriation problem can be decoupled [1]. The
spectral algorithm detect irreducible blocks of the similarity matrix
identifying also the corresponding index sets. The irreducible blocks
correspond to the connected components of the considered graph. If more than
one connected component is found, then the function calls itself on each
component, and stores the returned lists of nodes as children of a P-node. If
the similarity matrix of the considered problem is irreducible, the dimension
$n$ of the matrix is considered. The cases $n=1,\quad 2$ are trivial. If
$n>2$, the Laplacian matrix $L$ of $S$ is computed, as well as the Fiedler
value and the correspinding eigenvector. The PQser toolbox computes by default
the eigenpairs corresponding to the three eigenvalues of smallest magnitude,
since they are sufficient to understand if the Fiedler value is simple or
multiple, but the default value can be modified. The algorithm determines the
multiplicity of the Fiedler value according to a given tolerance. If the
Fiedler value is a simple eigenvalue of L, the algorithm sorts the elements of
the current list according to the reordering of the Fiedler vector and stores
them as the children of a Q-node. If two or more values of the Fiedler vector
are repeated, the function invokes itself recursively; on the contrary, the
corresponding node becomes a leaf In the presence of a multiple Fiedler
vector, the problem is not well posed and an approximate solution is computed,
as described in [3]. The number $N$ of all the admissible permutations
generated by the algorithm can be obtained by counting all the admissible
boundaries of the tree.

In this framework, with the aim of validating the PQser toolbox in a didatics
field, we applied the software in order to find all the admissible reordering
of the units, i.e., the people involved in the considered pilot project on the
basis of their behaviour studied through the chat they used during the trial.

##  4 Case study

In this section we analyze the first episode of the final prototype
experimented in January 2020. The group of the participants of this project is
composed by 26 students and the teacher who, as already mentioned, assumed the
role of a mediator in the group of the 4 students who play the actors role.
The story evolves in 5 episodes and in each one of them the students play a
different role being an actor or an observer in a different group; see [6].
The aim behind the narration is the solution of a mathematical problem by
proving that, given four consecutive natural numbers, the difference between
the product of the first and the fourth and the product between the second and
the third is always equal to 2. The four principal roles, assigned to the
students who are actors, are of the _Peste Clara_ , the _Blogger Sofia_ , the
_Boss Marco_ and the _Promoter Federico_.

All the 26 students have been divided into 6 groups indicated thereafter as
$g_{i}$ for $i=1,\ldots,6$. The group $g_{1}$ identifies, in each episode of
the narration, the group of the actors in the considered framework of the
story. The other groups, in which every member assumes one of the four above-
mentioned principal roles, represent the observers. The task of the latter is
that of observing the actors who interact with each other focusing, in
particular, on the behaviour of the actor who assumes their same role.

The investigation has been accomplished by analysing the group chat into which
the studends who act interacted with each other and with the teacher who helps
the actors in their assignement. Also the chat used by the observers have been
examined by using the Matlab sotware published in [3] and described above.
Related to the complex network theory, the chat examination led to the
construction of a matrix whose rows represent all the 27 participants to the
project while the columns report the principal and secondary variables
consisting of the roles and the interactions divided into primary and minor
too.

The adjacency matrix considered in the esperimentation, of size $27\times 31$,
represent abundance data and it is reported below. In particular, the matrix
is such that the rows and columns are costructed as follows. The rows are 27
and contain all the partecipants to the trial: the first four represent the
students who act in the considered episode. The rows from the 5th to the
second-last are associated to the other students who assume the role of
observers, while the last one is related to the teacher who mediates the
actors participation in the chat. The columns are instead 31 and they contain
the roles on each group into which the students are divided and the variables
considered in the pilot project. More in detail, the columns from the 1st to
the 4th represent the roles assumed by the actors, the fifth represents the
role taken on by the teacher. The columns from the 6th to the 25th represent
the roles assumed by the students on each observers group.

The last columns represent the variables which take into account the
interactions between the student and with the teacher. Precisely, column 26
report the interactions between the students related to the mathematical
problem, column 27 is related to the social interactions between the actors.
The 28th column reports the interaction of mathematical nature between the
actors and the teacher; column 29 takes into account the social interactions
between the students and the teacher. The 30th column reports the mathematical
exchanges between students and teacher and in the last one the element
$a_{i,31}$ represents the social interactions between the teacher and the
$i$-th student.

$\tiny{A=\left(\begin{array}[]{ccccccccccccccccccccccccccccccc}1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&18&8&7&6&5&2\\\
0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&16&10&3&2&1&2\\\
0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&16&6&5&2&3&0\\\
0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&11&7&1&0&1&0\\\
0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0\\\
0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&14&6\end{array}\right)}$

Let us consider the first student, by examining the first row of $A$, it can
be observed that the student plays the role of the “PESTE” corresponding to
the first column (the element $a_{1,1}=1$ indicates that student 1 has assumed
the first role which is that of the PESTE Clara). The student interacts with
classmates 18 times (main interactions / on the mathematical problem) being
the element $a_{1,26}=18$; element $a_{1,27}=8$ indicates that actor 1 carries
out 8 interventions of social interaction with companions. The element
$a_{1,28}=7$ indicates that the PESTE student interacted 7 times with the
teacher on the mathematical problem and the social / secondary interactions
with the mediatior were instead 6 (element $a_{1,29}=$ 6). The element
$a_{1,30}=5$ indicates that the teacher has interacted 5 times directly with
the student on the mathematical problem, while the last column shows that the
teahcre’s social interactions with the student were 2.

By considering the data matrix $A$, it can be observed that the group of the
actors given by the first 4 students interact only with the teacher. The other
students, who are the observers in this phase of the experimentation, do not
interact neither with each other nor with the first group and the teacher.
This fact leads to the observation that, in terms of graph theory, the indices
corresponding to the actors and the teacher may give a connected component of
the underlying graph. Hence, by applying the spectral algorithm, the indices
identitying the actors together and he teacher should correspond to the
childrend of a Q node.

The other students, on the other hand, may be considered as isolated nodes and
so their indices, according to how the spectral seriation algorithm works,
should identify the children leaves of a P node.

By using the data matrix, A, we constructed the similarity matrix associated
with our application. The observation that the group of the actors given by
the first 4 students interact only with the teacher while the other students,
who are the observers in this phase of the experimentation, interact neither
with each other nor with the first group and the teacher, leads to notice
that, in terms of graph theory, the indices corresponding to the actors and
the teacher may give a connected component of the underlying graph., i.e., set
of vertices that are linked to each other and are connected to no additional
vertices in the rest of the graph. Hence, by applying the spectral algorithm,
the indices identifying the actors together with the teacher should correspond
to the children of a Q node. The other students, on the other hand, may be
considered as isolated nodes and so their indices, according to how the
spectral seriation algorithm works, should identify the children leaves of a P
node. As mentioned above, the spectral algorithm is applied to the similarity
matrix associated with the matrix A which describes the data and it constructs
the PQ tree, displayed in Figure 2 which encodes all the admissible
permutations of the nodes, i.e. the participants.

Figure 2: PQ-tree corresponding to the data matrix $A$.

One of the admissible permutations, whose number is constrained by the
particular structure of the tree,is

p = [4 3 1 2 27 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26]

and it represents the displayed frontier of the tree represented in Figure 1
that is one of all the possible frontiers. By observing the structure of the
tree, it can be noted that the leaf nodes labelled as the students who acted
and the teacher, are isolated from the others which represent the observers.
Specifically, the nodes which represent the participants are children of a Q
node that is characterized by the fact that it represents both the right and
the left orderings of its leaves labelled as the node in the graph. The P
node, child of the Q node, represents the equivalence class of all the
permutations of its leaves. Hence, all the constrained permutations of the
nodes labelled as the participants in this phase, i.e., the students who acted
and the teacher, are the following

4 | 3 | 1 | 2 | 27
---|---|---|---|---
27 | 2 | 1 | 3 | 4
4 | 3 | 2 | 1 | 27
27 | 1 | 2 | 3 | 4

As aforementioned, the seriation problem consists in finding the best
enumeration order of a set of units so that elements with higher similarity
are closer to each other in the resulting sequence. Under thisperspective, the
obtained permutations allow us to make some considerations regarding the
similarity of the assigned roles based on the messages written in the chat. In
fact, it can be observed that, in all the admissible obtained permutations for
the nodes that represent the active players in this episode, nodes 1 and 2
(the Pest and the Blogger) are always close to each other and so are nodes 3
and 4 that represent the Boss and the Promoter respectively. The teacher,
labelled by node 27, is closely related to the Pest and the Blogger as in all
the resulting sequences these three nodes are placed together. From the point
of view of a didactic interpretation, the structure of the graph allows an
analysis of the behaviors of the student who actively participated with
respect to the role assigned to each one of them and with respect to the
communication with the teacher. The expected behavior of the Promoter, whose
task is to animate the interaction between peers and any direct interaction
with the uncle, is confirmed. The student who assumes the role of the Pest,
aimed at asking everyone questions, interacts mainly with the Blogger on the
mathematical question to be solved. We recall that this first episode is
related to the exploration of the problem from a mathematical point of view
but also to the trial stage of the roles’ tasks. This may explain the
particular structure of the graph related to the players which highlights a
similarity in the behavior of the roles of the Pest and the Blogger with
respect to the other characters. In this first phase, the teacher deliberately
plays an interlocutory role with respect to both the management of the group
and the resolution of the mathematical task. In the following, we analyse the
data coming from the chat of the 5 groups of students who play as observers in
the same analysed episode. Each of these groups observed and communicate
within itself simultaneously with the group of the actors who in the first
episode had to “explor” the problem enclosed in the story. Note that students
of each group interacted among themselfs and in this phase of the activity did
not interact with the other observers nor with the teacher. We considered the
chat written simultaneously to the actors’ one in order to study the behaviour
of the students who observe the ones who play by comparing the PQ-trees of
each observers’ group.

The matrix coming from the analisys of the chat is constructed as mentioned
above and has the following form:

$A=\left(\begin{array}[]{cccccccccccccccccccccccc}1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&16&0&2&0\\\
0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&5&1&0&0\\\
0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&14&3&0&1\\\
0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&7&2&2&1\\\
0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&10&0&0&0\\\
0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&9&1&2&0\\\
0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&9&0&2&0\\\
0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&8&0&0&0\\\
0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0\\\
0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&12&2&1&0\\\
0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&9&1&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&9&0&1&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&3&10&8&8\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&2&12&5&3\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&7&17&10&3\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&3&4&1&4\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&12&9&3\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&1&8&9&4\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&2&10&15&2\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&1&14&11&5\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\end{array}\right);$

In particular, the rows represent the students who are observers. All the 26
students are divided into groups $g_{i}$; the members of $g_{1}$ are the
actors while the observers are in the other groups. Groups $g_{i}$ for
$i=2,3,4$ consist of four students, in group $g_{5}$ there were six students
therefore 2 students play the PESTE role and two perform the BOSS. The last
group was composed of six students, two of them perform the PESTE and two had
the PROMOTER’s role. Given the composition of the observers’ groups, the rows
of the matrix are 25. There are 24 columns; for each of the 5 groups of
observers there are 4 columns relating to the roles of Pest, Blogger, Boss and
Promoter. Therefore the first 20 columns represent the roles and, as in the
case of the actors’ chat, the remaining columns represent the different types
of interactions minutes. In particular, column 21 contains the main
interventions, i.e., those relating to the observed role corresponding to that
assumed by the considered observer pupil. In column 22 the secondary / social
interventions are contained; elements $a_{i,23}$ are general interventions on
the behavior of the group of actors or on a role different from that assumed
by the $i$-th observer. Finally, the last column contains interventions
relating to the mathematical problem or to solution proposed by the students
in the chat group that observers discuss.

We report and analyze the peer interactions of the observers in each group, in
order to construct the PQtree coming from processing the similarity matrix
costructed from the binary data matrix. Note that the latter does not take
into account the frequencies but is obtained by replacing each non-zero entry
of $A$ by 1.

For the 5 observers’ groups the output of the algorithm is given by a tree
with only a Q node, two trees rooted by a P node and the trees of groups 4 and
6 have a pattern similar to the actors’ one with a mized P node and Q node
structure.

Riportiamo alcuni estratti e analizziamo le interazioni delle chat di ciascun
gruppo, al fine di identificare se alla analogia di struttura dell’albero
corrisponda una analogia di comportamento tra gruppi di osservatori o con il
gruppo degli attori.

In the following we report some excerpts and then analyze the interactions of
each group, in order to identify whether the analogy of the structure of the
tree corresponds to an analogy of behavior between groups of observers or with
the group of actors.

By analyzing the observers’ similarity matrix the obtained permutations is
given by the sequence of nodes

$\footnotesize{\texttt{p = [5 8 9 1 7 12 2 11 6 10 3 4 13 15 16 18 21 23 24 19
20 14 17 22 25]}}.$

In the following, $B_{k}$ indicates the data matrix relating to the group of
observers $g_{k}$ with $k=2,\ldots,6$.

Group $g_{2}$.

The data matrix related to observers’ group $g_{2}$ and the similarity matrix
of the corresponding ${0,1}$ data matrix are respectively

$B_{2}=\left(\begin{array}[]{cccccccc}1&0&0&0&16&0&2&0\\\ 0&1&0&0&5&1&0&0\\\
0&0&1&0&14&3&0&1\\\ 0&0&0&1&7&2&2&1\end{array}\right),\quad
S_{2}\left(\begin{array}[]{cccc}3&1&1&2\\\ 1&3&2&2\\\ 1&2&4&3\\\
2&2&3&5\end{array}\right)$

and one of the admissible permutations encoded in the PQtree obtained through
the seriation algorithm is

     p2 = [2 3 4 1]

that is the frontier of the PQtree, depicted in Figure 3, with a Q node as a
root.

Figure 3: PQ-tree corresponding to the data of group $g_{2}$.

We observed that in this group only the Boss and the Promoter made
considerations on the problem, like the following

Promoter 12:50: according to the Boss, the Promoter did not write the correct
formula;

Boss 12:51: the Boss suggests another formula

The contingency analysis shows that in this group there were few social
interactions and each member commented on the same interpreted role. In
particular the Pest posted many comments related to the actor Pest. Group
$g_{2}$ is the only group that has a compact and uniform behavior with respect
to the types of interactions we are analyzing. All the other observers’ groups
are characterized by behaviors more or less distinct within the roles or type
of interventions.

Group $g_{4}$.

The matrix constructed from the analysis of the data in the chat of group
$g_{4}$ and the similarity matrix constructed from its binary version are
respectively

$B_{4}=\left(\begin{array}[]{cccccccc}1&0&0&0&1&0&0&0\\\ 0&1&0&0&12&2&1&0\\\
0&0&1&0&9&1&0&0\\\ 0&0&0&1&9&0&1&0\end{array}\right),\quad
S_{4}\left(\begin{array}[]{cccc}2&1&1&1\\\ 1&4&2&2\\\ 1&2&3&1\\\
1&2&1&3\end{array}\right)$

and one of the admissible permutations encoded in the obtained tree is the
sequence

    p4 = [1 3 2 4].

that is the frontier of the PQtree in Figure 4.

Figure 4: PQ-tree corrispondente alla matrice dei dati $B_{4}$.

This PQtree has a P node as root and has two branching that identify different
behaviours between node 1 (the Pest) and the other members. In this group the
Pest has a marginal involvement at the end of this episode concerning a
consideration of how the Pest-actor is playing

Pest 13:10: the Pest is performing very well the role.

Group $g_{6}$.

The data matrix coming form the chat of group $g_{6}$ and the related
similarity matrix of the binary version are respectively

$B_{6}=\left(\begin{array}[]{cccccccc}1&0&0&0&1&11&8&3\\\ 1&0&0&0&0&1&1&0\\\
0&1&0&0&1&8&9&4\\\ 0&0&1&0&2&10&15&2\\\
0&0&0&1&1&14&11&5\end{array}\right),\quad
S_{6}=\left(\begin{array}[]{ccccc}5&3&4&4&4\\\ 3&3&2&2&2\\\ 4&2&5&4&4\\\
4&2&4&5&4\\\ 4&2&4&4&5\end{array}\right).$

The PQ-tree obtained after applying the seriation algorithm to the simularity
matrix constructed from the binary version of $B_{6}$ is depicted in Figure 5.

One of the admissible permutations, that is the frontier of the PQtree in
Figure 5, is the sequence

    p6 = [2 1 3 4 5].

Figure 5: PQ-tree related to the data matrix$B_{6}$.

Group $g_{5}$.

The data matrix related to the chat of group $g_{5}$ and the similarity matrix
are

$B_{5}=\left(\begin{array}[]{cccccccc}1&0&0&0&1&0&0&0\\\ 0&1&0&0&2&12&5&3\\\
0&0&1&0&7&17&10&3\\\ 0&0&0&1&3&4&1&4\\\
0&0&0&0&0&0&0&0\end{array}\right),\quad
S_{5}=\left(\begin{array}[]{ccccc}2&1&1&1&0\\\ 1&5&4&4&0\\\ 1&4&5&4&0\\\
1&4&4&5&0\\\ 0&0&0&0&0\end{array}\right)$

and one of the admissible permutations, that is the frontier of the tree
depicted in Figure 6 is the sequence

    p5 = [1 2 3 4 5].

Figure 6: PQ-tree related to the analysis of the matrix $B_{5}$.

The PQtree in Figure 6 represents in a compact way the following 24
permutations

5 | 4 | 3 | 2 | 1
---|---|---|---|---
5 | 4 | 2 | 3 | 1
5 | 3 | 4 | 2 | 1
5 | 3 | 2 | 4 | 1
5 | 2 | 4 | 3 | 1
5 | 2 | 3 | 4 | 1
5 | 1 | 4 | 3 | 2
5 | 1 | 4 | 2 | 3
5 | 1 | 3 | 4 | 2
5 | 1 | 3 | 2 | 4
5 | 1 | 2 | 4 | 3
5 | 1 | 2 | 3 | 4
4 | 3 | 2 | 1 | 5
4 | 2 | 3 | 1 | 5
3 | 4 | 2 | 1 | 5
3 | 2 | 4 | 1 | 5
2 | 4 | 3 | 1 | 5
2 | 3 | 4 | 1 | 5
1 | 4 | 3 | 2 | 5
1 | 4 | 2 | 3 | 5
1 | 3 | 4 | 2 | 5
1 | 3 | 2 | 4 | 5
1 | 2 | 4 | 3 | 5
1 | 2 | 3 | 4 | 5

Group $g_{3}$.

The third observers’ group is characterized by similar behavior of all members
who did not make comments on the problem. The data matrix coming form the chat
of the observers in group $g_{3}$ and the similarity matrix constructed form
the binary data matrix are respectively

$B_{3}=\left(\begin{array}[]{cccccccc}1&0&0&0&10&0&0&0\\\ 0&1&0&0&9&1&2&0\\\
0&0&1&0&9&0&2&0\\\ 0&0&0&1&8&0&0&0\end{array}\right),\quad
S_{3}=\left(\begin{array}[]{cccc}2&1&1&1\\\ 1&4&2&1\\\ 1&2&3&1\\\
1&1&1&2\end{array}\right)$

one of the possible permutation is the frontier of the PQtree depicted in
Figure 7, that is the sequence

    p3 = [1 2 3 4].

Figure 7: PQ-tree related to the analysis of group $g_{3}$.

The particular structure of the tree encode the following 12 admissible
permutations

4 | 3 | 1 | 2
---|---|---|---
4 | 2 | 3 | 1
4 | 1 | 3 | 2
4 | 1 | 2 | 3
3 | 2 | 4 | 1
2 | 3 | 4 | 1
3 | 2 | 1 | 4
2 | 3 | 1 | 4
1 | 4 | 3 | 2
1 | 4 | 2 | 3
1 | 3 | 2 | 4
1 | 2 | 3 | 4

Reading the chat we observed that the Pest (node 1) and the Promoter (node 4)
made considerations only on the role of their correspondent-actors and in fact
in the tree in Figure 7 are separated, as it should have been, from the Boss
and the Blogger who instead intervened on the actors who play other roles.
This can be observed in the following posts reported here as examples:

Promoter $g_{3}$ 12:30: the Promoter takes the floor allowing to…

Promoter $g_{3}$ 12:31: the Promoter gives proof of what he/she is saying

Peste $g_{3}$ 12:31: the Pest is participating a lot asking many questions

Blogger $g_{3}$ 12:32: the Blogger is participating a lot…

Boss $g_{3}$ 12:33: the Boss is coordinating the group very well…

Reading the observers’ interventions, it was noted that groups $g_{5}$ and
$g_{6}$ are more oriented to comment in general on the behavior of the actors
and not on the specific role that is the same one played by them. Moreover,
rather than analyzing the behavior of the actors who fulfill their
corresponding role, the observers of these two groups interact by making
interventions also on the mathematical problem.

##  5 Conclusions

In this manuscript, we presented the preliminary results of an experimental
work, on digital storytelling in Mathematics, aimed at promoting critical
mathematical thinking among students. The analyzed activity is the first
episode of a story that develops in 5 episodes and involves the participation
of students from a second-grade class who take on both the role of active
protagonists and that of observers of the actors during the problem solving
activity. In particular, the communication between the participants who
interacted on the chat of the Moodle e-learning platform was examined from a
didactic and numerical modeling point of view. The case study analyzed above,
allows us to validate the spectral algorithm and the accompanying Matlab
toolbox originally implemented for solving the seriation problem in
archaeology where the latter appeared first. In particular, the outcomes
obtained for the active members of the study and the comments at the end of
Section 3, show that the spectral algorithm gives a reasonable result in terms
of admissible permutations for the indices of the nodes depicting the assigned
roles. Although the size of the examined sample is not very large, the
structure of the algorithm allows us to confirm that also for wider
dimensions, the group of the active participants should be separated from the
observers as it identifies a connected component in the underneath graph.
Moreover, from a numerical point of view, the size of the similarity matrix
does not constitute a problem since the spectral algorithm is based on the
computation of an eigenvector and for thispurpose the toolbox includes the
possibility to choose between a small-scale and a large-scale implementation
and, for improving the performance in case of a large-scale problem, a
parallel version of the method is also provided. In this work, we observed how
the complex networks analysis in a DIST-M setting may be worthy both as a tool
for validating the mentioned algorithm and as a potential instrument for
allowing the identification of the behaviors, whether didactic or
interpersonal, one wants to examine. Further development of this research may
include the analogous investigation of the episodes subsequent to the first
analyzed in this manuscript, in order to put emphasis on potential
dissimilarities in the behavior of the students when they assume a different
role.

## References

  * [1] J. E. Atkins, E. Boman and B. Hendrickson. A spectral algorithm for seriation and the consecutive ones problem, SIAM Journal on Computing, 28(1), pp. 297–310, 1998.
  * [2] A. Pesci, Insegnare e apprendere cooperando: esperienze e prospettive, L’insegnamento della matematica e delle scienze integrate, 27(6), pp. 638–670, 2004.
  * [3] A. Concas, C. Fenu, and G. Rodriguez. PQser: a Matlab package for spectral seriation. Numer. Algorithms, 80(3):879-902, 2019.
  * [4] M. Polo, U. Dello Iacono, G. Fiorentino and A. Pierri. A social network analysis approach to a digital interactive storytelling in mathematics. Journal of e-Learning and Knowledge Society, 15(3): 239-250, 2019.
  * [5] A. Concas. Numerical Linear Algebra applications in Archaeology: the seriation and the photometric stereo problems. PhD Thesis. https://iris.unica.it/retrieve/handle/11584/285374/386189/tesi
  * [6] G. Albano, A. Pierri and M. Polo. Engagement in mathematics through digital interactive storytelling. Proceeding of Eleventh Congress of the European Society for Research in Mathematics Education (CERME11), pp. 1501-1508, 2019, https://hal.archives-ouvertes.fr/hal-02410195.
  * [7] E. Wenger. Communities of practice: Learning, meaning, and identity. Cambridge University Press, 1999.
  * [8] G. Albano, A. Pierri and M. Polo. Immersing in a digital storytelling in mathematocs : the student’s reflective action. Proceeding of Contemporary Mathematics Education, Critical thinking in mathematics: Perspectives and challenges, CME 2020.
  * [9] Y. Chevallard. Un concept en émergence: la dialectique des médias et des milieux, Actes du séminaire national de didactique des mathématiques, pp. 344–366, 2007.
  * [10] Y. Chevallard and C. Ladage. E-learning as a touchstone for didactic theory, and conversely. Journal of e-Learning and Knowledge Society, 4(2), pp. 163–171, 2008.
  * [11] P. Piana Agostinetti and M. Sommacal, Matteo, Il problema della seriazione in archeologia, Istituto italiano di preistoria e protostoria, pp.29–69, 2005.
  * [12] M. Dougia and P. Taylor. Moodle: Using learning communities to create an open source course management system. EdMedia+ Innovate Learning, pp. 171–178, 2003.
  * [13] K. S. Booth and G. S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Journal of computer and system sciences, 13(3), pp. 335–379, 1976.
  * [14] Y. Engeström. Expanding the scope of science education: an activity-theoretical perspective. Cognitive and affective aspects in science education research (Springer), pp. 357–370, 2017.
  * [15] , Y. Engeström and A. Sannino. Studies of expansive learning: Foundations, findings and future challenges. Educational research review (Elsevier) , 5(1), pp. 1–24, 2010.
  * [16] L. S. Vygotsky. Thought and language, MIT press, 2012.
  * [17] L. S. Vygotsky, Mind in society: The development of higher psychological processes,Harvard university press, 1980.
  * [18] D. Lazarou, R. Sutherland and S. Erduran. Argumentation in science education as a systemic activity: An activity-theoretical perspective. International Journal of Educational Research, Elsevier, 79, pp. 150–166, 2016.
  * [19] A. Sfard. There is more to discourse than meets the ears: Looking at thinking as communicating to learn more about mathematical learning. Educational studies in mathematics (Springer), 46, pp. 13–57, 2001.
  * [20] M. J. Brusco and D. Steinley. Clustering, seriation, and subset extraction of confusion data. Psychol. Methods, 11(3), pp. 271–286, 2006.
  * [21] F. R. Hodson, D. G. Kendall and P. Tautu. Mathematics in the Archaeological and Historical Sciences, Edimburg University Press, 1971.
  * [22] S. Fantinelli and V. Russo. Community of practice online, the importance of technology for learning: an application of Social Network Analysis, Journal of e-Learning and Knowledge Society, 14(3), 2018.
  * [23] W. M. F. Petrie. Sequences in Prehistoric Remains, J. R. Anthropol. Inst. 29, pp. 295–301, 1899.
  * [24] M. B. Eisen, P. T. Spellman, P. O. Brown and D. Botstein. Cluster analysis and display of genome-wide expression patterns, P. Natl. Acad. Sci. U.S.A., 95, pp. 14863–14868, 1998.
  * [25] B. G. Mirkin and S. N. Rodin. Graphs and Genes, Springer-Verlag, 11, 1984.
  * [26] A. King, Scripting collaborative learning processes: A cognitive perspective, Scripting computer-supported collaborative learning, Springer, pp. 13–37, 2007.
  * [27] L. Kobbe, A. Weinberger, P. Dillenbourg, A. Harrer, R. Hä mäläinen and F. Fisher, Specifying computer-supported collaboration scripts, International Journal of Computer-Supported Collaborative Learning, Springer, 2(2), pp. 211–224, 2007.
  * [28] A. Pesci. Cooperative learning and peer tutoring to promote students’ mathematics education, 2009.
  * [29] G. Albano and U. Dello Iacono. A scaffolding toolkit to foster argumentation and proofs in mathematics: some case studies, International Journal of Educational Technology in Higher Education, Springer, 16(1), pp. 1–12, 2019.
  * [30] L. Radford. The seen, the spoken and the written: A semiotic approach to the problem of objectification of mathematical knowledge, For the learning of mathematics, JSTOR, 22(2), pp. 14–23, 2002.
  * [31] Y. Engeström and A. Sannino. Studies of expansive learning: Foundations, findings and future challenges, Educational research review, Elsevier, 5(1), pp. 1–24, 2010.
  * [32] D. Sulisworo and S.P. Agustin and E. Sudarmiyati, Cooperative-blended learning using Moodle as an open source learning platform, International Journal of Technology Enhanced Learning, IEL, 8(2), pp. 187–198, 2016.