检索结果-内蒙古大学图书馆

modularity maximization to design contiguous policy zones for pandemic response

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2023年第1期304卷 99-112页

作者： Baghersad, Milad Emadikhiav, Mohsen Huang, C. Derrick Behara, Ravi S. Florida Atlantic Univ Coll Business Dept Informat Technol & Operat Management Boca Raton FL 33431 USA

The health and economic devastation caused by the COVID-19 pandemic has created a significant global humanitarian disaster. Pandemic response policies guided by geospatial approaches are appropriate additions to traditional epidemiological responses when addressing this disaster. However, little is known about finding the optimal set of locations or jurisdictions to create policy coordination zones. In this study, we propose optimization models and algorithms to identify coordination communities based on the natural movement of people. To do so, we develop a mixed-integer quadratic-programming model to maximize the modularity of detected communities while ensuring that the jurisdictions within each community are contiguous. To solve the problem, we present a heuristic and a column-generation algorithm. Our computational experiments highlight the effectiveness of the models and algorithms in various instances. We also apply the proposed optimization-based solutions to identify coordination zones within North Carolina and South Carolina, two highly interconnected states in the U.S. Results of our case study show that the proposed model detects communities that are significantly better for coordinating pandemic related policies than the existing geopolitical boundaries. (c) 2022 Elsevier B.V. All rights reserved.

关键词： OR in disaster relief Contiguous community detection modularity maximization Pandemic response coordination Column-generation algorithm

来源：评论

学校读者我要写书评

暂无评论

modularity maximization FOR GRAPHONS

引用

SIAM JOURNAL ON APPLIED MATHEMATICS 2022年第6期82卷 1930-1952页

作者： Klimm, Florian Jones, Nick S. Schaub, Michael T. Imperial Coll London Dept Math London SW7 2AZ England Univ Cambridge MRC Mitochondrial Biol Unit Cambridge CB2 0XY England Max Planck Inst Mol Genet Dept Computat Mol Biol D-14195 Berlin Germany Free Univ Berlin Dept Comp Sci D-14195 Berlin Germany Rhein Westfal TH Aachen Dept Comp Sci D-52074 Aachen Germany

Networks are a widely used tool for investigating the large-scale connectivity structure in complex systems and graphons have been proposed as an infinite-size limit of dense networks. The detection of communities or other meso-scale structures is a prominent topic in network science as it allows the identification of functional building blocks in complex systems. Similarly, we may want to simplify graphons in terms of communities, in order to gain a comprehensible description of their meso-scale structure. This raises the question of how communities in graphons can be identified. In this paper, we define a graphon modularity and demonstrate that it can be maximized to detect communities in graphons. We then investigate specific synthetic graphons and show that they may show a wide range of different community structures. We also reformulate the graphon-modularity maximization as a continuous optimization problem and so prove the optimal community structure or lack thereof for some graphons, something that is usually not possible for networks. Furthermore, we demonstrate that estimating a graphon from network data as an intermediate step can improve the detection of communities, in comparison with exclusively maximizing the modularity of the network. While the choice of graphon estimator may strongly influence the accord between the community structure of a network and its estimated graphon, we find that there is a substantial overlap if an appropriate estimator is used. Our study demonstrates that community detection for graphons is possible and may serve as a privacy-preserving way to cluster network data.

关键词： networks community detection modularity maximization graphs graphons privacy

来源：评论

学校读者我要写书评

暂无评论

Revisiting modularity maximization for Graph Clustering: A Contrastive Learning Perspective 24

Revisiting Modularity Maximization for Graph Clustering: A C...

引用

30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

作者： Liu, Yunfei Li, Jintang Chen, Yuehe Wu, Ruofan Wang, Ericbk Zhou, Jing Tian, Sheng Shen, Shuheng Fu, Xing Meng, Changhua Wang, Weiqiang Chen, Liang Ant Grp Hangzhou Peoples R China Ant Grp Guangzhou Peoples R China Ant Grp Shanghai Peoples R China

