Loading...
Please wait, while we are loading the content...
Similar Documents
Fifth Workshop on Software Quality Analysis, Monitoring, Improvement, and Applications
| Content Provider | Semantic Scholar |
|---|---|
| Author | Budimac, Zoran Horv'ath, Zolt'an Kozsik, Tamás |
| Copyright Year | 2013 |
| Abstract | ion. Therefore, the aim of this paper is to investigate existing GCE metrics as metrics reflecting cohesion of software modules. The rest of the paper is structured as follows. Related work is presented in Section 2. Graph clustering evaluation metrics explored in this work as software metrics are defined in the next section of the paper. Section 4 explains how GCE metrics can be applied to graph representation of software systems. Theoretical analysis of GCE metrics as software metrics is given in Section 5. The last section concludes the paper and presents research questions for our future work. 2. RELATED WORK Cohesion of a software module reflects how strongly related are the elements of the module. Perhaps the widest known cohesion metric in software engineering is LCOM (Lack of cohesion in methods) introduced by Chidamber and Kemerer [1994] in their object-oriented metrics suite. As the name of the metric suggests, LCOM is an inverse cohesion metric: a low value of LCOM indicates high cohesion of a class and vice versa. LCOM is based on a specific coupling between methods: two methods in a class are considered as data coupled if they use at least one common class attribute. Then LCOM is the number of non-coupled methods (P) reduced by the number of coupled methods (Q) if P > Q, or zero otherwise. From the definition of the LCOM it can be seen that this metric does not take external dependencies into account nor method invocations (another form of method coupling). The approach of Hitz and Montazeri [1995] to measure cohesion of software entities followed the research of Chidamber and Kemerer. For a class we can construct graph G whose nodes are methods defined in the class, and two methods are connected by an undirected link if they are data coupled. LCOM of Hitz and Montazeri is the number of connected components in G. The same authors also proposed another variant of the same metric where G includes method calls relations. Finally, they introduced a metric called connectivity which quantifies how much G is far from being completely connected. Bieman and Kang [1995] introduced two cohesion metrics called tight class cohesion (TCC) and loose class cohesion (LCC). The basic element in their metrics is again a graph representing a class that encompasses methods of the class. TCC/LCC is the density (the actual number of links divided by the maximal number of links) of a TCC/LCC graph. Two methods are connected in TCC graph if they both access the same variable or there is a direct call between them. LCC graph is an extension of TCC graph that includes indirect method calls. Lee et al. [1995] introduced a class cohesion metric based on information flow. The basic idea is that the strength of call coupling between invoking and invoked method is determined by the number of parameters of invoked method: the more information passed through formal parameters, the stronger call coupling between methods. Then, the cohesion of a method is defined as the number of calls to other methods multiplied by the number of formal parameters. Finally, the cohesion of a class is the sum of cohesion of its methods. From the review of widely used software engineering cohesion metrics it can be concluded that the cohesiveness of a software entity is estimated in isolation. In other words, those metrics rely only on internal dependencies, while external dependencies, dependencies reflecting coupling between software modules, are not taken into account. However, external dependencies can be also important when estimating cohesiveness of software modules. Firstly, a module that has much more external than internal dependencies hardly can be considered as strongly cohesive regardless of the density or the connectedness of its internal parts. Secondly, having two modules that have the same degree of internal density the one with the smaller number of external dependencies can be considered as more cohesive compared to the other. Graph clustering evaluation metrics as software metrics • 11:83 3. GRAPH CLUSTERING EVALUATION METRICS Let G = (V,E) be a directed graph where V is the set of nodes and E set of links. Let C denote a cluster in V (C ⊆ V ), and let c be a node from C. An intra-cluster link emanating from c connects c to another node from C, while an inter-cluster link emanating from c connects c to a node that does not belong to C. Intra-cluster out-degree of node c is the number of intra-cluster links emanating from c, while inter-cluster out-degree of node c is the number of inter-cluster links emanating from c. The most common formulation of the graph partitioning problem asks for a division of the set of nodes into balanced, disjoint subsets of nodes such that the edge cut (links connecting nodes from different clusters) is minimized. Therefore, the basic graph clustering evaluation (GCE) metrics are based on the size of the edge cut. Let EC denote the size of the cut (the number of inter-cluster links) for cluster C, EC = | {(x, y)} : x ∈ C, y 6∈ C | = ∑ x∈C inter-cluster out-degree(x), IC the number of intra-cluster links for C, IC = | {(x, y)} : x ∈ C, y ∈ C | = ∑ x∈C intra-cluster out-degree(x), NC the number of nodes in C, and N the number of nodes in the graph. Then cut based GCE metrics, conductance, expansion and cut-ratio, are defined as follows [Leskovec et al. 2010]: (1) Conductance of cluster C is the size of the cut normalized by the total number of links incident to nodes contained in C, Conductance(C) = EC EC + IC . (2) Expansion of cluster C is the size of the cut divided by the total number of nodes in C, Expansion(C) = EC NC . (3) Cut-ratio of cluster C is the size of the cut divided by the size of maximal cut, Cut-ratio(C) = EC NC(N −NC) . Probably the oldest definition of graph cluster originate from circuit theory which is furtherly adopted in social network analysis. Namely, Luccio and Sami [1969] introduced the notion of LS-set that is also known as Raddichi strong community in social network analysis [Radicchi et al. 2004]. For directed graphs, an LS-set is a subgraph such that the intra-cluster out-degree of each node in the set is higher than its inter-cluster out-degree. The nodes having zero out-degree are not taken into account when determining whether the cluster is Radicchi strong. If the number of intra-cluster links is higher than the number of inter-cluster links then the subgraph is considered as Radicchi weak cluster. Each Radicchi strong cluster is at the same time Radicchi weak cluster, while the converse is not generally true. If a cluster is Radicchi weak or strong then its conductance is smaller than 0.5. The difference between the number of intraand inter-cluster links inspired ODF (out-degree fraction) family of cluster quality measures [Leskovec et al. 2010]: (1) Maximum-ODF of cluster C is the maximum fraction of inter-cluster links of a node observed in the cluster, Maximum-ODF(C) = maxc∈C | {(c, d)} : d 6∈ C | Dout(c) , 11:84 • Miloš Savić, Mirjana Ivanović where Dout(c) stands for out-degree of node c. (2) Average-ODF of cluster C is the average fraction of inter-cluster links of nodes from C, |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://ceur-ws.org/Vol-1266/SQAMIA2014Proceedings.pdf |
| Alternate Webpage(s) | http://ceur-ws.org/Vol-1938/sqamia2017-preface.pdf |
| Alternate Webpage(s) | http://ceur-ws.org/Vol-1053/sqamia2013preface.pdf |
| Alternate Webpage(s) | http://ceur-ws.org/Vol-2217/sqamia-preface.pdf |
| Alternate Webpage(s) | http://ceur-ws.org/Vol-1375/SQAMIA2015_Preface.pdf |
| Alternate Webpage(s) | http://ceur-ws.org/Vol-1266/SQAMIA2014_Preface.pdf |
| Alternate Webpage(s) | http://sqamia16.elte.hu/downloads/sqamia2016-proc.pdf |
| Alternate Webpage(s) | http://ceur-ws.org/Vol-1375/SQAMIA2015_Proceedings.pdf |
| Alternate Webpage(s) | http://ceur-ws.org/Vol-1677/sqamia2016-preface.pdf |
| Alternate Webpage(s) | http://ceur-ws.org/Vol-1053/SQAMIA2013FullProceedings.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
