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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Exact Signed modularity density maximization Solutions and Their Real Meaning

Exact Signed Modularity Density Maximization Solutions and T...

引用

IEEE Congress on Evolutionary Computation (CEC) as part of the IEEE World Congress on Computational Intelligence (IEEE WCCI)

作者： de Santiago, Rafael 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

ISBN: (纸本)9781728169293

In the context of social media analyses, signed social networks are important representations of relationships between entities. These networks can represent positive or negative relationships between every two entities of a social network. One of the usual analyses over social networks is the communities/clustering search. In this paper, we report analyses on the Signed modularity density maximization problem, which searches for meaningful clusters inside a signed social network. In this analysis, we present a new branch-and-price algorithm to find optimal solutions to this problem. The optimal solutions of two real signed networks and some artificial networks are generated and analyzed. The results suggest that the problem finds meaningful clusterings in signed social networks, and some parameters are suggested to obtain the best results.

关键词： signed social networks clustering modularity density maximization

来源：评论

学校读者我要写书评

暂无评论

Exact computational solution of modularity density maximization by effective column generation

引用

COMPUTERS & OPERATIONS RESEARCH 2017年 86卷 18-29页

作者： de Santiago, Rafael Lamb, Luis C. Univ Vale Itajai Itajai Brazil Univ Fed Rio Grande do Sul Porto Alegre RS Brazil

modularity density maximization (MDM) is associated with clustering problems in networks. MDM is an alternative to the resolution limit issue of the modularity maximization problem. Several reports in the literature have described mathematical programming models for MDM which solve instances of at most 40 nodes. In this context, this paper presents six new column generation methods that find exact solutions for the MDM problem. These methods use exact and auxiliary heuristic problems and an initial variable generator. Our methods show clear improvements over current results. Comparisons between our proposed methods and state-of-the-art algorithms are also carried out. Our results show that (i) two of our methods surpass the exact state-of-the-art algorithms in terms of time, and (ii) our methods provide optimal values for larger instances than current approaches can tackle. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Graph clustering modularity density maximization Column generation

来源：评论

学校读者我要写书评

暂无评论

Divisive heuristic for modularity density maximization

引用

COMPUTERS & OPERATIONS RESEARCH 2016年第Jul.期71卷 100-109页

作者： Costa, Alberto Kushnarev, Sergey Liberti, Leo Sun, Zeyu Natl Univ Singapore Singapore 117548 Singapore Swiss Fed Inst Technol Future Resilient Syst Program Singapore Singapore Singapore Univ Technol & Design Singapore Singapore Ecole Polytech CNRS LIX F-91128 Palaiseau France

In this paper we consider a particular method of clustering for graphs, namely the modularity density maximization. We propose a hierarchical divisive heuristic which works by splitting recursively a cluster into two new clusters by maximizing the modularity density, and we derive four reformulations for the mathematical programming model used to obtain the optimal splitting. We report computational results of the eight algorithms (four reformulations with two different symmetry breaking strategies) obtained on some instances from the literature. Statistical tests show that the best model in terms of computational time is the one that is obtained with a dual reformulation of the bilinear terms arising in the objective function. Moreover, the hierarchical divisive heuristic provides generally near-optimal solutions in terms of modularity density. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Clustering modularity density maximization Multilinear terms Reformulation Heuristic

来源：评论

学校读者我要写书评

暂无评论

MILP formulations for the modularity density maximization problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2015年第1期245卷 14-21页

作者： Costa, Alberto Singapore Univ Technol & Design Singapore 138682 Singapore

Cluster analysis refers to finding subsets of vertices of a graph (called clusters) which are more likely to be joined pairwise than vertices in different clusters. In the last years this topic has been studied by many researchers, and several methods have been proposed. One of the most popular is to maximize the modularity, which represents the fraction of edges within clusters minus the expected fraction of such edges in a random graph with the same degree distribution. However, this criterion presents some issues, for example the resolution limit, i.e., the difficulty to detect clusters having small sizes. In this paper we focus on a recent measure, called modularity density, which improves the resolution limit issue of modularity. The problem of maximizing the modularity density can be described by means of a 0-1 NLP formulation. We derive some properties of the optimal solution which will be used to tighten the formulation, and we propose some MILP reformulations which yield an improvement of the resolution time. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Clustering Mixed integer linear programming modularity density maximization Reformulations

来源：评论

学校读者我要写书评

暂无评论

Efficient modularity density heuristics for large graphs

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2017年第3期258卷 844-865页

