# Left-Right Oscillate Algorithm for Community Detection Used in E-Learning System

Jan Martinovič, Pavla Dráždilová, Kateřina Slaninová, Tomáš Kocyan, Václav Snášel

► To cite this version:

Jan Martinovič, Pavla Dráždilová, Kateřina Slaninová, Tomáš Kocyan, Václav Snášel. Left-Right Oscillate Algorithm for Community Detection Used in E-Learning System. 11th International Conference on Computer Information Systems and Industrial Management (CISIM), Sep 2012, Venice, Italy. pp.278-289, 10.1007/978-3-642-33260-9_24. hal-01551718

HAL Id: hal-01551718

https://inria.hal.science/hal-01551718

Submitted on 30 Jun 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Left-Right Oscillate Algorithm for Community Detection used in E-learning system

Jan Martinovič², Pavla Dráždilová¹, Kateřina Slaninová¹, Tomáš Kocyan², and Václav Snášel²

¹ VŠB - Technical University of Ostrava, Faculty of Electrical Engineering and Computer Science, 17. listopadu 15/2172, 708 33 Ostrava, Czech Republic (katerina.slaninova,pavla.drazdilova)@vsb.cz

² VŠB - Technical University of Ostrava, IT4Innovations, 17. listopadu 15/2172, 708 33 Ostrava, Czech Republic (jan.martinovic,tomas.kocyan,vaclav.snasel)@vsb.cz

**Abstract.** Learning management systems are widely used as a support of distance learning. Recently, these systems successfully help in present education as well. Learning management systems store large amount of data based on the history of users' interactions with the system. Obtained information is commonly used for further course optimization, finding e-tutors in collaboration learning, analysis of students' behavior, or for other purposes. The partial goal of the paper is an analysis of students' behavior in a learning management system. Students' behavior is defined using selected methods from sequential and process mining with the focus to the reduction of large amount of extracted sequences. The main goal of the paper is description of our Left-Right Oscillate algorithm for community detection. The usage of this algorithm is presented on the extracted sequences from the learning management system. The core of this work is based on spectral ordering. Spectral ordering is the first part of an algorithm used to seek out communities within selected, evaluated networks. More precise designations for communities are then monitored using modularity.

## 1 Introduction

E-learning is a method of education which utilizes a wide spectrum of technologies, mainly internet or computer-based, in the learning process. It is naturally related to distance learning, but nowadays is commonly used to support face-to-face learning as well. Learning management systems (LMS) provide effective maintenance of particular courses and facilitate communication within the student community and between educators and students [9]. Such systems usually support the distribution of study materials to students, content building of courses, preparation of quizzes and assignments, discussions, or distance management of classes. In addition, these systems provide a number of collaborative learning tools such as forums, chats, news, file storage etc.

Regardless of LMS benefits, huge amount of recorded data in large collections makes often too difficult to manage them and to extract useful information from them.
To overcome this problem, some LMS offer basic reporting tools. However, in such large amount of information the outputs become quite obscure and unclear. In addition, they do not provide specific information of student activities while evaluating the structure and content of the courses and its effectiveness for the learning process [26]. The most effective solution to this problem is to use data mining techniques [1].

The main goal of the paper is the description of our Left-Right Oscillate algorithm for community detection. The usage of this algorithm is presented on the extracted sequences from a learning management system. The core of this work is based on spectral ordering. Spectral ordering is the first part of an algorithm used to seek out communities within selected, evaluated networks. More precise designations for communities are then monitored using modularity.

The discovery and analysis of community structure in networks is a topic of considerable recent interest in sociology, physics, biology and other fields. Networks are very useful as a foundation for the mathematical representation of a variety of complex systems such as biological and social systems, the Internet, the world wide web, and many others [8, 17]. A common feature of many networks is community structure, the tendency for vertices to divide into groups, with dense connections within groups and only sparser connections between them [12, 18].

## 2 Analysis of Students' Behavior

Several authors published contributions with relation to mining data from e-learning systems to extract knowledge that describe students' behavior. Among others we can mention for example [14], where authors investigated learning process of students by the analysis of web log files. A 'learnograms' were used to visualize students' behavior in this publication. Chen et al. [3] used fuzzy clustering to analyze e-learning behavior of students. El-Hales [11] used association rule mining, classification using decision trees, E-M clustering and outlier detection to describe students' behavior. Yang et al. [25] presented a framework for visualization of learning historical data, learning patterns and learning status of students using association rules mining. The agent technology and statistical analysis methods were applied on student e-learning behavior to evaluate findings within the context of behavior theory and behavioral science in [2].

Our subject of interest in this paper is student behavior in LMS, which is recorded in form of events and stored in the logs. Thus, we can define the student behavior with the terms of process mining which are used commonly in business sphere. Aalst et al. [23, 22] defines event log as follows:

Let $A$ be a set of activities (also referred as tasks) and $U$ as set of performers (resources, persons). $E = A \times U$ is the set of (possible) events (combinations of an activity and performer). For a given set $A$, $A^*$ is the set of all finite sequences over $A$. A finite sequence over $A$ of length $n$ is mapping $\sigma = \langle a_1, a_2, ..., a_n \rangle$, where $a_i = \sigma(i)$ for $1 \le i \le n$. $C = E^*$ is the set of possible event sequences. A simple event log is a multiset of traces over $A$.

The behavioral patterns are discovered using similarity of extracted sequences of activities performed in the system.
A sequence is an ordered list of elements, denoted $<e_1, e_2, ..., e_l>$. Given two sequences $\alpha = \langle a_1, a_2, ..., a_n \rangle$ and $\beta = \langle b_1, b_2, ..., b_m \rangle$. $\alpha$ is called a subsequence of $\beta$, denoted as $\alpha \subseteq \beta$, if there exist integers $1 \le j_1 < j_2 < ... < j_n \le m$ such that $a_1 = b_{j_1}, a_2 = b_{j_2}, ..., a_n = b_{j_n}$. $\beta$ is then a super sequence of $\alpha$.

For finding the behavioral patterns, we need to use the methods for the sequence comparison. There are generally known several methods for the comparison of two or more categorical sequences. On the basis of our previous work [21] we have selected the algorithm, which deals with the different lengths of sequences and with the possible error or distortion inside the sequence.

*Time-warped longest common subsequence (T-WLCS)* [13] is the method, which combines the advantages of two methods from pattern mining - The longest common subsequence (LCSS) [15] and Dynamic time warping (DTW) [16]. LCSS allows us to find the longest common subsequence of two compared sequences. DTW is used for finding the optimal visualization of elements in two sequences to match them as much as possible. Then, selected T-WLCS method is able to compare sequences of various lengths, it takes into consideration the order of elements in the sequences, and it is immune to minor distortions inside of one of the compared sequences. Moreover, the method emphasizes recurrence of the elements in one of the compared sequences.

To obtain behavioral patterns of similar sequences in LMS, we have used our proposed new Left-Right Oscillate algorithm for community detection. The algorithm is based on spectral ordering (see Section 3).

# 3 Spectral Clustering and Ordering

Spectral clustering has become one of the most popular modern clustering algorithms in recent years. It is one of the graph theoretical clustering techniques and is simple to implement, can be solved efficiently by standard linear algebra methods, and very often outperforms traditional clustering algorithms such as the k-means or single linkage (hierarchical clustering). A comprehensive introduction to the mathematics involved in spectral graph theory is the textbook of Chung [5]. Spectral clustering algorithm uses eigenvalues and eigenvectors of Laplacian of similarity matrix derived from the data set to find the clusters. A practical implementation of the clustering algorithm is presented in [4]. Recursive spectral clustering algorithm is used in [6]. There Dasgupta et al. analyzed the second eigenvector technique of spectral partitioning on the planted partition random graph model, by constructing a recursive algorithm. A spectral clustering approach to finding communities in graphs was applied in [24].

Ding and He showed in [7] that a linear ordering based on a distance sensitive objective has a continuous solution which is the eigenvector of the Laplacian. Their solution demonstrate close relationship between clustering and ordering. They proposed direct K-way cluster assignment method which transforms the problem to linearization of the clustering assignment problem. The linearized assignment algorithm depends crucially on an algorithm for ordering objects based on pairwise similarity metric. The ordering is such that adjacent objects are similar while objects far away along the ordering are dissimilar. They showed that for such an ordering objective function the inverse index
permutation has a continuous (relaxed) solution which is the eigenvector of the Laplacian of the similarity matrix.

## 3.1 Modularity - Quality of Detected Communities

To quantify the quality of the subdivisions we can use modularity [20], defined as the fraction of links between the nodes in the same community minus their expected value in a corresponding random graph [20]. Networks with the high modularity have dense connections between the nodes within community, but sparse connections between the nodes in the different communities. Modularity is often used in optimization methods for detecting community structure in the networks [19]. The value of the modularity lies in the range $(-0.5, 1]$. It is positive, if the number of edges within groups exceeds the number expected on the basis of chance.

For a weighted graph G we have a weight function $w: E \to R$. It is for example function of the similarity between the nodes $v_i$ and $v_j$. The weighted adjacency matrix of the graph is the matrix $W = (w_{ij})$ $i, j = 1, \dots, n$. Than the degree of a vertex $v_i \in V$ in weighted graph is defined as

$$d_i = \sum_{j=1}^{n} w_{ij}.$$

The weighted degree matrix D is defined as the diagonal matrix with the weighted degrees $d_1, \dots, d_n$ on the diagonal.

