Arne Hendrik Schulz
email: ahschulz@ifib.de

Debora Jeske
email: debora.jeske@unn.ac.uk

Learner Differences in the Online Context: Introducing a New Method

Keywords: E-learning, log file analysis, cluster analysis, learner group differences, learning strategies

The paper introduces an alternative method to analyze different learning styles among students. This method was developed as an alternative to more traditional methods such as hierarchical cluster analysis. The method was tested using a large data set (n = 868) which included participants completing a small e-module in addition to a small number of measures to assess learner characteristics. The resulting log files were analyzed using the method. Results were similar to those observed using traditional methods. The method provides a new starting point for subsequent analysis and identification of learner differences using other information such as log files from e-learning and Massive Online Open Courses (MOOCs).

Introduction

The research about learners in e-learning environments is a very broad research theme. A lot of research addresses pedagogic questions like acceptance of tests and materials or the extent to which learners benefit from using digital systems like Learning Management Systems [START_REF] Concannon | What campus-based students think about the quality and benefits of e-learning[END_REF][START_REF] Garrison | E-Learning in the 21st Century: A Framework for Research and Practice[END_REF][START_REF] Selim | Critical success factors for e-learning acceptance: Confirmatory factor models[END_REF]. Determining the needs of different users and learner groups plays a significant role in education as this allows educators, practitioners and designers to respond to and adapt tutor instructions to various learning characteristics exhibited by these groups. This has generated numerous studies on adaptive hypermedia, personalized design and e-learning [START_REF] Brusilovsky | Adaptive Hypermedia. User Modeling and User-Adapted Interaction[END_REF][START_REF] Hsiao | Motivational Social Visualizations for Personalized E-Learning[END_REF].

The use of trace and log file information to identify different groups of learners and users using various algorithms and analyses allows researchers to examine different behaviors. This approach of identifying different user groups is very helpful by combining it with additional behavioral data gathered during online activities. In addition, when we try to understand learning processes, many more variables may come into play. The pace at which we learn and how we navigate is often influenced by various different learner characteristics ranging from prior knowledge, age, motivation, learning preferences and strategies [START_REF] Jeske | Evaluation and revision of the Study Preference Questionnaire: Creating a user-friendly tool for nontraditional learners and learning environments[END_REF]. This means that when we create clusters using log files, we can use these new clusters in combination with additional learner characteristics to better understand cluster differences. These independent variables might inform research in the area of digital competencies which e-learners may lack and hence impact the efficiency with which e-learning tools can support their learning.

Previous research

There has been a lot of research on the topic of learner analytics in digital environments, recently summarized under the term learning analytics [START_REF] Greller | Translating Learning into Numbers: A Generic Framework for Learning Analytics[END_REF], a subcategory of educational data mining [START_REF] Baker | The state of educational data mining in 2009: A review and future visions[END_REF][START_REF] Dyckhoff | Design and Implementation of a Learning Analytics Toolkit for Teachers[END_REF][START_REF] Romero | Educational Data Mining: A Review of the State of the Art[END_REF]. Chen et al. [START_REF] Chen | Diagnosis of students' online learning portfolios[END_REF] create a framework for analyzing students' online learning portfolios. They include logon times, logon days, general activity within the system (clicks, duration of studying) and course results (midterm and final) of 162 undergraduate students. Results show that higher online learning activity and more intensive work with online materials leads to significantly better course results and grades. Del Valle and Duffy [START_REF] Valle | Online learning: Learner characteristics and their approaches to managing learning[END_REF] clustered 59 learners of an "online teacher professional development curriculum". Based on the online behavior (total time online, course duration, average inter-session interval, proportion of time on learning resources, proportion of learning resources accessed, exploration, proportion of time in messenger) the authors extracted 3 user clusters named mastery orientated, task focused and minimal approach. The former two groups can be characterized as being more active within the course; the last group is more inactive, but has the highest self-reported prior knowledge. The more active groups (mastery orientated and task focused) had a higher satisfaction and higher learning effect (self-reported). Lee [START_REF] Lee | Investigating students' learning approaches, perceptions of online discussions, and students' online and academic performance[END_REF] asked 116 students of a general education course at a Taiwan university to fill out a questionnaire about their online learning perception and styles. Three clusters were extracted and described. One cluster represented students that are highly motivated and adopted deep learning strategies, the second cluster had students that were also highly motivated and tended to adopt deep learning strategies. The last cluster had students with the lowest motivation and adoption of deep strategies. Quinell et al. [START_REF] Quinnell | Conceptions of Biology and Approaches to Learning of First Year Biology Students: Introducing a technique for tracking changes in learner profiles over time[END_REF] also found significant differences in the learner styles of first year university degree biology students. There are several other studies researching students' performances and clustering them using self-reported measures [START_REF] Richardson | Mental models of learning in distance education[END_REF][START_REF] Sparks | Profiles of more and less successful L2 learners: A cluster analysis study[END_REF][START_REF] Wade | An Analysis of Spontaneous Study Strategies[END_REF]. Nevertheless, most of these studies rely only on questionnaires and sometimes on examination and term results or grades. They do not take students' online behavior into account.

Goals of this research

In order to capture the learner characteristics of more diverse and broader learners, it will be essential to utilize new tools to analyze patterns and optimize what we learn about our learners. The aims of this paper are therefore to: (1) describe a new method to cluster learners and (2) demonstrate the utility of this method in a large data set of e-learners for which both log files and self-reported learner characteristics had been collected. We focused on variables that had also been included in the examination of learner differences in previous research. We provide evidence demonstrating that the new method performs similarly and as well as traditional cluster analysis.

Introduction to the New Clustering Method

All user actions within our developed e-learning model (including content and questions) are logged. This information is used to extract separate user groups based on their systems' usage. We cluster the user using hierarchical clustering technique [START_REF] Everitt | Cluster analysis[END_REF][START_REF] Hastie | The Elements of Statistical Learning: Data Mining, Inference, and Prediction[END_REF][START_REF] Liu | Web data mining: exploring hyperlinks, contents, and usage data[END_REF] with Ward's [START_REF] Ward | Hierarchical Grouping to Optimize an Objective Function[END_REF] linkage algorithm. The distance between two users is measured via two measures developed by Xiao et al. [START_REF] Xiao | Measuring similarity of interests for clustering webusers[END_REF] and Xiao and Zhang [START_REF] Xiao | Clustering of web users using session-based similarity measures[END_REF], named frequency based measure and viewing-time based measure. Both measures are based on the cosine angle [START_REF] Tan | Introduction to data mining[END_REF] and are widely used in the areas of information retrieval [START_REF] Grossman | Information Retrieval: Algorithms and Heuristics[END_REF]. The similarity of two users, according to the frequency based measure, is calculated using the following formula:

( ) ∑ ) ( )) √∑ )) ∑ ( )) ∑ ))
is the squared sum of the access times of all accessed pages by user u i/j and ∑ ) ( )) is the product of all accesses done by both users. If both users access the same pages and have identical accesses on all visited pages, their similarity will be 1. If they do not visit any common pages at all, their similarity will be 0.

The viewing-time based similarity of two users is calculated using the following formula:

( ) ∑ ) ( )) √∑ )) ∑ ( )) ∑ ))
is the sum of the squared viewing times of all visited pages by user u i and ∑ ) (

)) is the product of all viewing times visited by both compared users. The interpretation of the results is straightforward. We combine both algorithms and weight them. Weighting is needed as the frequency based measure may not bring up the best results, due to the fact that many users visited each page of the e-module once only: the users had a mean of 19.4 page visits (sd = 4.1). Compared to the 18 pages the e-module consisted of, there seems to be not a big variety among the users. Therefore, we weight the viewing-time based measure with .85 and the frequency based measure with .15. The final measure has the following formula and will be referred to as cosine similarit y :

( ) (
) )

The idea of both algorithms is that users with similar interests have a common "footprint" in the log files. Using the frequency based measure, this means that they will have the same numbers of accesses of common pages [cf. 26]). Using the viewing-time based measure assumes that the same interests are reflecting in the same viewing times. Furthermore, this measure is indirectly taking into account more hidden variables like literacy (affecting the viewing time). Both algorithms do not measure sequence of the pages. The e-learning modules are linear which does not need such a feature.

Application of the New Method

In the next step, we wanted to apply the new method to a data set of e-learners for which we also had log file information. As shown above, we took the number of page visits for the frequency based measure and the visiting time per page for the viewingtime based measure. If a user had multiple page visits, the viewing times were summed up.

The test material was a small e-module featuring five short chapters on team development. Participants had to complete a number of short test questions. Following this, participants completed a set of items to assess their learning characteristics.

Self-reported variables

The questions included demographics, prior knowledge about the topic and about elearning in general, as well as questions about the self-reported measures (discussed further below). These were accessed via a questionnaire that had to be answered before the module itself.

Deep and surface learning strategy: deep versus surface processing refers to learning styles that capture how learners utilize diverse learning strategies to come to a specific goal [START_REF] Biggs | The revised two-factor Study Process Questionnaire: R-SPQ-2F[END_REF]. Deep and surface strategies were identified using three items which were inspired by subscales produced by Biggs et al. [START_REF] Biggs | The revised two-factor Study Process Questionnaire: R-SPQ-2F[END_REF]. An example item for deep strategy is: "When I am interested in a topic, I spend additional time on trying to learn more information about it". An example item for surface strategy is: "I tend to learn more than is necessary" (reverse-coded). So this learning difference helps to detect the amount of effort that individuals invest into learning about a topic, that is, either in-depth or superficially. The response options ranging from (1) "never or only rarely true of me" to (5) "always or almost always true of me".

Serialist learning preference: serialists can be labeled "operation learners" with a more pronounced bottom-up approach [START_REF] Jeske | Evaluation and revision of the Study Preference Questionnaire: Creating a user-friendly tool for nontraditional learners and learning environments[END_REF][START_REF] Ford | Learning Styles and Strategies of Postgraduate Students[END_REF]. These individuals tend to focus on the immediate or local aspects. They have a narrower focus, oftentimes emphasizing the details and the way to success rather than trying to achieve a larger overview. Serialists learn in a linear and sequential fashion which goes hand in hand with an emphasis on memorizing facts for reproduction, emphasizing product in order to construe logical arguments and simple hypotheses [START_REF] Ford | Cognitive styles and virtual environments[END_REF]. Serialist processing is often contrasted with holist processing. Holists tend have a more global strategy and wider focus on several aspects [START_REF] Ford | Learning Styles and Strategies of Postgraduate Students[END_REF]. This also means they like to focus on numerous topics simultaneously, emphasizing the use of numerous sources in order to elaborate on information and seek patterns amongst facts. These aspects lead to more generalized descriptions and higher level comprehension, but potentially at the expense of individual detail. In all three datasets, serialist preference was measured using 7 items. An example here is: "I deal with a new topic as thoroughly as I can first time around". The response options ranged from (1) "strongly disagree" to (5) "strongly agree".

Prior knowledge: we also asked participants one item each about their prior knowledge with e-learning modules and the topic of the e-module. Knowledge about e-learning was assessed using four answering options: (1) I have a lot of experience with e-learning; (2) I have some experience with e-learning; (3) I have very little experience with e-learning; and (4) I have no prior experience with e-learning. The four answering options asked about topic familiarity as follows: (1) I was very knowledgeable; (2) I was quite knowledgeable; (3) I knew a little; and (4) I didn't know anything about it. All answers were reverse-coded, so that more knowledge corresponded with higher scores.

All items measuring learning strategies and preferences were summarized to provide a mean-centered composite for each scale. All scales featured a reliability coefficient above .7.

Participants and procedure

Participants were students at a distance-learning institution in Germany. They were offered opportunity to participate in exchange for obtaining research credit (N=686). We collected information about participant sex and age. Participants were between 17 and 63 years old (M=32.62, SD=9.27), the most frequent age (mode) indicated was 28 with a mean of 32.6 years (SD = 9.2). About one fifth were female (n = 145). Male participants were slightly younger (M = 32.3 vs. M = 33.6). A t-test provides no significant difference (t-value = 1.402, degrees of freedom = 218.441, p-value < 0.16).

Data collection took place in spring 2013. In total, 686 participants completed both the test and the questionnaire. Missing and incomplete information reduced the number to 669 participants.

Results of the Analysis

We first examined the given cluster solutions. Scree plots and dendrograms led us to a four cluster solution. In the next step, we conducted descriptive statistics and correlations of the measures (Table 1). Finally, we examined user clusters based on log file information obtained from all learners during the e-module. In the final step, we examined how the clusters we identified using log files, and how they differed in terms of their learner characteristics.

