Optimizing Community Detection - The Supercomputing Challenge

Optimizing Community Detection 1 1.0 Executive Summary 3 2.0 Problem Statement 4 3.0 Background Information 5 4.0 Procedural Overview 7 4.1 Network Setup 4.2 Visualization 4.3 Algorithm Setup 5.0 Results 12 5.1 Efficiency 5.2 Accuracy 6.0 Conclusions 20 7.0 Significant Original Achievement 20 8.0 Future Work 21 9.0 Appendix 22 9.1 Acknowledgements 9.2 Works Cited 9.3 Data 9.4 Program Code 3 1.0 Executive Summary Earth in itself is a large-scale network. It is a system connecting and overlapping the individual networks of daily life from communication

systems to biological systems. In science, these networks are used to express connections between different nodes through arcs and paths. To understand and apply these structures, decomposition is of utmost importance. Decomposition allows for the breakdown of complex problems into smaller, more manageable ones, which adds an element of simplicity to the problem. With networks, this process results in the formation of communities which signifies the connectivity between distinct groups of nodes. This project optimizes decomposition by finding the most efficient optimization method for partitioning of networks with maximum modularity. Java was used to implement and compare two main techniques: Girvan-Newman Algorithm and Ant Colony Optimization (ACO). Both algorithms were also tested with a variety of modifications. A Hierarchical Girvan- Newman Algorithm was implemented. Combinations between the ACO and Probability Summation as well as between the ACO and Power Iteration was used. In discovering the most efficient optimization method, this project could be applied to most networks which naturally divide into communities or modules. Examples of such systems include transportation, manufacturing, communication, biological, and citation networks. 4 2.0 Problem Statement What is the most efficient optimization method to maximize the modularity of a partitioned network? The purpose of this project is to find an efficient and accurate method of maximizing the modularity of a partitioned network. Finding the maximum modularity of a network is extremely useful for any real-life situation the network may represent. Identifying groups makes it possible for someone to lay efficient connections or place the nodes in optimal locations. 5 3.0 Background Information Networks are systems where sets of nodes are connected through links or edges. These systems appear in everyday life in the form of power grids, biological networks and pathways, metabolic networks, the Internet, social networks, and much more. Through the partitioning of networks in this project, systems are rearranged into communities allowing for further practical application of networks. For example, partitions within social networks can be used to represent social groupings based on common traits or interests. Citation network communities reveal related papers on certain topics, while the communities formed in the World Wide Web represent related sites. In economic networks, partitioning can reveal elements of vertical disintegration and groups of similar businesses. In a general sense, these partitions expose information which would be impossible to see in the big picture. With better understanding of networks through partitioning, correlations between network topology and function...

Website: www.challenge.nm.org | Filesize: -
No of Page(s): 80
Download Optimizing Community Detection - The Supercomputing Challenge.pdf