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

Relating modularity maximization and Stochastic Block Models in Multilayer Networks

SIAM JOURNAL ON MATHEMATICS OF DATA SCIENCE 2019年第4期1卷 667-698页

作者： Pamfil, A. Roxana Howison, Sam D. Lambiotte, Renaud Porter, Mason A. Univ Oxford Math Inst Oxford OX2 6GG England Univ Calif Los Angeles Dept Math Los Angeles CA 90095 USA

Characterizing large-scale organization in networks, including multilayer networks, is one of the most prominent topics in network science and is important for many applications. One type of mesoscale feature is community structure, in which sets of nodes are densely connected internally but sparsely connected to other dense sets of nodes. Two of the most popular approaches for community detection are to maximize an objective function called \modularity" and to perform statistical inference using stochastic block models. Inspired by Newman's work on monolayer networks [Phys. Rev. E, 94 (2016), 052315], we show in multilayer networks that maximizing modularity is equivalent, under certain conditions, to maximizing the posterior probability of community assignments under suitably chosen stochastic block models. We derive versions of this equivalence for various types of multilayer structures, including temporal, multiplex, and multilevel networks. We consider cases in which the key parameters are constant, as well as ones in which they vary across layers;in the latter case, this yields a novel, layer-weighted version of the modularity function. Our results also help address a longstanding difficulty of multilayer modularity-maximization algorithms, which require the specification of two sets of tuning parameters that have been difficult to choose in practice. We show how to perform this parameter selection in a statistically grounded way, and we demonstrate the effectiveness of our approach on both synthetic and empirical networks.

关键词： community detection modularity maximization stochastic block models multilayer networks

来源：评论

学校读者我要写书评

暂无评论

Adaptive modularity maximization via edge weighting scheme

引用

INFORMATION SCIENCES 2018年 424卷 55-68页

作者： Lu, Xiaoyan Kuzmin, Konstantin Chen, Mingming Szymanski, Boleslaw K. Rensselaer Polytech Inst Dept Comp Sci Troy NY 12181 USA Google Inc Mountain View CA USA

modularity maximization is one of the state-of-the-art methods for community detection that has gained popularity in the last decade. Yet it suffers from the resolution limit problem by preferring under certain conditions large communities over small ones. To solve this problem, we propose to expand the meaning of the edges that are currently used to indicate propensity of nodes for sharing the same community. In our approach this is the role of edges with positive weights while edges with negative weights indicate aversion for putting their end-nodes into one community. We also present a novel regression model which assigns weights to the edges of a graph according to their local topological features to enhance the accuracy of modularity maximization algorithms. We construct artificial graphs based on the parameters sampled from a given unweighted network and train the regression model on ground truth communities of these artificial graphs in a supervised fashion. The extraction of local topological edge features can be done in linear time, making this process efficient. Experimental results on real and synthetic networks show that the state-of-the-art community detection algorithms improve their performance significantly by finding communities in the weighted graphs produced by our model. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Community detection Scalability modularity maximization Regularization

来源：评论

学校读者我要写书评

暂无评论

CONVEXIFIED modularity maximization FOR DEGREE-CORRECTED STOCHASTIC BLOCK MODELS

引用

ANNALS OF STATISTICS 2018年第4期46卷 1573-1602页

作者： Chen, Yudong Li, Xiaodong Xu, Jiaming Cornell Univ Operat Res & Informat Engn Ithaca NY 14850 USA Univ Calif Davis Dept Stat Davis CA 95616 USA Purdue Univ Krannert Sch Management W Lafayette IN 47907 USA

The stochastic block model (SBM), a popular framework for studying community detection in networks, is limited by the assumption that all nodes in the same community are statistically equivalent and have equal expected degrees. The degree-corrected stochastic block model (DCSBM) is a natural extension of SBM that allows for degree heterogeneity within communities. To find the communities under DCSBM, this paper proposes a convexified modularity maximization approach, which is based on a convex programming relaxation of the classical (generalized) modularity maximization formulation, followed by a novel doubly-weighted l(1)-norm k-medoids procedure. We establish nonasymptotic theoretical guarantees for approximate and perfect clustering, both of which build on a new degree-corrected density gap condition. Our approximate clustering results are insensitive to the minimum degree, and hold even in sparse regime with bounded average degrees. In the special case of SBM, our theoretical guarantees match the best-known results of computationally feasible algorithms. Numerically, we provide an efficient implementation of our algorithm, which is applied to both synthetic and real-world networks. Experiment results show that our method enjoys competitive performance compared to the state of the art in the literature.