ISBN: (纸本)9798400704901

Graph clustering, a fundamental and challenging task in graph mining, aims to classify nodes in a graph into several disjoint clusters. In recent years, graph contrastive learning (GCL) has emerged as a dominant line of research in graph clustering and advances the new state-of-the-art. However, GCL-based methods heavily rely on graph augmentations and contrastive schemes, which may potentially introduce challenges such as semantic drift and scalability issues. Another promising line of research involves the adoption of modularity maximization, a popular and effective measure for community detection, as the guiding principle for clustering tasks. Despite the recent progress, the underlying mechanism of modularity maximization is still not well understood. In this work, we dig into the hidden success of modularity maximization for graph clustering. Our analysis reveals the strong connections between modularity maximization and graph contrastive learning, where positive and negative examples are naturally defined by modularity. In light of our results, we propose a community-aware graph clustering framework, coined Magi, which leverages modularity maximization as a contrastive pretext task to effectively uncover the underlying information of communities in graphs, while avoiding the problem of semantic drift. Extensive experiments on multiple graph datasets verify the effectiveness of Magi in terms of scalability and clustering performance compared to state-of-the-art graph clustering methods. Notably, Magi easily scales a sufficiently large graph with 100M nodes while outperforming strong baselines.

关键词： Graph clustering graph contrastive learning modularity maximization

来源：评论

学校读者我要写书评

暂无评论

Analyzing modularity maximization in approximation, heuristic, and graph neural network algorithms for community detection

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2024年 78卷

作者： Aref, Samin Mostajabdaveh, Mahdi Univ Toronto Dept Mech & Ind Engn Toronto ON M5S3G8 Canada Polytech Montreal Dept Math & Ind Engn Montreal PQ H3T1J4 Canada

Community detection, which involves partitioning nodes within a network, has widespread applications across computational sciences. modularity-based algorithms identify communities by attempting to maximize the modularity function across network node partitions. Our study assesses the performance of various modularitybased algorithms in obtaining optimal partitions. Our analysis utilizes 104 networks, including both real -world instances from diverse contexts and modular graphs from two families of synthetic benchmarks. We analyze ten inexact modularity-based algorithms against the exact integer programming baseline that globally optimizes modularity. Our comparative analysis includes eight heuristics, two variants of a graph neural network algorithm, and nine variations of the Bayan approximation algorithm. Our findings reveal that the average modularity-based heuristic yields optimal partitions in only 43.9% of the 104 networks analyzed. Graph neural networks and approximate Bayan, on average, achieve optimality on 68.7% and 82.3% of the networks respectively. Additionally, our analysis of three partition similarity metrics exposes substantial dissimilarities between high-modularity sub -optimal partitions and any optimal partition of the networks. We observe that near-optimal partitions are often disproportionately dissimilar to any optimal partition. Taken together, our analysis points to a crucial limitation of the commonly used modularity-based methods: they rarely produce an optimal partition or a partition resembling an optimal partition even on networks with modular structures. If modularity is to be used for detecting communities, we recommend approximate optimization algorithms for a methodologically sound usage of modularity within its applicability limits. This article is an extended version of an ICCS 2023 conference paper (Aref et al., 2023).

关键词： Network science modularity maximization Integer programming Approximation Graph neural network Graph optimization

来源：评论

学校读者我要写书评

暂无评论

Additive approximation algorithms for modularity maximization

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2021年 117卷 182-201页

作者： Kawase, Yasushi Matsui, Tomomi Miyauchi, Atsushi Univ Tokyo Grad Sch Informat Sci & Technol Bunkyo Ku Hongo 7-3-1 Tokyo 1138656 Japan Tokyo Inst Technol Sch Engn Meguro Ku Ookayama 2-12-1 Tokyo 1528552 Japan