In terms of the edge weights, modularity $Q(C_1, \dots, C_k)$ is defined over a specific clustering into $k$ known clusters $C_1, \dots, C_k$ as

$$Q(C_1, \dots, C_k) = \sum_{i=1}^{k} (e_{ii} - \sum_{j=1, i \neq j}^{k} e_{ij})$$

where $e_{ij} = \sum_{(u,v) \in E, u \in C_i, v \in C_j} w(u, v)$ with each edge $(u, v) \in E$ included at most once in the computation.

# 4 Left-Right Oscillate Algorithm for Community Detection

Upon completing our study of various modifications of algorithms for spectral clustering, we designed our own algorithm for detecting communities within complex networks. This algorithm utilizes spectral ordering where similar vertices are closer to indexes and less similar vertices are further from indexes. When determining the ordering, it is necessary to calculate the eigenvector of the second smallest eigenvalue of the matrix $L = D - W$. Since we have designed our algorithm for large amounts of data in a complex network, we used Lanczos method to calculate the Fiedler vector. Once the Fiedler vector was calculated, we detected appropriate gaps that divide the vertices of a graph into communities. As observed in the experiment, this type of separation into gaps leads to several badly-assigned subgraphs. This is due to the fact that the Fiedler vector is only linear ordered, as is revealed in our data collection. The Left-Right algorithm (see Algorithm 3.1) we have designed for incorporating small subgraphs into larger communities, gradually increases modularity in a given calculation.
**Algorithm 1 Left-Right Algorithm for Community Detection**

Input: similarity matrix $W = w_{i,j}$ for $i = 1, ..., n$ and $S_c$ size of smallest communities.

Output: communities $C_k$, modularity of detected communities

1. Create Laplacian $L = D - W$ using a matrix of similarity $W$ of a connected graph $G = (V, E, W)$.

2. Calculate the Fiedler vector (the second eigenvector of Laplacian).

3. Reorder vertices according to Fiedler vector.

4. Calculate the sums of antidiagonals $Asum_i = \sum_{j} w_{i-j,i+j}$ and $Asum_{(i+1/2)} = \sum_{j} w_{i-j,i+j+1}$ for all $i = 1, ..., n$ and determine $sum_i = Asum(i - 1/2)/4 + Asum(i)/2 + Asum(i + 1/2)/4$.

5. Approximate the discrete function $sum_i$ by its spline and determine its first and second derivation. Then find all local minimums and maximums.

6. Assign maximum gaps that lie between two local maximums. Divide the set of vertices according to its gaps. Obtain subsets $SS_k \subset V$, where $k = 1, ..., K$ is the amount of subsets.

7. Detect a community using the Left-Right Oscillate assigning algorithm (see Algorithm 2).

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Similarity Matrix and Permuted Similarity Matrix (Natural Number of Communities is 7)</figcaption></figure>

Spectral ordering minimizes the sum of weighted edges multiplied to the power of the difference in index nodes with the edge incidence. The calculation used for this equation is the given eigenvector of the second smallest eigenvalue (Fiedler vector) matrix $L = D - W$. A visualized Fiedler vector and ordered matrix similarity (in agreement with the Fiedler vector) reveals the creation of several natural clusters which is assigned by our algorithm.

For finding the Fiedler vector of Laplacian above a large, sparse and symmetric matrix representative of the evaluated network, we used Lanczos method to partially solve the eigenvalue problem. To determine the dimension of Krylov subspaces (for a more precisely calculated Lanczos method), we used modularity for determining the quality of a detected community. In [7], there is an example of a symmetric Laplacian $L_{sym} = D^{-1/2}LD^{-1/2}$. Our experiment revealed, that this solution is only appropriate for some networks.
**Algorithm 2 Left-Right-Oscillate Assigned**

Input: subsets $SS_k \subset V$, where $k = 1, \dots, K$, $S_c$ size of smallest communities.

Output: communities $C_k$, modularity of detected partitioning.

1. Find connected components $C_j$ for subset $SS_1$, which are greater than the selected size $|C_j| \ge S_c$. These components create communities. We add the rest of the vertices $v_i \in SS_1 - \cup C_j$ to the next subset of vertices $SS_2$.

2. Find next connected components $C_j$ for every subset $SS_k$ ($k = 2, \dots, K$), which are greater than the selected size $|C_j| \ge S_c$. These components create communities. Attempt to assign other vertices to the previous community, which was established in the previous step. If the vertex has no edge leading to the previous community than we add the vertex to the next subset of vertices $SS_{k+1}$. Continue repeating this method 2 until we reach the end of ordered vertices.

3. Going through all subsets of vertices, connected components are assigned to $C_j$ for $j = 1, \dots, J-1$ and $C_J$ contain a set of connected components smaller than the selected size.