Cluster results

The visualization of the clustering process in the dendrogram indicated four possible solutions, between two and four groups of classifications. A scree plot indicated a three cluster solution whereas a four cluster solution leads to a higher distance between the clusters (.099 versus .109) and a lower within-group distance (.171 versus .169). Possible distances range from 0 to 1 as the calculated distances have the identical range. Additionally, the average silhouette width indicator [START_REF] Kaufman | Finding Groups in Data. An Introduction to Cluster Analysis[END_REF] suggests a four cluster solution (.251 versus .239). The average silhouette width ranges from -1 to 1. The absolute value is interpreted. Additionally, the fourth generated cluster in the four cluster solution (split from cluster 2 in the three cluster solution) shows a better silhouette than the non-split cluster 2 in the three cluster solution, Therefore, we decided to use a four cluster solution.

Descriptives for self-report measures

Descriptive statistics about the self-reported measures show that the users selected response options in the middle of the five-point scale with higher average scores for deep strategy processing and serialist preferences (see Table 1). The prior knowledge was above average for both variables with a slightly higher value for prior e-learning knowledge (and a lower standard deviation). The correlation matrix reveals that knowledge and behavior are almost uncorrelated and mostly not significant. Prior topic knowledge and prior e-learning knowledge have a weak correlation (r = .17, p < .001). Deep strategy and surface strategy has a moderate and negative correlation as expected (r = -.51, p < .001). In addition, surface strategy and serialist preference correlate negatively (r = -.18, p < .001). For more details see Table 2.

Learner differences

The cluster sizes were big enough to test them for significant differences related to the following characteristics: age, surface strategy, deep strategy, prior knowledge (according to the e-module topic and e-learning in general) and serialist learning preference. Additionally, we included the time used in the e-module and the number of page visits in the analysis. Covariates were gender and age (where age was not a dependent variable).

The results of the analysis of variance suggest significant group differences in relation to the prior e-learning knowledge of the participants in the different clusters, their level of serialist learning preferences and the amount of time used (see Table 3). A number of other differences appear relevant as a means to differentiate the clusters from one another. The findings are summarized in Table 3. In order to label the three clusters of e-learners coherently, we decided to label the clusters first and foremost based on their level of prior knowledge as e-learning experts (those with the highest prior knowledge), e-learning users (with average prior knowledge) or e-learning novices (with low prior knowledge). All clusters featuring high serialist learning preferences were labeled as sequential, as in very orderly, and those with low values on this variable as superficial e-learners. All clusters featuring high scores in terms of their surface strategy approach were considered as surface elearners. We focused on the significant differences only.

We consider Cluster 1 as disengaged but knowledgeable e-learning experts. The assigned users have the highest e-learning knowledge (3.01 out of 4), but only average knowledge about the topic compared to other clusters (3.22 out of 4). They also exhibit the lowest serialist preference compared to other clusters (3.49 out of 5) and appear to be more disengaged (superficial in their approach). They spend a relatively low amount of time in the small e-module overall compared to other groups. High e-learning experience might have led to greater disengagement with the e-module. In addition, their tendency to work in a less sequential and detail-oriented manner led to less time spent in the module.

Individuals in Cluster 2 are engaged and knowledgeable e-learning users. They appear to have average topic knowledge (3.27 out of 5) and e-learning experience (2.77 out of 5, hence users, not experts). They show a more pronounced serialist preference (3.62 out of 5). They have, however, invested quite a lot in learning as they also spend more time in the e-module than two out of the four clusters. This suggests that average experience and greater orientation to detail also increases learning time.

306

Cluster 3 seems to include disengaged but very knowledge e-learning users. They have the highest familiarity with the topic (3.35 out of 4), but average familiarity with e-learning (2.66 out of 4). They have serialist preferences similar to those of Cluster 2 (3.60 out of 5). At the same time, this cluster spends the least amount of time on the emodule. This suggests that while they are detail-oriented, higher familiarity with the topic may lead to a more disengaged learning process.

Cluster 4 includes the engaged but not very knowledgeable e-learning novices. This group has very limited e-learning experience (2.47 out of 4) and limited topic knowledge (2.97 out of 4). At the same time, this group includes the individuals with the strongest serialist preference. They will diligently study the materials, and take longer than individuals from other clusters. The novelty of the topic and e-learning in addition to their detail-orientation (via serialist preference) may explain why they are more engaged with the materials.

Our clusters suggest that prior knowledge can help to explain cluster difference in terms of time dedicated to the e-module they are studying. Learning characteristics such as serialist preferences (detail orientation and sequential processing) may play an additional role when trying to explain cluster differences, especially in relation to the amount of time that individuals will invest in a task.

Performance of the cosine similarity

We also examined the type of clusters obtained using the Euclidean distance [START_REF] Deza | Encyclopedia of Distances[END_REF] instead of the cosine angle, again applying Ward's linkage method in the hierarchical cluster analysis. The results are largely identical, resulting in four clusters that showed similar learning differences. An analysis of variance using four clusters revealed several significant differences, in relation to prior knowledge (e-learning and topic), serialist learning preference and age.

Whereas the results were quite comparable, we observed two differences. First, the clusters computed with the Euclidean distance were more equally distributed, resulting in two clusters with about 210 cases each and two further clusters including 116 and 132 cases, respectively. The generated clusters using the cosine similarity are significantly unequally distributed, resulting in two big clusters (281 and 291 cases) and two small clusters (65 and 32 cases). Secondly, and more importantly, the goodness of fit between the two dissimilarity measures is significantly different. We computed the Average Silhouette Width [START_REF] Rousseeuw | Silhouettes: A graphical aid to the interpretation and validation of cluster analysis[END_REF] for both solutions. The Silhouette Width compares the dissimilarity between within-cluster cases and without-cluster cases for each case. The value has a range from -1 to 1, where 1 stands for a perfect fit of that case into its designated cluster. The Average Silhouette Width is the grand mean over all cases. Kaufman and Rousseeuw [START_REF] Kaufman | Finding Groups in Data. An Introduction to Cluster Analysis[END_REF] define all values below 0.25 as not suitable ("no structure found"). Values between 0.26 and 0.5 are being considered as having a weak structure, values between 0.51 and 0.7 are seen that a reasonable structure has been found and values above 0.7 stand for a strong structure.