The modularity is the best known and widely used quality function for community detection in graphs. We investigate the approximability of the modularity maximization problem and some related problems. We first design a polynomial-time 0.4209-additive approximation algorithm for the modularity maximization problem, which improves the current best additive approximation error of 0.4672. Our theoretical analysis also demonstrates that the proposed algorithm obtains a nearly-optimal solution for any instance with a high modularity value. We next design a polynomial-time 0.1660-additive approximation algorithm for the maximum modularity cut problem. Finally, we extend our algorithm to some related problems. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Networks Community detection modularity maximization Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A ground truth contest between modularity maximization and modularity density maximization

引用

ARTIFICIAL INTELLIGENCE REVIEW 2020年第6期53卷 4575-4599页

作者： de Santiago, R. Lamb, Luis C. Univ Fed Santa Catarina Dept Comp Sci & Stat Florianopolis SC Brazil Univ Fed Rio Grande do Sul Inst Informat Porto Alegre RS Brazil

Computational techniques for network clustering identification are critical to several application domains. Recently, modularity maximization and modularity Density maximization have become two of the main techniques that provide computational methods to identify network clusterings. Therefore, understanding their differences and common characteristics is fundamental to decide which one is best suited for a given application. Several heuristics and exact methods have been developed for both modularity maximization and modularity Density maximization problems. Unfortunately, no structured methodological comparison between the two techniques has been proposed yet. This paper reports a ground truth contest between both optimization problems. We do so aiming to compare their exact solutions and the results of heuristics inspired in these problems. In our analysis, we use branch-and-price exact methods which apply the best-known column generation procedures. The heuristic methods obtain the highest objective function scores and find solutions for networks with hundreds of thousands of nodes. Our experiments suggest that modularity Density maximization yields the best results over the tested networks. The experiments also show the behavior and importance of the quantitative factor of the modularity Density maximization objective function.

关键词： Network clustering modularity maximization modularity density maximization Algorithms Heuristics Ground truth analyses

来源：评论

学校读者我要写书评

暂无评论

Correspondence analysis-based network clustering and importance of degenerate solutions unification of spectral clustering and modularity maximization

引用

SOCIAL NETWORK ANALYSIS AND MINING 2020年第1期10卷 1-13页

作者： Kimura, Masaomi Shibaura Inst Technol 3-7-5 Toyosu Koto City Tokyo 1358548 Japan

Methods to find clusters in a network have been studied extensively because clustering has practical importance in many applications. Commonly used methods include spectral clustering and Newman's modularity maximization. However, there has been no unified view of the two methods. In this study, we introduce an innovative guiding principle based on correspondence analysis to obtain node coordinates and discuss its equivalence to spectral clustering and Newman's modularity. Besides, we discuss a degeneration case and its significance.

关键词： Spectral clustering modularity maximization Network clustering Correspondence analysis

来源：评论

学校读者我要写书评

暂无评论

A modularity-maximization-based approach for detecting multi-communities in social networks

引用

ANNALS OF OPERATIONS RESEARCH 2021年第1-2期303卷 381-411页

作者： Tsung, Chen-Kun Lee, Sing-Ling Ho, Hann-Jang Chou, ShengKai Natl Chin Yi Univ Technol 57Sec 2Zhongshan Rd Taichung 41170 Taiwan Natl Chung Cheng Univ 168 Univ Rd Minhsiung 62102 Chiayi Taiwan WuFeng Univ 117Sec 2Chiankuo Rd Minhsiung 62153 Chiayi Taiwan