4. Employ the same approach going right-left without "oscillation". Begin with $C_{J-1} = C_{J-1} \cup C_J$.

The next step for the algorithm is to order indexes of vertices $v_i \in V$ for all $i = 1, \dots, n$ in compliance with ordering using Fiedler vector values. Because we want to find communities that are easily detected in a visual representation when ordered by a similarity matrix, we must determine where one community in a linear order ends and the next begins (find two nodes that belong to various communities). For this reason, we have calculated the value of antidiagonal sums above an ordered set of vertices that capture a cluster overlap in neighboring vertices $v_i$. We define cluster crossing as the sum of a small fraction of the pairwise similarities. This is aided by linear ordering data points. The goal is to find the nodes that lay in the areas with fewer edges. These vertices lie close to locales with minimum function that are attached by approximation of a cluster overlap discrete function $Sum_i$. We assigned this approximation using the spline function, allowing for easy calculations of both the first and second derivation, which are used to assign local extremes. Between the two local maximum extremes of this function, there lie two vertices. In this area, these vertices represent a maximum gap (the difference in their Fiedler vector value). This gap determines the border between two potential communities.

Using this method, we have found the natural amount of 'communities' above a given evaluated network. Since the precision with which the Fiedler vector is calculated is a determining factor, and since in some cases vertices are incorrectly assigned, the result is an irrelevant component. The benefit of using our algorithm lies within its ability to assign isolated nodes (or very small subgraphs with selected sizes) to the nearest, most suitable, connected component that creates the nucleus of a future community. Within our assignments, we gradually arrive at a set of vertices $V$ separated by gaps in individual subsets $V_k$. If the found set $V_k$ does not create a connected subgraph ($G_k = (V_k, E)$), we determine all connected components in this subgraph. The maximum connected subgraph then creates the nucleus of this community and all subgraphs smaller than the selected size are moved to the right. We then attempt to reassign the subgraph to the next subset of vertices $V_{k+1}$. Due to the linear nature of spectral or-
dering, it is presumable that subgraphs not yet assigned are reordered to the next sub-set of vertices. This means that we add the vertices of these subgraphs to the vertices of the next subset (that came into existence along gaps and creates a subgraph of the original graph with a set of vertices $V_{k+1}$). Then we test the connectivity of subgraph $G_{k+1}$, which was expanded by the nodes from the previous, unassigned subgraph. We go through the entire, spectrally ordered set of graph vertices employing this method. At the end of this process, we have created the most relevant of components within which we assign small subgraphs that are not yet assigned. Then, we repeat this approach in the opposite direction - going from right to left - and we try to add vertices for inspection in a subgraph. We may then assign the vertices to a connected subgraph with adjacency to a vertex of a given subgraph.

Once we assign a subset of vertices using gaps, and once we have detected connected components from left to right and vice versa, we always calculate the modularity for the obtained separation of graphs into subgraphs. Our results have revealed that our Left-right method increases modularity. The resulting connected subgraphs then create the structure of communities in the graph, which is demonstrated on well known data collection Zachary karate club in Table 1.

<table><caption>**Table 1.** Modularity Before and After Left-Right Algorithm for Zachary Karate Club</caption><thead><tr><th></th><th>Before Left-right</th><th>Commun.</th><th>After Left</th><th>Commun.</th><th>After Left-right</th><th>Commun.</th></tr></thead><tbody><tr><td>Laplacian</td><td>0.272</td><td>11</td><td>0.361</td><td>4</td><td>0.361</td><td>4</td></tr><tr><td>Normalized-cut</td><td>0.342</td><td>7</td><td>0.311</td><td>4</td><td>0.311</td><td>4</td></tr></tbody></table>

# 5 Sequence Extraction in LMS Moodle

In this section is presented the extraction of students' behavioral patterns performed in the e-learning educational process. The analyzed data collections were stored in the Learning Management System (LMS) Moodle logs used to support e-learning education at Silesian University, Czech Republic.

The logs consist of records of all events performed by Moodle users, such as communication in forums and chats, reading study materials or blogs, taking tests or quizzes etc. The users of this system are students, tutors, and administrators; the experiment was limited to the events performed only by students.

Let us define a set of students (users) $U$, set of courses $C$ and term Activity $a_k \in A$, where $A = P \times B$ is a combination of activity prefix $p_m \in P$ (e.g. course view, resource view, blog view, quiz attempt) and an action $b_n \in B$, which describes detailed information of an activity prefix (concrete downloaded or viewed material, concrete test etc.). Event $e_j \in E$ then represents the activity performed by certain student $u_i \in U$ in LMS. On the basis of this definition, we have created a set $S_i$ of sequences $s_{ij}$ for the user $u_i$, which represents the students' (users') paths (sessions) on the LMS website. Sequence $s_{ij}$ is defined as a sequence of activities, for example $s_{ij} = \langle a_{1j}, a_{2j}, \dots, a_{qj} \rangle$, which is j-th sequence of the user $u_i$.
The sequences were extracted likewise the user sessions on the web; the end of the sequences was identified by at least 30 minutes of inactivity, which is based on our previous experiments [10]. Similar conclusion was presented by Zorrilla et al. in [26].

