# Mining Domain-Specific Design Patterns: A Case Study +
## 3 The Methodology
### Phase 2: Mining the Candidate Domain-Specific Design Patterns
#### 3.2.1 Mining the Recurrent Patterns at Hypertext Level  
To locate the recurrent patterns (their core specifications along with their starting and termination variants) occurring among the set of conceptual models, we have reduced the problem of their identification into the domain of graph mining, and particularly to the subgraph isomorphism problem. The latter is synopsized in its general form into finding whether the isomorphic image of a subgraph exists in a larger graph. An example of an isomorphic image of a subgraph is depicted in Figure 3. The subgraph in Figure 3b is isomorphic to the subgraph in Figure 3a. As we can see, despite the different configuration of nodes in the two subgraphs, the edges connecting the nodes of the same color remain the same. The table in Figure 3c contains some sequences of the nodes that are connected in the subgraphs of Figure 3a,b. For example, a sequence can start from node S, from which one can navigate to node article category list (ACL) and then navigate to node A, and so on. By observing the node sequences, one can notice that they can actually reveal the recurrent patterns occurring within a graph, both their core specifications and their starting and termination variants. Clearly, the identification of the isomorphic subgraphs within a graph is an alternative way to obtain the identification of the incorporated recurrent patterns. Based on this, we attempt to identify the recurrent patterns lying in the set of the recovered conceptual models, by locating all the isomorphic subgraphs within their equivalent graph representations. To achieve this, we employ a graph mining algorithm, namely gSpan [20], which identifies the occurrences of all the recurrent isomorphic subgraph patterns within the conceptual model graphs. More specifically, gSpan addresses the problem of frequent subgraph mining. Due to space limitations, we cannot provide a detailed description of how the gSpan works, but we present an explanatory overview. Intuitively, gSpan traverses the set G of the conceptual model graphs and finds all the smaller subgraphs g in G that occur frequently. A subgraph g is frequent if its occurrence frequency in G, denoted as support(g), is no less than a minimum support threshold (minSup). In a more formal definition, the problem of frequent subgraph mining is to find any subgraph g into G so that support(g) \(\geq\) minSup. When looking for the occurrences of a subgraph in G, the algorithm encounters except for its identical occurrences, its isomorphic images, too. In this way, the conceptual model graphs are analyzed in terms of the frequent subgraphs (representing recurrent patterns) occurring among them. To apply the gSpan algorithm on the set of conceptual model graphs, we have used the Parsemis project Parsemis (2016), which supports an implementation of the gSpan algorithm within a graphical environment for visualizing the identified frequent subgraphs. An example can be found in Figure 4 which presents an identified subgraph pattern representing one of the most typical ways of browsing large hierarchical content structures, i.e., the hierarchy of categories and subcategories of an information object, used in the designs of many educational websites. The pattern consists of a composition of Joomla! hypertext design elements (components and modules) involving four different pages of an educational website. More specifically, it consists of an article page publishing content about an information object, from which users can navigate to a second page which is based on the ACL component and allows users to quickly scan a list of information items. By selecting a certain list item, users can navigate to a third page of the same component type (ACL), allowing them to have access to a second list of information items. Finally, by selecting a specific list item, users can have access to an article page presenting content about the selected list item. Figure 4: A frequent subgraph detected in the conceptual models of educational websites.