PROJECT TITLE :

Quadratic Program-Based Modularity Maximization for Fuzzy Community Detection in Social Networks

ABSTRACT:

One of the most important elements of Social Network Analysis is community detection, i.e., finding teams of similar people based mostly on their traits. In this paper, we have a tendency to present the fuzzy modularity maximization (FMM) approach for community detection, that finds overlapping - that is, fuzzy - communities (where appropriate) by maximizing a generalized kind of Newman's modularity. The first proposed FMM resolution uses a tree-based mostly structure to seek out a globally optimal answer, while the second proposed answer uses alternating optimization to efficiently search for a regionally optimal answer. Each of these approaches are based on a proposed algorithm referred to as one-step modularity maximization (OSMM), which computes the optimal cluster memberships for one person in the social network. We prove that OSMM will be formulated as a simplified quadratic knapsack optimization problem, which is O(n) time complexity. We then propose a tree-based mostly algorithm, known as FMM/Notice Best Leaf Node (FMM/FBLN), which represents sequences of OSMM steps in a tree-based mostly structure. It's proved that FMM/FBLN finds globally optimal solutions for FMM; but, the time complexity of FMM/FBLN is O(nd), d ≥ 2; therefore, it's impractical for many real-world networks. To combat this inefficiency, we have a tendency to propose 5 heuristic-based alternating optimization schemes, i.e., FMM/H1-H5, that are all shown to be O(n2) 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 2 fuzzy community detection algorithms known as GA and vertex-similarity based gradient-descent technique (VSGD) on 10 real-world datasets. We tend to conclude that one in every of the 5 heuristic algorithms (FMM/H2) is terribly competitive with GALS and a lot of a lot of effective than MSFCM, GA, and VSGD. Furthermore, all of the FMM/H schemes are at least 2 orders of magnitude faster than GALS in run time. Finally, - MM/H, in contrast to GALS (which only produces crisp partitions) and MSFCM (which perpetually finds fuzzy partitions), is the only fuzzy community detection algorithm so far that may find the max-modularity partition, fuzzy or crisp.