关键词： Community detection modularity maximization degree-corrected stochastic block model convex relaxation k-medians social network

来源：评论

学校读者我要写书评

暂无评论

modularity maximization using completely positive programming

引用

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS 2017年 471卷 20-32页

作者： Yazdanparast, Sakineh Havens, Timothy C. Michigan Technol Univ Dept Elect & Comp Engn Houghton MI 49931 USA

Community detection is one of the most prominent problems of social network analysis. In this paper, a novel method for modularity maximization (MM) for community detection is presented which exploits the Alternating Direction Augmented Lagrangian (ADAL) method for maximizing a generalized form of Newman's modularity function. We first transform Newman's modularity function into a quadratic program and then use Completely Positive Programming (CPP) to map the quadratic program to a linear program, which provides the globally optimal maximum modularity partition. In order to solve the proposed CPP problem, a closed form solution using the ADAL merged with a rank minimization approach is proposed. The performance of the proposed method is evaluated on several real world data sets used for benchmarks community detection. Simulation results shows the proposed technique provides outstanding results in terms of modularity value for crisp partitions. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Community detection modularity maximization Completely positive programming Quadratic programming Linear programming

来源：评论

学校读者我要写书评

暂无评论

Overlapping Community Detection using Clique Proximity and modularity maximization 4

Overlapping Community Detection using Clique Proximity and M...

引用

4th IEEE International Conference on Research in Computational Intelligence and Communication Networks (ICRCICN)

作者： Roy, Mithun Pan, Indrajit Siliguri Inst Technol Dept Comp Sci & Engn Siliguri W Bengal India RCC Inst Informat Technol Dept Informat Technol Kolkata W Bengal India

ISBN: (纸本)9781538676387

Significant communities within social network contain some leading members. Detection of significant communities within a reasonable time is very difficult. This work proposes a new algorithm for a significant community detection using clique proximity measurement and modularity maximization. This algorithm has initially detected disjoint communities. Then some key nodes are identified within this disjoint community which appears in more than one of these disjoint communities. These nodes are subsequently utilized to detect overlapping communities. Experimental results show that present community detection approach shows better performance in terms of modularity.

关键词： clique proximity modularity maximization overlapping community significant community social networks

来源：评论

学校读者我要写书评

暂无评论

On the Role of Degree Influence in Suboptimal modularity maximization

On the Role of Degree Influence in Suboptimal Modularity Max...

引用

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

作者： de Santiago, Rafael Lamb, Luis C. Univ Fed Rio Grande do Sul Inst Informat BR-91501970 Porto Alegre RS Brazil

ISBN: (纸本)9781509006229

Recently, the modularity maximization clustering problem has been the subject of relevant research in community identification. However, it is known that there are an exponential number of suboptimal partitions. This leads to limitations in the development of optimization methods since there are several partitions identified as almost optimal. In this paper, we aim at identifying how node features can influence the number of suboptimal partitions. We show that nodes with small degree dictate the number of suboptimal partitions. We then demonstrate that degree is the most important feature of the nodes, as it defines the magnitude of this value in obtaining suboptimal partitions. We present experimental results that validate our hypothesis and theoretical results. Finally, we show two examples of heuristics that are improved by using our findings.

关键词： Network Clustering modularity maximization Optimization Degeneracies

来源：评论

学校读者我要写书评

暂无评论

Efficient Stochastic Local Search for modularity maximization

Efficient Stochastic Local Search for Modularity Maximizatio...

引用

Genetic and Evolutionary Computation Conference (GECCO)

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

ISBN: (纸本)9781450343237

In this paper, we analyze stochastic local searches and neighbor-hood strategies for the modularity maximization problem. modularity maximization was shown relevant in the identification of clusters in complex and social networks. Our experimental analysis shows that 1-neighborhood is a better strategy for the problem as it quickly locates suboptimal partitions. We find 99% near best-known partitions with 94% of frequency in time vertical bar V vertical bar(1:44) and 95% near best known Q values in sublinear time.

关键词： Clustering modularity maximization Stochastic Local Search

来源：评论

学校读者我要写书评

暂无评论

Quadratic Program-Based modularity maximization for Fuzzy Community Detection in Social Networks

引用

IEEE TRANSACTIONS ON FUZZY SYSTEMS 2015年第5期23卷 1356-1371页

作者： Su, Jianhai Havens, Timothy C. Michigan Technol Univ Dept Comp Sci Houghton MI 49931 USA Michigan Technol Univ Dept Elect & Comp Engn Houghton MI 49931 USA