The Average Silhouette Width of the solution defined by the Euclidean distance was 0.04. This solution indicates that the solution did not result in a meaningful structure. One bigger and one smaller cluster also had Average Silhouette Widths values below 0. The two remaining clusters showed a weak structure (0.27 and 0.37).

The clusters generated by the cosine similarity led to a better detection of the underlying structure. The Average Silhouette Width value was 0.26, which means that the cosine similarity helped to detect evidence of a weak structure. One big cluster had an Average Silhouette Width value of 0.53 ("reasonable structure found") while one small cluster had a width of 0.32. The values of the two remaining clusters ranged from -0.05 up to 0.04. This means that the structure still cannot be regarded as being good, but the algorithm shows a better solution than the Euclidean distance.

Discussion

The results of the new method suggest that we can obtain differentiated cluster profiles by considering both log files and self-report data together. The new method presents an alternative to hierarchical clustering, which resulted in similar results. The advantages of the new method are as follows: first, the algorithms we used were developed for the application in web-based digital systems; additionally, we combined two measures to include both the time spent on every page and the number of single page accessed by each user; and finally, our analyses showed that the cosine similarity had a better detection of the underlying structure than the Euclidean distance. Xiao et al. [START_REF] Xiao | Measuring similarity of interests for clustering webusers[END_REF], Xiao and Zhang [START_REF] Xiao | Clustering of web users using session-based similarity measures[END_REF], and Kumar et al. [START_REF] Kumar | Rough clustering of sequential data[END_REF] developed more algorithms to compare users. Some of these algorithms include the users' path and can lead to better cluster solutions. In fact, due to the linear structure of the e-module, these algorithms were not needed, but could be implemented easily if needed.

In conclusion, we believe that the combination of new methods and more data can aid future learning analyses aimed at detecting digital competencies and personalization opportunities. Most of the research tends to focus on the needs of younger learners. However, given the importance of lifelong learning, future users are likely to show increased demographic and skill diversity. As learners become more differentiated in terms of their past learning (prior knowledge), age and various related skills (digital competence), it becomes more appropriate to include these variables in order to consider their influence. This development also suggests that learners will start from different baselines. New methods such as the one we introduced will provide the means to consider such differences and characteristics and address these potentially in personalized and different tutoring -so as to improve performance for all users across the board and to increase user satisfaction and optimize the learning experience [START_REF] Facca | Mining interesting knowledge from weblogs: a survey[END_REF][START_REF] Mobasher | Automatic personalization based on Web usage mining[END_REF].

Figure 1

 1 Figure 1 also visualizes how the four clusters compare in terms of the learningrelevant characteristics (deep strategy, surface strategy, serialist preferences, and prior learning.

Fig. 1 :

 1 Fig. 1: Visualized cluster differences

  Xiao et al. define a webpage that consists of k different pages P = { p 1 , p 2 , p 3 , … p k } accessed by n different users U = { u 1 , u 2 , u 3 , … u n }. Frequency based measure takes into account how often pages are visited by the users, while the viewing-time based measure considers the amount of time each user is spending on different pages. Therefore, let acc(p k ,u i ) be the number of times user u i is accessing page p k and let t(p k ,u i ) be the time t the user u i spends viewing page p k . If a user is not accessing a page (and is not spending any time on that page) each measure will be 0.

Table 1 :

 1 Summary of self-reported measures (N=669)

	Variable	Scale Mean SD
	Deep strategy	5	3.52 0.85
	Surface strategy	5	2.98 0.95
	Serialist preference	5	3.57 0.67
	Prior topic knowledge	4	2.90 1.12
	Prior e-learning knowledge	4	3.07 1.07

Table 2 :

 2 Correlation of self-reported measures

		Deep	Surface	Serialist	Prior topic	Prior e-
		Strategy	Strategy	preference	knowledge	learning
						knowledge
	Deep strategy	1
	Surface strategy	-0.51*** 1
	Serialist	0.02	-0.18*** 1
	preference
	Prior topic	0.03	-0.02	0.07	1
	knowledge
	Prior e-learning	0.06	-0.08	0.06	0.17***	1
	knowledge
	Note: Pearson Correlation -p < 0.05 = *; p < 0.01 = **; p< 0.001 = ***

Table 3 :

 3 Analysis of cluster differences

		Cluster	Cluster	Cluster	Cluster
		1	2	3	4
		Mean	Mean	Mean	Mean	ANCOVA
	Age	33.03	31.10	33.72	31.06	F(3.663)=1.103, p=.347
	Deep strategy	3.53	3.49	3.48	3.88	F(3.663)=1.949, p=.120
	Surface strategy 2.99	2.98	2.90	3.01	F(3.663)=.194, p=.900
	Serialist
	preference	3.49	3.62	3.60	3.78	F(3.663)=2.954, p=.032
	Prior topic
	knowledge	3.22	3.27	3.35	2.97	F(3.561)=5.383, p=.001
	Prior e-learning
	knowledge	3.01	2.77	2.66	2.47	F(3.632)=2.218, p=.085
	Page visits	19.36	19.47	19.05	19.00	F(3.662)=.306, p=.821
						F(3.662)=16.088,
	Total time	374.77 460.98 349.49 514.16	p<.001


WETICE 2016 -From group collaboration to large scale social collaboration -10

Challenges at the time

  • A programming language that can be used by a Clerical worker • Software engineeringmodeling and validation • Operating Systems and databasedistribution of data, consistency and security • Measurement and Evaluation • Communication -teleconferencing • Other areapsychology, social implications 16From group collaboration to large scale social collaboration -46 • Very wide area affected • Several political decisions level • Coordination issues during the evacuation The Danube floods 16/6/2016 WETICE 2016 -From group collaboration to large scale social collaboration -47 • 2002,2005,2006,…,2014 • Very common eventcross international borders • Requires a dedicated organisation Wolfgang Rattay/Reuters) Coordination at a large scale • Combination of human and services activities • Composition of hundred of services • Duration, kind of contribution, governance • Various domains : logistic, crisis management, more complex a situation gets, for instance where you may have many organizations working collectively in order to accomplish a goal, but at the same time working independently in terms of their own interests, where you get in those in situation like that, you know it get to the point, to be so complex that it would be collaboration helps to solve large scale problems • Only very solution based ad-hoc support Large scale collaboration issues • A programming language that can be used by a Clerical worker • Software engineeringmodeling and validation • Operating Systems and databasedistribution of data, consistency and security • Measurement and Evaluation -prediction • Security, privacy and trust • WYSIWweS or What ou see is what we see • Community Processes • Concurrency Control • Other areapsychology, social implications 16/6/2016 WETICE 2016 -From group collaboration to large scale social collaboration -64


