FOCS: Fast Overlapped Community Search

 Abstract

Discovery of natural groups of similarly functioning individuals is a key task in analysis of real world networks. Also, overlap between community pairs is commonplace in large social and biological graphs, in particular. In fact, overlaps between communities are known to be denser than the non-overlapped regions of the communities. However, most of the existing algorithms that detect overlapping communities assume that the communities are denser than their surrounding regions, and falsely identify overlaps as communities. Further, many of these algorithms are computationally demanding and thus, do not scale reasonably with varying network sizes. In this article, we propose FOCS (Fast Overlapped Community Search), an algorithm that accounts for local connectedness in order to identify overlapped communities. FOCS is shown to be linear in number of edges and nodes. It additionally gains in speed via simultaneous selection of multiple near-best communities rather than merely the best, at each iteration. FOCS outperforms some popular overlapped community finding algorithms in terms of computational time while not compromising with quality.

Aim

The main aim is to search for overlapped communities in large networks based on locally computed scores.

Scope

The scope is, FOCS (Fast Overlapped Community Search), an algorithm that accounts for local connectedness in order to identify overlapped communities.

Existing System

However, most of the existing algorithms that detect overlapping communities assume that the communities are denser than their surrounding regions, and falsely identify overlaps as communities. The problem of overlapped community detection in social networks has been addressed using a game theoretic framework, where the dynamics of community formation have been captured as a strategic game. Here, each node, a selfish agent in disguise, selects the communities to join or leave, based on its definition of utility. Utility is usually a combination of gain and loss functions. 

Disadvantages

1. FOCS outperforms some popular overlapped community finding algorithms in terms of computational time while not compromising with quality.
2. One of the limitations of FOCS is that the maximum number of communities that can be detected by this method is equal to the number of nodes in a network.

Proposed System

1. This project proposes FOCS (Fast Overlapped Community Search), an algorithm that accounts for local connectedness in order to identify overlapped communities. FOCS is shown to be linear in number of edges and nodes.
2. In this paper, we propose FOCS (Fast Overlapped Community Search) algorithm that searches for overlapped communities in large networks based on locally computed scores. The method has been applied to several large social and biological networks. The detected communities have been compared with respective ground-truth communities for the networks.

Advantages

FOCS is shown to be linear in number of edges and nodes. It additionally gains in speed via simultaneous selection of multiple near-best communities rather than merely the best, at each iteration.

SYSTEM CONFIGURATION 
HARDWARE REQUIREMENTS:-

·       Processor                    -   Pentium –III

·      Speed            -    1.1 Ghz

·      RAM             -    256 MB(min)

·      Hard Disk              -   20 GB

·      Floppy Drive         -    1.44 MB

·      Key Board             -    Standard Windows Keyboard

·      Mouse           -    Two or Three Button Mouse

·      Monitor                 -    SVGA

SOFTWARE REQUIREMENTS:-

·      Operating System          : Windows  7                                  

·      Front End                      : JSP AND SERVLET

·      Database                       : MYSQL

References

Chowdhary, G, Sengupta, D. “FOCS: FAST OVERLAPPED COMMUNITY SEARCH” Knowledge and Data Engineering, IEEE Transactions on (Volume:PP,Issue: 99 ) June 2015