Using this method, we have obtained a set of all sequences $S = \cup_{i} S_{i}$, which consisted of large amount of different sequences $s_{i}$ performed in LMS Moodle. We have selected the course Microeconomy A as an example for the demonstration of proposed method. In Table 2 is presented detailed information about the selected course.

<table><caption>**Table 2.** Description of Log File for Course Microeconomy A</caption><thead><tr><th>Records</th><th>Students</th><th>Prefixes</th><th>Actions</th><th>Sequences</th></tr></thead><tbody><tr><td>65 012</td><td>807</td><td>67</td><td>951</td><td>8 854</td></tr></tbody></table>

<table><caption>**Table 3.** Description of Sequence Graphs for T-WLCS Method</caption><thead><tr><th colspan="5">T-WLCS</th></tr><tr><th>θ</th><th>Isolated Nodes</th><th>Edges</th><th>Avg. Degree</th><th>Avg. Weighted Degree</th></tr></thead><tbody><tr><td>0.1</td><td>31</td><td>5577366</td><td>944.036</td><td>179.431</td></tr><tr><td><strong>0.2</strong></td><td><strong>143</strong></td><td><strong>1739042</strong></td><td><strong>294.354</strong></td><td><strong>88.883</strong></td></tr><tr><td>0.3</td><td>606</td><td>534648</td><td>90.496</td><td>38.735</td></tr><tr><td><strong>0.4</strong></td><td><strong>1200</strong></td><td><strong>271826</strong></td><td><strong>46.010</strong></td><td><strong>22.998</strong></td></tr><tr><td>0.5</td><td>2465</td><td>103028</td><td>17.439</td><td>10.430</td></tr><tr><td>0.6</td><td>3781</td><td>29298</td><td>4.959</td><td>3.596</td></tr><tr><td><strong>0.7</strong></td><td><strong>5038</strong></td><td><strong>8080</strong></td><td><strong>1.368</strong></td><td><strong>1.269</strong></td></tr><tr><td>0.8</td><td>5517</td><td>5914</td><td>1.001</td><td>0.997</td></tr><tr><td>0.9</td><td>5568</td><td>5788</td><td>0.980</td><td>0.980</td></tr></tbody></table>

The obtained set $S$ of sequences consisted of large amount of different sequences, often very similar. Such large amount of information is hard to clearly visualize and to present in well arranged way. Moreover, the comparison of users based on their behavior is computationally expensive with such dimension. Therefore, we present in the article [21] the identification of significant behavioral patterns based on the sequence similarity, which allows us to reduce amount of extracted sequences.

We have used T-WLCS methods for the similarity measurement of sequences. The T-WLCS find the longest common subsequence $\alpha$ of compared sequences $\beta_{x}$ and $\beta_{y}$, where $\alpha \subseteq \beta_{x} \land \alpha \subseteq \beta_{y}$, with relation to T-WLCS. Similarity was counted by the Equation 1.

$$Sim(\beta_{x}, \beta_{y}) = \frac{(l(\alpha) * h)^{2}}{l(\beta_{x}) * l(\beta_{y})}, \qquad (1)$$

where $l(\alpha)$ is a length of the longest common subsequence $\alpha$ for sequences $\beta_{x}$ and $\beta_{y}$; $l(\beta_{x})$ and $l(\beta_{y})$ are analogically lengths of compared sequences $\beta_{x}$ and $\beta_{y}$, and
$$h = \frac{\text{Min}(l(\beta_x), l(\beta_y))}{\text{Max}(l(\beta_x), l(\beta_y))} \qquad (2)$$

On the basis of selected T-WLCS method for finding the similarity of sequences, we have constructed the similarity matrix for sequences (|S| × |S|) which can be represented using tools of graph theory. For the visualization of network was constructed weighted graph G(V, E), where weight w is defined as function w : E(G) → R, when w(e) > 0. Set V is represented by set of sequences S, weights w are evaluated by the similarity of sequences, see Equation 1, depending on selected method. In Table 3 is more detailed description of weighted graphs of sequences, where weight is defined by T-WLCS method for selected threshold θ (threshold for edges filtering - edges with smaller weights are removed). The number of nodes for each graph is 5908.

## 5.1 Reduction of Large Amount of Sequences by Left-Right Oscillate Algorithm