作者： Santiago, Rafael Lamb, Luis C. Univ Fed Rio Grande do Sul Inst Informat Porto Alegre RS Brazil Univ Vale Itajai Ctr Ciencias Tecnol Terra & Mar Itajai SC Brazil

modularity density maximization is a community detection optimization problem which improves the resolution limit degeneracy of modularity maximization. This paper presents seven scalable heuristics for modularity density and compares them with literature results from exact mixed integer linear programming and GAOD, iMeme-Net, HAIN, and BMD-lambda heuristics. The results are also compared with CNM and Louvain, which are scalable heuristics for modularity maximization. The results suggest that our seven heuristics are faster than GAOD, iMeme-Net, HAIN, and BMD-lambda modularity density heuristics. Our experiments also show that some of our heuristics surpassed the objective function value reported by iMemeNet, Hain, and BMD-lambda for some real graphs. Our seven heuristics were tested with real graphs from the Stanford Large Network Dataset Collection and the experiments show that they are scalable. This feature was confirmed by an amortized complexity analysis which reveals average linear time for three of our heuristics. Hypothesis tests suggest that four proposed heuristics are state-of-the-art since they are scalable for hundreds of thousands of nodes for the modularity density problem, and they find the high objective value partitions for the largest instances. Ground truth experiments in artificial random graphs were performed and suggest that our heuristics lead to better cluster detection than both CNM and Louvain. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Heuristics Clustering modularity density maximization Large graphs

来源：评论

学校读者我要写书评

暂无评论

Efficient Quantitative Heuristics for Graph Clustering 17

Efficient Quantitative Heuristics for Graph Clustering

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Santiago, Rafael Lamb, Luis C. Univ Vale Itajai BR-88302901 Itajai SC Brazil Univ Fed Rio Grande do Sul BR-91501970 Porto Alegre RS Brazil

ISBN: (纸本)9781450349390

modularity density maximization (MDM) aims at the identification of modular clusters in graphs. In this paper, we introduce a quantitative heuristic called HLSMDM-lambda, which solves the MDM problem in large graphs. We compared it with state-of-the-art results of exact and heuristic methods such as MDB2, GAOD, iMeme-Net, HAIN, divisive BMD-lambda, MCN-lambda, CNM, and Louvain. The largest tested graphs were executed very efficiently. Our results show that HLSMDM-lambda is scalable in terms of time and is able to find partitions with the highest objective value for the largest tested graphs. HLSMDM-lambda also produced effective results in a ground truth analysis. These results point out that HLSMDM-lambda is a state-of-the-art heuristic for the MDM problem.

关键词： Graph Clustering modularity density maximization Large Graphs

来源：评论

学校读者我要写书评

暂无评论

Efficient modularity density heuristics in graph clustering and their applications

Efficient modularity density heuristics in graph clustering ...

引用

作者： Santiago, Rafael de

modularity density maximization is a graph clustering problem which avoids the resolution limit degeneracy of the modularity maximization problem. This thesis aims at solving larger instances than current modularity density heuristics do, and show how close the obtained solutions are to the expected clustering. Three main contributions arise from this objective. The first one is about the theoretical contributions about properties of modularity density based prioritizers. The second one is the development of eight modularity density maximization heuristics. Our heuristics are compared with optimal results from the literature, and with GAOD, iMeme-Net, HAIN, BMD- heuristics. Our results are also compared with CNM and Louvain which are heuristics for modularity maximization that solve instances with thousands of nodes. The tests were carried out by using graphs from the “Stanford Large Network Dataset Collection”. The experiments have shown that our eight heuristics found solutions for graphs with hundreds of thousands of nodes. Our results have also shown that five of our heuristics surpassed the current state-of-the-art modularity density maximization heuristic solvers for large graphs. A third contribution is the proposal of six column generation methods. These methods use exact and heuristic auxiliary solvers and an initial variable generator. Comparisons among our proposed column generations and state-of-the-art algorithms were also carried out. The results showed that: (i) two of our methods surpassed the state-of-the-art algorithms in terms of time, and (ii) our methods proved the optimal value for larger instances than current approaches can tackle. Our results suggest clear improvements to the state-of-the-art results for the modularity density maximization problem. ...

关键词： Clustering Heurística modularity density maximization Grafos : Arvores : Algoritmos : Algebra booleana : Logica de computadores : Modelagem aritmetica Heuristic search Multilevel heuristics Local search Column generation Tese

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：