The modularity is a widely-used objective function to determine communities from a given network. The leading eigenvector method is a popular solution that applies the first eigenvector to determine the communities. The low computation cost is the major advantage of the leading eigenvector method. However, the leading eigenvector method only can split a network into two communities. To detect multiple communities, the modularity maximization is transformed to the vector partition problem (VPP). We propose an algorithm which is called as the partition at polar coordinate protocol (PPCP) to solve the VPP problem. The goal of PPCP is to find non-overlapping vertex vector sets so as to maximize the quadratic sum of the norms of community vectors. The proposed PPCP has two steps to determine the communities that are the network structure analysis and the community determination. During the network structure analysis, we obtain following issues. First, the vertex vectors belong to different communities can be separated by the distribution angles. Second, a node with a higher degree corresponds to a vertex vector with a larger norm. So, we propose three refinement functions including the noise reduction, the common-friends model and the strong connectivity hypothesis to improve the accuracy of PPCP. In our simulations, PPCP detects communities more precisely than Fine-tuned algorithm especially in the network with the weak structure. Moreover, the proposed refinement functions can capture the special properties of the network. So, PPCP with refinement functions performs much better than Fine-tuned algorithm and PPCP without refinement functions in terms of the accuracy in detecting communities.

关键词： modularity maximization Community detection Spectral clustering

来源：评论

学校读者我要写书评

暂无评论

Modified modularity Density maximization and Density Ratio Heuristic

引用

COMPUTERS & OPERATIONS RESEARCH 2023年 150卷

作者： Saleh, Zead Pirim, Harun King Fahd Univ Petr & Minerals Ind & Syst Engn Dhahran Saudi Arabia North Dakota State Univ Ind & Mfg Engn Fargo ND 58105 USA

Network science is considered as an interdisciplinary research field engaging engineering, social, natural, and computer sciences. Most networks nestle vertices organized in groups called communities, modules or clusters. Communities are groups of vertices that perhaps partake similar features and/or function common roles within a graph. modularity maximization objective is employed in community detection algorithms. However, modularity maximization solution has practical problems such as resolution limit and frailty. Recently, an alternative clustering measure known as modularity density has been developed to address the resolution limit of modularity maximization. modularity Density maximization (MDM) aims to reduce the out of cluster links. The less out connections improve the objective function. In this research, the out connections are perceived as distances. Thus, we propose a Modified modularity Density maximization (MMDM) as we consider minimizing the deepest out connection instead of minimizing the out links. Modified modularity Density maximization (MMDM) is formulated as a Mixed Integer Linear Programming (MILP). GAMS software is used to solve the model and the obtained results are compared with MDM using internal cluster validation approach. A novel heuristic clustering algorithm named Density Ratio (DR) Heuristic. DR is proposed to solve larger data sets that cannot be solved by MILP or take very long time to solve. The heuristic is applied on both MMDM and MDM approaches and the obtained results are compared using internal cluster validation approach. MMDM finds higher values compared to MDM based on internal validation for some datasets. The density ratio heuristic finds global optimal or near optimal solutions with the datasets employed for the MILP model.

关键词： Clustering modularity maximization modularity Density maximization Heuristic Algorithm MILP

来源：评论

学校读者我要写书评

暂无评论

Ascent-descent variable neighborhood decomposition search for community detection by modularity maximization

引用

ANNALS OF OPERATIONS RESEARCH 2019年第1-2期272卷 273-287页

作者： Dzamic, Dusan Aloise, Daniel Mladenovic, Nenad Univ Belgrade Fac Org Sci Belgrade Serbia Univ Fed Rio Grande do Norte Dept Engn Computacao & Automacao Natal RN Brazil Serbian Acad Sci Math Inst Belgrade Serbia

In this paper we propose a new variant of the Variable Neighborhood Decomposition Search (VNDS) heuristic for solving global optimization problems. We call it Ascent-Descent VNDS since it performs boundary effect, or local search step, even if the improvement in solving the subproblem has not been obtained. We apply it in detecting communities in large networks by modularity maximization, the criterion which is, despite of some recent criticism, most widely used. Computational analysis is performed on 22 instances from the 10th DIMACS Implementation Challenge. On 13 instances where optimal solutions were not known, we got the improved best known solutions on 9 instances and on 4 instances the solution was equal to the best known. Thus, the proposed new heuristic outperforms the current state-of-the-art algorithms from the literature.

关键词： Clustering Community detection modularity maximization Variable neighborhood search Decomposition

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：