We described the procedure for extraction of sequence from the LMS system in previous parts of the paper. We created the graphs of sequences by T-WLCS method. The examples in this section show how the graphs of sequences are divided to clusters by Left-Right Oscillate algorithm. We will use the concept "clusters" instead of "communities" in this part of the paper because we used Left-Right Oscillate algorithm for finding clusters of sequences.

<table><caption>**Table 4.** Description of Selected Biggest Clusters of Sequence Graphs for T-WLCS Method</caption><thead><tr><th colspan="3">T-WLCS</th></tr><tr><th>θ</th><th>Nodes</th><th>Edges</th></tr></thead><tbody><tr><td>0.2</td><td>5763</td><td>1739040</td></tr><tr><td>0.4</td><td>4639</td><td>271732</td></tr><tr><td>0.7</td><td>142</td><td>1030</td></tr></tbody></table>

For the illustration, we have selected three different graphs from Table 3. These are the graphs created with parameter θ is greater than 0.2, 0.4 and 0.7. In each graph, there was identified the largest connected component, and on the basis on this component was created the new graph. This graph was partitioned by our new Left-Right Oscillate algorithm (maximum cycles of Lanczos algorithm inside Left-Right Oscillate algorithm was set to 1500). The sizes of these newly generated graphs are presented in Table 4.

Individual outputs and quality cuts of graphs after Left-Right Oscillate algorithm can be seen in Table 5, Table 5 and Table 7. In these tables we have column "Modularity Type" where row "Original" is without applied Left-Right Algorithm and "Left-Right" is row with information after Left-Right algorithm. Other columns in these tables are "Modularity" (see section 3.1), "Clusters" with amount of clusters after partitioning and columns with sizes of the top three communities (columns "Size of 1th", "Size of 2th", "Size of 3th").
<table><caption>**Table 5.** Partitioning of Sequence Graph for $\theta \le 0.2$</caption><thead><tr><th colspan="6">S<sub>c</sub> = 1</th></tr><tr><th>Modularity Type</th><th>Modularity</th><th>Clusters</th><th>Size of 1th</th><th>Size of 2nd</th><th>Size of 3rd</th></tr></thead><tbody><tr><td>Original</td><td>0.23471</td><td>85</td><td>560</td><td>365</td><td>104</td></tr><tr><td>Left-Right</td><td>0.23471</td><td>85</td><td>560</td><td>365</td><td>104</td></tr></tbody><thead><tr><th colspan="6">S<sub>c</sub> = 3</th></tr><tr><th>Modularity Type</th><th>Modularity</th><th>Clusters</th><th>Size of 1th</th><th>Size of 2nd</th><th>Size of 3rd</th></tr></thead><tbody><tr><td>Original</td><td>0.23471</td><td>85</td><td>560</td><td>365</td><td>104</td></tr><tr><td>Left-Right</td><td><b>0.23721</b></td><td><b>7</b></td><td><b>581</b></td><td><b>421</b></td><td><b>104</b></td></tr></tbody><thead><tr><th colspan="6">S<sub>c</sub> = 6</th></tr><tr><th>Modularity Type</th><th>Modularity</th><th>Clusters</th><th>Size of 1th</th><th>Size of 2nd</th><th>Size of 3rd</th></tr></thead><tbody><tr><td>Original</td><td>0.23471</td><td>85</td><td>560</td><td>365</td><td>104</td></tr><tr><td>Left-Right</td><td><b>0.23717</b></td><td><b>5</b></td><td><b>580</b></td><td><b>424</b></td><td><b>104</b></td></tr></tbody></table>

<table><caption>**Table 6.** Partitioning of Sequence Graph for $\theta \le 0.4$</caption><thead><tr><th colspan="6">S<sub>c</sub> = 1</th></tr><tr><th>Modularity Type</th><th>Modularity</th><th>Clusters</th><th>Size of 1th</th><th>Size of 2nd</th><th>Size of 3rd</th></tr></thead><tbody><tr><td>Original</td><td>0.52153</td><td>656</td><td>829</td><td>648</td><td>497</td></tr><tr><td>Left-Right</td><td>0.52153</td><td>656</td><td>829</td><td>648</td><td>497</td></tr></tbody><thead><tr><th colspan="6">S<sub>c</sub> = 3</th></tr><tr><th>Modularity Type</th><th>Modularity</th><th>Clusters</th><th>Size of 1th</th><th>Size of 2nd</th><th>Size of 3rd</th></tr></thead><tbody><tr><td>Original</td><td>0.52153</td><td>656</td><td>829</td><td>648</td><td>497</td></tr><tr><td>Left-Right</td><td><b>0.52820</b></td><td><b>101</b></td><td><b>956</b></td><td><b>720</b></td><td><b>579</b></td></tr></tbody><thead><tr><th colspan="6">S<sub>c</sub> = 6</th></tr><tr><th>Modularity Type</th><th>Modularity</th><th>Clusters</th><th>Size of 1th</th><th>Size of 2nd</th><th>Size of 3rd</th></tr></thead><tbody><tr><td>Original</td><td>0.52153</td><td>656</td><td>829</td><td>648</td><td>497</td></tr><tr><td>Left-Right</td><td><b>0.52955</b></td><td><b>59</b></td><td><b>962</b></td><td><b>739</b></td><td><b>594</b></td></tr></tbody><thead><tr><th colspan="6">S<sub>c</sub> = 10</th></tr><tr><th>Modularity Type</th><th>Modularity</th><th>Clusters</th><th>Size of 1th</th><th>Size of 2nd</th><th>Size of 3rd</th></tr></thead><tbody><tr><td>Original</td><td>0.52153</td><td>656</td><td>829</td><td>648</td><td>497</td></tr><tr><td>Left-Right</td><td><b>0.52890</b></td><td><b>40</b></td><td><b>952</b></td><td><b>794</b></td><td><b>586</b></td></tr></tbody></table>

