Exploring community structure of software Call Graph and its applications in class cohesion measurementby Yu Qu, Xiaohong Guan, Qinghua Zheng, Ting Liu, Lidan Wang, Yuqiao Hou, Zijiang Yang

Journal of Systems and Software

About

Year
2015
DOI
10.1016/j.jss.2015.06.015
Subject
Hardware and Architecture / Software / Information Systems

Similar

Notes from the societies

Authors:
Society of Community Medicine
1985

LXVIII. The Abbot and Convent of Woburn to the King

Authors:
Thabbot and convent of Woburn
1843

Regulatory approaches to the control of environmental mutagens and carcinogens

Authors:
Members and Consultant of Committee
1983

Graph classes with structured neighborhoods and algorithmic applications

Authors:
Rémy Belmonte, Martin Vatshelle
2013

Measuring class cohesion based on dependence analysis

Authors:
Zhen-Qiang Chen, Bao-Wen Xu, Yu-Ming Zhou
2004

Text

Accepted Manuscript

Exploring Community Structure of Software Call Graph and its

Applications in Class Cohesion Measurement

Yu Qu, Xiaohong Guan, Qinghua Zheng, Ting Liu, Lidan Wang,

Yuqiao Hou, Zijiang Yang

PII: S0164-1212(15)00125-9

DOI: 10.1016/j.jss.2015.06.015

Reference: JSS 9528

To appear in: The Journal of Systems & Software

Received date: 20 November 2014

Revised date: 16 April 2015

Accepted date: 7 June 2015

Please cite this article as: Yu Qu, Xiaohong Guan, Qinghua Zheng, Ting Liu, Lidan Wang, Yuqiao Hou,

Zijiang Yang, Exploring Community Structure of Software Call Graph and its Applications in Class

Cohesion Measurement, The Journal of Systems & Software (2015), doi: 10.1016/j.jss.2015.06.015

This is a PDF file of an unedited manuscript that has been accepted for publication. As a service to our customers we are providing this early version of the manuscript. The manuscript will undergo copyediting, typesetting, and review of the resulting proof before it is published in its final form. Please note that during the production process errors may be discovered which could affect the content, and all legal disclaimers that apply to the journal pertain.

ACCEPTED MANUSCRIPT

AC

CE

PT

ED

M

AN

US

CR

IP

T

Highlights • We show that software static Call Graphs exhibit significant community structures. • We propose two new class cohesion metrics based on community structures. • The new metrics provide new and useful measurement of software class cohesion. • The new metrics perform better than existing metrics in software fault prediction. 1

ACCEPTED MANUSCRIPT

AC

CE

PT

ED

M

AN

US

CR

IP

T

Exploring Community Structure of Software Call Graph and its Applications in Class

Cohesion Measurement

Yu Qua, Xiaohong Guana,∗, Qinghua Zhenga, Ting Liua, Lidan Wanga, Yuqiao Houa, Zijiang Yangb aMinistry of Education Key Lab for Intelligent Network and Network Security, Xi’an Jiaotong University, Xi’an, Shaanxi, China 710049 bDepartment of Computer Science, Western Michigan University, Kalamazoo, MI, USA 48167

Abstract

Many complex networked systems exhibit natural divisions of network nodes. Each division, or community, is a densely connected subgroup. Such community structure not only helps comprehension but also finds wide applications in complex systems. Software networks, e.g., Class Dependency Networks, are such networks with community structures, but their characteristics at the function or method call granularity have not been investigated, which are useful for evaluating and improving software intra-class structure.

Moreover, existing proposed applications of software community structure have not been directly compared or combined with existing software engineering practices. Comparison with baseline practices is needed to convince practitioners to adopt the proposed approaches. In this paper, we show that networks formed by software methods and their calls exhibit relatively significant community structures. Based on our findings we propose two new class cohesion metrics to measure the cohesiveness of object-oriented programs. Our experiment on 10 large open-source Java programs validate the existence of community structures and the derived metrics give additional and useful measurement of class cohesion. As an application we show that the new metrics are able to predict software faults more effectively than existing metrics.

Keywords: Software cohesiveness measurement, Class cohesion metrics, Complex network analysis, Community structure 1. Introduction

Many natural and man-made complex networked systems, including metabolic networks, computer networks and social networks, exhibit divisions or clusters of network nodes (Flake et al., 2000; Girvan and Newman, 2002; Palla et al., 2005; Fortunato, 2010; Mucha et al., 2010). Each division, or community (Girvan and Newman, 2002), is a densely connected and highly correlated subgroup. Such community structure not only helps comprehension but also finds wide applications in complex systems. For example, researchers in Biology and

Bioinformatics have applied community detection algorithms to identifying functional groups of proteins in Protein-Protein

Interaction networks (Dunn et al., 2005; Jonsson et al., 2006).

For online auction sites such as ebay.com, community structure is used to improve the effectiveness of the recommendation systems (Jin et al., 2007; Reichardt and Bornholdt, 2007). A survey on the applications of community detection algorithms can be found in Fortunato (2010).

There are also research efforts to investigate community structures in software, a very complex system (Pan et al., 2011; ˇSubelj and Bajec, 2011, 2012; Concas et al., 2013; ˇSubelj et al., ∗Corresponding author.

Email addresses: yqu@sei.xjtu.edu.cn (Yu Qu), xhguan@sei.xjtu.edu.cn (Xiaohong Guan), qhzheng@mail.xjtu.edu.cn (Qinghua Zheng), tliu@sei.xjtu.edu.cn (Ting Liu), lidanwang@stu.xjtu.edu.cn (Lidan Wang), yqhou@sei.xjtu.edu.cn (Yuqiao Hou), zijiang.yang@wmich.edu (Zijiang Yang)

Figure 1: Community structure of jEdit with 5,979 nodes and 34 communities, detected by Louvain algorithm (Blondel et al., 2008). 2014). Most of them reported a significant community structure of a certain type of software network such as Class Dependency

Networks ( ˇSubelj and Bajec, 2011). Some pioneering applications of software community structure are proposed (for more details, please refer to Section 2). However, there are still some unsolved problems.

Firstly, most of the measurements are performed on the network of classes. Little results are reported on the granularity of software method or function call, i.e., method/function Call

Graphs (Graham et al., 1982). Such investigation is necessary from both theoretical and practical perspectives. In addition, measurements of the network of classes cannot be used in intraclass structure, which limits their applications in software quality evaluation and improvement.

Preprint submitted to Journal of Systems and Software June 13, 2015