tailieunhanh - Báo cáo sinh học: "Module detection in complex networks using integer optimisation"

Tuyển tập các báo cáo nghiên cứu về sinh học được đăng trên tạp chí y học Molecular Biology cung cấp cho các bạn kiến thức về ngành sinh học đề tài: Module detection in complex networks using integer optimisation. | Xu et al. Algorithms for Molecular Biology 2010 5 36 http content 5 1 36 AMR ALGORITHMS FOR MOLECULAR BIOLOGY RESEARCH Open Access Module detection in complex networks using integer optimisation Gang Xu1 Laura Bennett2 Lazaros G Papageorgiou1 Sophia Tsoka2 Abstract Background The detection of modules or community structure is widely used to reveal the underlying properties of complex networks in biology as well as physical and social sciences. Since the adoption of modularity as a measure of network topological properties several methodologies for the discovery of community structure based on modularity maximisation have been developed. However satisfactory partitions of large graphs with modest computational resources are particularly challenging due to the NP-hard nature of the related optimisation problem. Furthermore it has been suggested that optimising the modularity metric can reach a resolution limit whereby the algorithm fails to detect smaller communities than a specific size in large networks. Results We present a novel solution approach to identify community structure in large complex networks and address resolution limitations in module detection. The proposed algorithm employs modularity to express network community structure and it is based on mixed integer optimisation models. The solution procedure is extended through an iterative procedure to diminish effects that tend to agglomerate smaller modules resolution limitations . Conclusions A comprehensive comparative analysis of methodologies for module detection based on modularity maximisation shows that our approach outperforms previously reported methods. Furthermore in contrast to previous reports we propose a strategy to handle resolution limitations in modularity maximisation. Overall we illustrate ways to improve existing methodologies for community structure identification so as to increase its efficiency and applicability. Background Networks - . groups of entities nodes or