It is apparent that the modularity is improved, if the parameter $S_c$ (size of smallest clusters - see Algorithm 3.1) of the Left-Right Oscillate algorithm is greater than 1.

## 6 Conclusion

In the paper we introduced the Left-Right Oscillate algorithm, which allows us to improve the results of community detection based on spectral ordering. We showed effect of parameter $S_c$ on the quality of clustering of sequences, which were extracted from the Moodle e-learning system. This allows us to better identify the same behavior of students in the online e-learning system. Modularity was used for measuring the quality
<table><caption>Table 7. Partitioning of Sequence Graph for $\theta \le 0.7$</caption><thead><tr><th colspan="7">S<sub>c</sub> = 1</th></tr><tr><th>Modularity Type</th><th>Modularity</th><th>Clusters</th><th>Size of 1th</th><th>Size of 2nd</th><th>Size of 3rd</th></tr></thead><tbody><tr><td>Original</td><td>0.26457</td><td>63</td><td>15</td><td>15</td><td>14</td></tr><tr><td>Left-Right</td><td>0.26457</td><td>63</td><td>15</td><td>15</td><td>14</td></tr></tbody><thead><tr><th colspan="7">S<sub>c</sub> = 3</th></tr><tr><th>Modularity Type</th><th>Modularity</th><th>Clusters</th><th>Size of 1th</th><th>Size of 2nd</th><th>Size of 3rd</th></tr></thead><tbody><tr><td>Original</td><td>0.26457</td><td>63</td><td>15</td><td>15</td><td>14</td></tr><tr><td>Left-Right</td><td><strong>0.38731</strong></td><td><strong>12</strong></td><td><strong>23</strong></td><td><strong>22</strong></td><td><strong>21</strong></td></tr></tbody><thead><tr><th colspan="7">S<sub>c</sub> = 6</th></tr><tr><th>Modularity Type</th><th>Modularity</th><th>Clusters</th><th>Size of 1th</th><th>Size of 2nd</th><th>Size of 3rd</th></tr></thead><tbody><tr><td>Original</td><td>0.26457</td><td>63</td><td>15</td><td>15</td><td>14</td></tr><tr><td>Left-Right</td><td><strong>0.46304</strong></td><td><strong>7</strong></td><td><strong>45</strong></td><td><strong>15</strong></td><td><strong>14</strong></td></tr></tbody><thead><tr><th colspan="7">S<sub>c</sub> = 10</th></tr><tr><th>Modularity Type</th><th>Modularity</th><th>Clusters</th><th>Size of 1th</th><th>Size of 2nd</th><th>Size of 3rd</th></tr></thead><tbody><tr><td>Original</td><td>0.26457</td><td>63</td><td>15</td><td>15</td><td>14</td></tr><tr><td>Left-Right</td><td><strong>0.45416</strong></td><td>4</td><td><strong>58</strong></td><td><strong>42</strong></td><td><strong>27</strong></td></tr></tbody></table>

of the distribution of sequences within clusters. In the future work we want to consider using the Left-Right Oscillate algorithm for hierarchical graph of sequences partitioning. Thanks to this we want to aim a more appropriate division of student's behavioral patterns.

## Acknowledgment

This work was partially supported by SGS, VSB – Technical University of Ostrava, Czech Republic, under the grant No. SP2012/151 Large graph analysis and processing and by the European Regional Development Fund in the IT4Innovations Centre of Excellence project (CZ.1.05/1.1.00/02.0070).

## References

1. F. Castro, A. Vellido, A. Nebot, and F. Mugica. Applying data mining techniques to e-learning problems. *Studies in Computational Intelligence (SCI)*, 62:183–221, 2007.

2. B. Chen, C. Shen, G. Ma, Y. Zhang, and Y. Zhou. The evaluation and analysis of student e-learning behaviour. In *IEEE/ACIS 10th International Conference on Computer and Information Science (ICIS)*, 2011, pages 244–248, 2011.