Pauline Collon-Drouaillet
email: pauline.collon@ensg.inpl-nancy.fr

Vincent Henrion

Jeanne Pellerin

An algorithm for 3D simulation of branchwork karst networks using Horton parameters and A . Application to a synthetic case

This paper presents a method to stochastically simulate 3D karstic networks and more specifically branchwork pattern cave systems. Considering that they can be compared to 3D fluvial networks, the topological classification of Strahler and the corresponding ratios of Horton are used to define three morphometric parameters. These parameters are integrated in an algorithm which computes branches hierarchically to obtain a final network organised around the main observed inlet and outlet with a branching complexity controlled by the user. Each branch corresponds to a low-cost path between two points calculated with the A graph search algorithm. Speleogenetic information on inception horizons, palaeo-water tables and fractures is accounted for by adapted definitions of the searching functions of A . The method is demonstrated on a 3D synthetic case with discrete fractures networks, inception horizons and a palaeo-water table. The simulated karsts have a realistic geometry and are geologically consistent.

Simulation of 3D karstic networks is often required to build consistent geomodels in carbonate reservoir environments for various applications: water supply management, complex carbonate petroleum reservoirs studies, civil ingeneering, etc. Genetic approaches try to reproduce the physical processes leading to karst formation [START_REF] Dreybrodt | Processes of speleogenesis: a modeling approach[END_REF][START_REF] Ford | Karst Hydrogeology and Geomorphology[END_REF]. Because of their extreme computational heaviness, they are essentially operating in 2D (e.g. [START_REF] Kaufman | Karst aquifer evolution in fractured, porous rocks[END_REF][START_REF] Kaufman | Cave development in the swabian alb, south-west germany: A numerical perspective[END_REF]. Moreover they are based on various parameters (e.g. palaeo-climate, boundary conditions, etc.) that are not always available [START_REF] Dreybrodt | Basic processes and mechanisms governing the evolution of karst. Speleogenesis and Evolution of Karst Aquifers[END_REF].

Static approaches directly simulate the result of the karstification process but to our knowledge only a few attempts have been made in this direction. [START_REF] Jaquet | Stochastic discrete model of karstic networks[END_REF] used a modified latticegas automaton for the discrete simulation of karstic networks. As it uses a random-walk technique, this method would be difficult to constrain exactly with field data. Karst networks are computed independently in several 2D horizontal layers and the addition of vertical conduits where karst were observed at surface provides a 2.5D image. The orientation of the lattice has a significant impact on the results since its segments determine the distribution of faults and fractures considered and imposed their orthogonal orientations. The different approach of [START_REF] Labourdette | Process-like modeling of flank-magin caves: from genesis to burial evolution[END_REF] focuses on flank-margin caves modelling with an object-based method. Providing realistic geometries and volumes with a limited number of parameters, the main drawback of this method is that it needs a 3D model of surveyed caves. Indeed, it relies on an iterative procedure that stops when differences in volume and shape between simulated and observed caves become small enough. It also uses a dissolution probability cube based on hypothesis specific to flank margin caves. Particularly adapted in the case of flank-margin caves, the method is not directly applicable to other karst types. Moreover, none of these two methods considers the global shape of the networks.

According to [START_REF] Palmer | Speleogenesis in carbonate rocks. Speleogenesis and Evolution of Karst Aquifer[END_REF] karst patterns can be qualitatively separated in three main families related to speleogenetical context (Fig. 1): i) branchwork patterns (curvilinear or rectilinear); ii) maze patterns (anastomotic, network, spongework); and iii) ramiform patterns. In this article, we focus on branchwork karsts and present a method to constrain their simulation by specific parameters. The global workflow, first introduced by [START_REF] Henrion | Stochastic simulation of cave systems in reservoir modeling[END_REF], consists in four main steps described in the first section. The basic idea is to compute a skeleton of the karstic network and to simulate stochastically the karst envelope around it. The specific algorithm developed to build branchwork skeletons with a control on the branching complexity is presented in the second section. It is based on a hierachical computation of elementary branches, each branch being the lowest-cost path between two points computed with the A graph search algorithm. The searching functions of A are defined to account for speleogenetic information. The last section, which can be read independantly, demonstrates the method on a 3D synthetic case with inception horizons and fractures showing the potential of the approach. Geological model building. The capacity of the geomodel to synthesize geological data and knowledge of the studied zone impacts the complete workflow: surfaces that favour karstogenesis have to be integrated at this step. Following basic principles of 3D geomodelling [START_REF] Caumon | Surface-based 3d modeling of geological structures[END_REF] ensures the consistency of the model. The petrophysical properties, permeability and porosity, can be defined indifferently with kriging or sequential gaussian simulation (e.g. [START_REF] Goovaerts | Geostatistics for natural resources evaluation[END_REF]). Discrete Fracture Networks can be simulated with the stochastic method developed by [START_REF] Macé | Caractérisation et modélisation numérique tridimensionnelle des réseaux de fractures naturelles[END_REF].

General workflow for karst simulation

Discretization of the geomodel into a graph of connectivities. The graph used here is a PipeNetwork: an unstructured connectivity graph designed to perform flow simulations [START_REF] Vitel | Méthodes de discrétisation et de changement d' échelle pour les réservoirs fracturés 3[END_REF]. It consists in a set of pipes connecting a set of nodes, which respectively correspond to the facets of the control volumes DOI: 10.1144/SP370.3 and the grid points of a reservoir simulation grid. From a geometrical point of view, it corresponds to the partial topological dual of a corner-point grid (Fig. 3). The PipeNetwork provides a unified structure for various types of geomodels: structured grids combined or not with fracture networks or unstructured grids with faults and horizons. Various properties simulated in the geomodel can be transferred on the graph (e.g. permeability) and some other may be computed during the discretization process (e.g. volumes). A specificity of the PipeNetwork is to store the properties of the media on nodes (e.g. permeability, volume), while properties concerning flow transmission are stored on pipes (e.g. transmissibility, permeability per length). Inlets and outlets can be imposed by field observation or stochastically simulated. Karst skeleton computation. The skeleton of the karst is extracted from the previous graph as preferential flow paths between inlets and oulets points. This step controls the high scale geometry of the karst. Thus, it is the key part for a process dedicated to the modeling of branchwork patterns and it is fully detailed in the next section of this paper.