One of the most important elements of social network analysis is community detection, i.e., finding groups of similar people based on their traits. In this paper, we present the fuzzy modularity maximization (FMM) approach for community detection, which finds overlapping-that is, fuzzy-communities (where appropriate) by maximizing a generalized form of Newman's modularity. The first proposed FMM solution uses a tree-based structure to find a globally optimal solution, while the second proposed solution uses alternating optimization to efficiently search for a locally optimal solution. Both of these approaches are based on a proposed algorithm called one-step modularity maximization (OSMM), which computes the optimal cluster memberships for one person in the social network. We prove that OSMM can be formulated as a simplified quadratic knapsack optimization problem, which is O(n) time complexity. We then propose a tree-based algorithm, called FMM/Find Best Leaf Node (FMM/FBLN), which represents sequences of OSMM steps in a tree-based structure. It is proved that FMM/FBLN finds globally optimal solutions for FMM;however, the time complexity of FMM/FBLN is O(n(d)), d >= 2;thus, it is impractical for most real-world networks. To combat this inefficiency, we propose five heuristic-based alternating optimization schemes, i.e., FMM/H1-H5, which are all shown to be O(n(2)) time complexity. We compare the results of the FMM/H solutions with those of state-of-the-art community detection algorithms, MULTICUT spectral FCM (MSFCM) and GALS, and with those of two fuzzy community detection algorithms called GA and vertex-similarity based gradient-descent method (VSGD) on ten real-world datasets. We conclude that one of the five heuristic algorithms (FMM/H2) is very competitive with GALS and much more effective than MSFCM, GA, and VSGD. Furthermore, all of the FMM/H schemes are at least two orders of magnitude faster than GALS in run time. Finally, FMM/H, unlike GALS (which only pr

关键词： Fuzzy clustering fuzzy community detection graphs modularity modularity maximization quadratic knapsack problem (QKP) quadratic program social networks

来源：评论

学校读者我要写书评

暂无评论

A locally optimal hierarchical divisive heuristic for bipartite modularity maximization

引用

OPTIMIZATION LETTERS 2014年第3期8卷 903-917页

作者： Costa, Alberto Hansen, Pierre Ecole Polytech LIX F-91128 Palaiseau France HEC Montreal Gerad Montreal PQ H3T 2A7 Canada

Given a set of entities, cluster analysis aims at finding subsets, also called clusters or communities or modules, entities of which are homogeneous and well separated. In the last ten years clustering on networks, or graphs, has been a subject of intense study. Edges between pairs of vertices within the same cluster should be relatively dense, while edges between pairs of vertices in different clusters should be relatively sparse. This led Newman to define the modularity of a cluster as the difference between the number of internal edges and the expected number of such edges in a random graph with the same degree distribution. The modularity of a partition of the vertices is the sum of the modularities of its clusters. modularity has been extended recently to the case of bipartite graphs. In this paper we propose a hierarchical divisive heuristic for approximate modularity maximization in bipartite graphs. The subproblem of bipartitioning a cluster is solved exactly;hence the heuristic is locally optimal. Several formulations of this subproblem are presented and compared. Some are much better than others, and this illustrates the importance of reformulations. Computational experiences on a series of ten test problems from the literature are reported.

关键词： Bipartite graphs Clustering modularity maximization

来源：评论

学校读者我要写书评

暂无评论

Reformulation of a model for hierarchical divisive graph modularity maximization

引用

ANNALS OF OPERATIONS RESEARCH 2014年第1期222卷 213-226页

作者： Cafieri, Sonia Costa, Alberto Hansen, Pierre Ecole Natl Aviat Civile Lab MAIAA F-31055 Toulouse France Ecole Polytech LIX F-91128 Palaiseau France HEC GERAD Montreal PQ H3T 2A7 Canada

Finding clusters, or communities, in a graph, or network is a very important problem which arises in many domains. Several models were proposed for its solution. One of the most studied and exploited is the maximization of the so called modularity, which represents the sum over all communities of the fraction of edges within these communities minus the expected fraction of such edges in a random graph with the same distribution of degrees. As this problem is NP-hard, a few non-polynomial algorithms and a large number of heuristics were proposed in order to find respectively optimal or high modularity partitions for a given graph. We focus on one of these heuristics, namely a divisive hierarchical method, which works by recursively splitting a cluster into two new clusters in an optimal way. This splitting step is performed by solving a convex quadratic program. We propose a compact reformulation of such model, using change of variables, expansion of integers in powers of two and symmetry breaking constraints. The resolution time is reduced by a factor up to 10 with respect to the one obtained with the original formulation.

关键词： Clustering Compact reformulation Divisive hierarchical heuristic modularity maximization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：