3. J. Chen, K. Huang, F. Wang, and H. Wang. E-learning behavior analysis based on fuzzy clustering. In *Proceedings of International Conference on Genetic and Evolutionary Computing*, 2009.

4. D. Cheng, R. Kannan, S. Vempala, and G. Wang. On a recursive spectral algorithm for clustering from pairwise similarities. Technical report, MIT, 2003.

5. F. R. K. Chung. *Spectral Graph Theory*, volume 92. American Mathematical Society, 1997.
6. A. Dasgupta, J. Hopcroft, R. Kannan, and P. Mitra. Spectral clustering by recursive partitioning. In *ESA'06: Proceedings of the 14th conference on Annual European Symposium*, pages 256–267. Springer-Verlag, 2006.

7. C. Ding and X. He. Linearized cluster assignment via spectral ordering. *Twentyfirst international conference on Machine learning ICML 04*, 21:30, 2004.

8. S. N. Dorogovtsev and J. F. F. Mendes. *Evolution of Networks: From Biological Nets to the Internet and WWW*, volume 57. Oxford University Press, 2003.

9. P. Dráždilová, G. Obadi, K. Slaninová, S. Al-Dubaee, J. Martinovič, and V. Snášel. Computational intelligence methods for data analysis and mining of elearning activities. In F. Xhafa, S. Caballe, A. Abraham, T. Daradoumis, and J. Perez, editors, *Studies in Computational Intelligence For Technology Enhanced Learning*, volume 273, pages 195–224. Heidelberg, Germany: Springer-Verlag, 2010.

10. P. Dráždilová, K. Slaninová, J. Martinovič, G. Obadi, and V. Snášel. Creation of students' activities from learning management system and their analysis. In A. Abraham, V. Snášel, and K. Wegrzyn-Wolska, editors, *IEEE Proceedings of International Conference on Computational Aspects of Social Networks CASON 2009*, pages 155–160, 2009.

11. A. El-halees. Mining students data to analyze learning behavior: a case study. 2008.

12. M. Girvan and M. E. J. Newman. Community structure in social and biological networks. *Proceedings of the National Academy of Sciences of the United States of America*, 99(12):7821–7826, 2002.

13. A. Guo and H. Siegelmann. *Time-Warped Longest Common Subsequence Algorithm for Music Retrieval*, pages 258–261. Universitat Pompeu Fabra, 2004.

14. A. Hershkovitz and R. Nachmias. Learning about online learning processes and students' motivation through web usage mining. *Interdisciplinary Journal of E-Learning and Learning Objects*, 5:197–214, 2009.

15. D. S. Hirschberg. Algorithms for the longest common subsequence problem. *J. ACM*, 24:664–675, October 1977.

16. M. Müller. *Information Retrieval for Music and Motion*. Springer, 2007.

17. M. E. J. Newman, A.-L., and D. J. Watts. *The structure and dynamics of networks*, volume 107. Princeton University Press, 2006.

18. M. E. J. Newman. Detecting community structure in networks. *The European Physical Journal B Condensed Matter*, 38(2):321–330, 2004.

19. M. E. J. Newman. Modularity and community structure in networks. *Proceedings of the National Academy of Sciences of the United States of America*, 103(23):8577–8582, 2006.

20. M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. *Physical Review E - Statistical, Nonlinear and Soft Matter Physics*, 69(2 Pt 2):16, 2004.

21. K. Slaninová, T. Kocyan, J. Martinovič, P. Dráždilová, and V. Snášel. Dynamic time warping in analysis of student behavioral patterns. In *Proceedings of the Dateso 2012, Annual International Workshop on DAtabases, TExtS, Specifications and Objects*, pages 49–59, 2012.

22. W. M. P. van der Aalst. *Process Mining: Discovery, Conformance and Enhancement of Business Processes*. Springer Heidelberg, 1st edition, 2011.

23. W. M. P. van der Aalst, H. A. Reijers, and M. Song. Discovering social networks from event logs. *Comput. Supported Coop. Work*, 14(6):549–593, 2005.

24. S. White and P. Smyth. A spectral clustering approach to finding communities in graphs. *Proceedings of the fifth SIAM international conference on data mining*, 119:274, 2005.

25. F. Yang, R. Shen, and P. Han. Construction and application of the learning behavior analysis center based on open e-learning platform. 2002.

26. M. Zorrilla, E. Menasalvas, D. Marín, E. Mora, and J. Segovia. Web usage mining project for improving web-based learning sites. In *Computer Aided Systems Theory EUROCAST 2005*, volume 3643/2005 of *Lecture Notes in Computer Science*, chapter Web Usage Mining Project for Improving Web-Based Learning Sites. Springer Berlin / Heidelberg, 2005.