Computation of realistic 3D karst envelopes. This final step relies on the object-distance simulation method (ODSIM ) proposed by [START_REF] Henrion | Odsim: An object-distance simulation method for conditioning complex natural structures[END_REF]. It computes for each point p = [p x p y p z ] T of a grid G the Euclidean distance to a geological body skeleton providing a 3D distance field D(p) (Fig. 2,4.1). This distance field is then truncated by a spatially correlated random threshold ϕ (p) which may be generated using Sequential Gaussian Simulation or other stochastic simulation method (e.g. [START_REF] Goovaerts | Geostatistics for natural resources evaluation[END_REF][START_REF] Deutsch | GSLIB: Geostatistical Software Library and User's Guide (Applied Geostatistics)[END_REF]) (Fig. 2,4.2). The resulting object is identified in the grid by a binary categorical property I B (Fig. 2,4.3) defined by

I B (p) = 1 if D(p) ≤ ϕ(p) 0 if not (1)
During this process, the extension of karst conduits is controlled by the distribution (PDF) of the threshold while the parameters of the variogram control the roughness and anistropy of karst conduits. Indeed, higher variogram ranges involve lower changes of the threshold values, providing a smoother enveloppe. If the ranges vary with the directions, this will be reflected in the geometrical evolution of karst conduits that will be smoother along the mean directions. An iterative Gibbs sampler [START_REF] Geman | Stochastic relaxation, gibbs distribution and the bayesian restoration of images[END_REF] with inequality constraints allows to condition the threshold simulation to well data while preserving its spatial structure and histogram [START_REF] Henrion | Odsim: An object-distance simulation method for conditioning complex natural structures[END_REF].

Methodology for branchwork karst pattern generation

An algorithm to control the branching complexity of karst networks

Branchwork patterns have a typical topology, characterized by a hierarchical organization excluding cycles (only one path between two points) . A solution to reproduce this hierarchy is to extract a main path, and compute secondary paths connected to it [START_REF] Bonneau | Genetic-like modeling of karst network[END_REF]. But none of the previously developed techniques integrates a possibility to control the branching complexity of the networks. Developed for hydrological applications, the topological classification of [START_REF] Strahler | Hypsometric (area-altitude) analysis of erosional topography[END_REF] can be applied on any directed graph tree. Each segment of the tree is assigned an order i with the followings rules (Fig. 4):

• each segment with no parent (i.e. with no affluent for a stream) has an order equal to 1;

• a segment formed from the confluence of two segments of order i, has an order equal to i + 1;

• a segment formed from the confluence of two segments of order m and n, has an order equal to max(m, n).

The Horton-Strahler number of a tree is defined as the order of its outlet. It is denoted K o in this work. The branching complexity of a network can be described by the Horton bifurcation ratio R B , based on the law of stream numbers [START_REF] Horton | Erosional development of streams and their drainage basins; hydrophysical approach to quantitative morphology[END_REF] which states that the ratio

N Ki N Ki+1
where N Ki is the number of paths of order i, converges to a constant when order increases. Moreover, the Horton law of stream lengths states that a geometric relationship exists between the cumulated length of streams of a given order L i and the corresponding order i, i.e. the ratio

L i L i+1 converges to a constant called the Length Ratio R L .
From a geometrical point of view, a branchwork pattern is an oriented graph tree. So, Strahler classification can be applied to it. The geostatistical and fractal studies of length caves made by [START_REF] Curl | Fractal dimensions and geometries of caves[END_REF] demonstrate that the lengths of caves in a given region and the size of modular elements constituting them are distributed hyperbolically. This indicates that a self-similarity appears in these complex systems. Despite the fact that Horton laws on stream numbers and stream lengths have not been proved for karstic systems, the Horton ratios may help to reproduce this self-similarity. Thus, the three parameters, K o , R B and R L , are integrated in a new algorithm to simulate branchwork karsts controlled by the user.

The algorithm (Fig. 5) first computes a main path between the given input and output. Then, for each order i from (K o -1) to 1, the following three steps are performed: 1. Compute 1 path connected to each path of order 1 to increase its order. This is done using a length smooth constraint described below.

Update Horton orders;

3. Generate the (N Ki -2N Ki+1 ) remaining paths with output points randomly chosen on paths of order > 1 guaranteeing that Horton orders i are preserved.

The length smooth constraint enforces the use of the R L ratio. Considering l i as the average length of a segment of order i and L as the curvilinear length of the main path linking inlet and outlet, we have the following equations:

     L i = N i × l i L = Ko i=1 l i (2)
Thus:

l i l i+1 = R L R B = r (3)
which leads to:

l i = r Ko-i × l Ko (4)
and:

l Ko = L Ko-1 j=0 r j (5)
To perform the first step of the previous algorithm for a current order i, we impose the output point p out i of the new path to be located at a distance l i+1 from the downstream segment extremity. Then, the new input point p in i is randomly chosen on the half upper sphere of radius l = rand [0.5

;1] * i-1 j=1 l j
where rand [0.5;1] is a random number chosen between 0.5 and 1. As karsts form from surface infiltration, the input point is vertically projected on the upper part of the PipeNetwork. The new pair of points [p in i ; p out i ] is then used to compute the connected path. The third step is quite similar of the first one, except that the output point is randomly chosen on an existing path of order 1. As the computed paths between two points are not straight lines (see the detailed method below) and as the path extraction ends when crossing an existing segment, the length of the resulting path is different from the used radius l (often superior to l, explaining the use of the random multiplier).

Thus, the R L ratio guides the simulation but is not strictly honoured justifying the notion of smooth constraint. The R B ratio is more constraining but the use of non-integers permit to obtain network with different values. On the contrary, the Horton-Strahler number K o is always strictly respected and can be considered as a hard constraint.

Using A for single path computation

A algorithm allows to easily compute single karst branches honouring given input and output points. These points might be actual inlet and/or outlet of the network or location computing by the branchwork karst simulation algorithm described in the previous section. A is a graph search algorithm that aims at finding the least cost path between two given nodes [START_REF] Hart | A formal basis for the heuristic determination of minimum cost paths in graphs[END_REF]. It uses a best-first search, i.e. it first explores the most promising node chosen according to a specified rule, and derives from Edsger Dijkstra's 1959 algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF]. A better performance (with respect to time) is obtained thanks to the use of a heuristic function f (x). f is the sum of (1) a cost function g(x), which is the cumulated cost from the starting node to the current node, and (2) an admissible heuristic estimate h(x) of the distance to the goal. Two rules have to be respected:

• The cost has to be strictly positive: g(x) > 0;

• The heuristic estimate has to be admissible, i.e. it must not overestimate the distance to the goal: h(x) < g(x, goal), where g(x, goal) is the minimal cost from x to goal.

To use A for karst skeleton computation, these two functions must be defined consistently. Despite the complexity of the phenomenons involved, speleologists agree that knowing two connected points, karstic conduits develop preferentially along paths with high hydraulic conductivity and short length (Ford & Williams, 2007, chap. 7). Thus, we define the cost on a pipe as a function of the inverse of the permeability per length K Lij (Eq. 6). The permeability per length is a weighted average permeability calculated on a pipe linking two nodes i and j using the node hydraulic conductivities and volumes DOI: 10.1144/SP370.3 and divided by the pipe length (Eq. 7). The resulting cost, proportional to 1 K Lij , is homogeneous to a time and thus it can be summed and is independent of mesh resolution.

cost ij = 1 K Lij × grav ij (6) K Lij = 1 d ij × k i × vol i + k j × vol j vol i + vol j (7)
with:

• k i the permeability at point i;

• vol i the volume of the cell represented by node i;

• d ij the distance between the points i and j.

The gravity grav ij is included in the cost computation has a multiplier coefficient (Eq. 6) to avoid vertically oscillating paths (Eq. 8)

grav ij =    1 if z ij ≥ 0 1 - z ij d ij if z ij < 0 (8)
The admissible heuristic is a function of the distance from the current node to the output node (Eq. 9). Unit homogeneity and A requirements are guaranteed by the use of a multiplier coefficient equal to the maximal cost M cp encountered on the PipeNetwork multiplied by the length of this maximal cost pipe Lmp (Eq. 9):

heur j = d j,output max (K L × d) (9)
where d j,output is the distance between the point j and the output. With these definitions of the cost and the heuristic, the A algorithm extracts paths between two points of a PipeNetwork using hydraulic conductivity information. Speleogenetical concepts and geological information might be included at the geomodel building step and will then be taken into account when the skeleton is computed. Different kind of surfaces have been identified as preferential surfaces for karst development: inception horizons are the restricted numbers of bedding planes within the limestone series along which a karstic network tends to develop [START_REF] Lowe | The origin of limestone caverns: an inception horizon hypothesis[END_REF], palaeo-water tables and fractures are also proved to favour karst development [START_REF] Dreybrodt | Basic processes and mechanisms governing the evolution of karst. Speleogenesis and Evolution of Karst Aquifers[END_REF]. For inception horizons and palaeo-water table, an adapted building of the geomodel using a grid conformable to the considered surfaces with a local mesh refinement along these levels allows their integration in the PipeNetwork. Giving these surfaces higher values of hydraulic conductivity promotes the simulation of paths along them. The object-based method developed by [START_REF] Macé | Caractérisation et modélisation numérique tridimensionnelle des réseaux de fractures naturelles[END_REF] stochastically simulates a discrete fracture networks (DFN) from data on their orientation, extension and density. These fractures can be jointly discretized with the geomodel [START_REF] Vitel | Méthodes de discrétisation et de changement d' échelle pour les réservoirs fracturés 3[END_REF] allowing to generate karst skeletons strongly influenced by their presence.

Application on a synthetic case

The method is applied on a 3D synthetic case. The fractured geological system is made of a succession of three stratigraphic units, from base to top: one layer of shale overhanged by two layers of limestone. Two inception horizons separate these units and a palaeo-water table is located inside the bottom limestone unit (Fig. 6a). Two fracture families are considered. All these surfaces favour karstogenesis.

A stratigraphic grid (cell numbers: 30 × 37 × 21) is built from these data, with thinner cells (2m high) centered on the inception horizons and the palaeo-water table (Fig. 6b). The hydraulic conductivities and porosities of the different units (Table 1) are simulated using an unconditional sequential gaussian simulation [START_REF] Goovaerts | Geostatistics for natural resources evaluation[END_REF] with a uniform law and a spherical variogram (with ranges : 200m, 200m and 50m). The two Discrete Fracture Networks (DFN) are simulated (Fig. 6a) according to the workflow proposed by [START_REF] Macé | 3d fratures characterization based on geomechanics and geologic data uncertainties[END_REF], with a higher density of fracturation along the fold axis. Their properties, following triangular laws, are indicated in Table 2. The model is discretized into a PipeNetwork composed of 50605 nodes, including 27300 nodes for the fractures (Fig. 7). The permeability per length values range from 1.7 10 -11 s -1 in belower shale to around 10 -2 s -1 in short pipes of fractures, inception horizons and palaeo-water table. A network simulation is performed between inlet and outlet (Fig. 8) with the following values: K o = 3, R B = 2.8 and R L = 3.5. The obtained branchwork skeleton honours its input parameters K o and R B and the skeleton paths are located preferentially along the fractures, the inception horizons and the water table due to their higher permeability (Fig. 8). the skeleton paths are located preferentially along the fractures; (c) Vertical cross-section: the paths are also preferentially located around the inception horizons and the water table due to their higher permeability.

To illustrate the influence of the three morphometric parameters several simulations have been performed, each time with the same random seed for the search of input points (Fig. 9). Consistently with their definitions, the K o value controls the hierarchical organisation i.e. the branching complexity of the network, and imposes an order to the outlet of the karst. Increasing the bifurcation ratio R B produces denser networks without changing the global order, i.e. for the same K o value it generates an higher number of paths. Finally, the length ratio R L influences the lengths of secondary paths. (c) An higher value of R L involves higher lengths of secondary paths.

As presented in the global workflow, the object-distance simulation method (ODSIM ) can be applied on the resulted skeletons to generate stochatically several 3D envelopes of the network [START_REF] Henrion | Odsim: An object-distance simulation method for conditioning complex natural structures[END_REF]. The Fig. 10 illustrates this method on the reference skeleton computed on the synthetic case. In karstic systems the geometry of the voids is perceptible at a local scale (dimensions from meters to ten or so meters) whereas the previous studied skeletons was computed at a regional scale (kilometer or so). The thresholds have been simulated using a triangular distribution (PDF) (minimum = 1 , mode = 2, maximum = 15) and a gaussian variogram with an azimuth = 60, a dip = 0, ranges = [30 25 15], no nugget effect and a cumulative sill = 1. The distance field has been then truncated by these thresholds to produce three binary categorical properties. To make easiest the visualization of the results, envelope surfaces have been extracted from grid isovalues.

Figure 1 :

 1 Figure 1: Cave pattern classification after Palmer (2003): "Common patterns of solutional caves. Dot sizes show the relative abundance of cave types in each of the listed categories.Single-passage caves are rudimentary or fragmentary versions of those shown here."

Fig. 2

 2 Fig. 2 summarizes the four main steps of the global workflow.Geological model building. The capacity of the geomodel to synthesize geological data and knowledge of the studied zone impacts the complete workflow: surfaces that favour karstogenesis have to be integrated at this step. Following basic principles of 3D geomodelling[START_REF] Caumon | Surface-based 3d modeling of geological structures[END_REF] ensures the consistency of the model. The petrophysical properties, permeability and porosity, can be defined indifferently with kriging or sequential gaussian simulation (e.g.[START_REF] Goovaerts | Geostatistics for natural resources evaluation[END_REF]). Discrete Fracture Networks can be simulated with the stochastic method developed by[START_REF] Macé | Caractérisation et modélisation numérique tridimensionnelle des réseaux de fractures naturelles[END_REF].Discretization of the geomodel into a graph of connectivities. The graph used here is a PipeNetwork: an unstructured connectivity graph designed to perform flow simulations[START_REF] Vitel | Méthodes de discrétisation et de changement d' échelle pour les réservoirs fracturés 3[END_REF]. It consists in a set of pipes connecting a set of nodes, which respectively correspond to the facets of the control volumes

Figure 2 :

 2 Figure 2: General workflow for stochastic 3D karst simulation

Figure 3 :

 3 Figure 3: PipeNetwork as partial topological dual of a block-centered corner-point grid (Blue cubes: nodes, orange lines: pipes) (modified from Vitel (2007))

Figure 4 :

 4 Figure 4: Example of Strahler classification on a hydrological network (South France) where the Horton-Strahler number is equal to 4

Figure 5 :

 5 Figure 5: The different steps of the branchwork network algorithm. The initialisation consists in the extraction of a main path linking inlet and outlet. Then, for each order i from (K o -1) to 1, the step 1 computes 1 path connected to each path of order 1, the second step updates Horton orders and the third step generates the remaining paths on segments of order > 1 to honour the bifurcation ratio R B . The input points definition in step 1 and 3 and the output points choice in step 1 are guided by the values of the length ratio R B

Figure 6 :

 6 Figure 6: 3D Geological synthetic model of the area in which karstic network is generated: (a) The three surfaces favouring karstogenesis and the two discrete fracture networks; (b) The corresponding stratigraphic grid with simulated hydraulic property values.

Figure 7 :

 7 Figure 7: PipeNetwork resulting from the joined discretization of the stratigraphic grid and the two DFN (c). Preferential surfaces for karst development, (a) fractures , (b)inception horizons and palaeo-water table have a higher permeability per length (orange) than the layers.

Figure 8 :

 8 Figure 8: Branchwork skeleton obtained with K o = 3, R B = 2.8 and R L = 3.5 and given inlet and outlet. (a) The branching connectivity respects the input parameters; (b) Top view:the skeleton paths are located preferentially along the fractures; (c) Vertical cross-section: the paths are also preferentially located around the inception horizons and the water table due to their higher permeability.

Figure 9 :

 9 Figure 9: Branchwork skeletons obtained by changing the values of the three morphometric parameters K o , R B and R L . (a) The K o value controls the hierarchical organisation i.e. the branching complexity; (b) The global number of paths is increasing with the R B parameter;(c) An higher value of R L involves higher lengths of secondary paths.

Figure 10 :

 10 Figure 10: Application of the ODSIM method to the reference skeleton.

Table 1 :

 1 Stratigraphic grid specifications

	Stratigraphic unit	Number of	Mean hydraulic	Mean porosity Mean thickness
		layers	conductivity (m s -1 )	(%)	(m)
	limestone 2	5	5.10 -5	20%	32.5
	inception horizon 2	1	1.10 -3	24%	2
	limestone 1	4	4.10 -5	19%	35
	water level	1	1.10 -3	24%	2
	limestone 1	5	4.10 -5	19%	50
	inception horizon 1	1	1.10 -3	24%	2
	shale	5	1.10 -8	7.5%	80

Table 2 :

 2 Discrete Fracture Networks properties

	DFN	Hydraulic	aperture	Dip( o )	Dir ( o )	Length (m)	Width(m)
		cond. (m s -1 )	(m)	min-mode-max min-mode-max min-mode-max min-mode-max
	1	1.2 10 -3	0.003	85-90-100	85-90-100	150-210-250	70-100-120
	2	0.8 10 -3	0.002	75-85-100	120-130-135	160-230-260	80-120-140

DOI: 10.1144/SP370.3

Conclusions and perpectives

The developed methodology generates branchwork karstic networks with a user control on branching complexity and gives promising results. However, the choice of using Horton-Strahler parameters could be discussed. Indeed these parameters have been proven relevant in the case of fluvial networks but not yet in the case of natural karstic systems. The main differences are that karst are not organised along a unique horizon, that often some multiple interconnections appear, etc. A preliminary work is going on to test the relevancy of the Strahler orders on natural karsts. The few multiple interconnections could be reproduced by additional path computations. However, a step of formalism and automation is required to obtain an effective tool.

Further work will aim at providing tools to simulate the other karst patterns. The network maze is quite easy to simulate by the direct application of the ODSIM method on an adequate selection of DFN fractures but improvements can be done considering their automation and calibration by the user. Anastomotic mazes, spongework mazes and ramiform patterns require specific developments to be deliberately simulated.

Regarding the karst envelope, the ODSIM method generates various shapes but could still be improved to integrate field data like seismic information, a library of natural karstic shapes and their geological environment.

We would like to thank the industrial and academic members of the Gocad Consortium, ASGA, for their support, Paradigm Geophysical for providing the Gocad Software and API, and the French National Scientific Research Center CNRS-CRPG for their support.