View on GitHub


Integrating Network and Community Discovery

download .ZIPdownload .TGZ


The problem of community detection has recently been studied widely in the context of the web and social media networks. Most algorithms for community detection assume that the entire network is available for online analysis. In practice, this is not really true, because only restricted portions of the network may be available at any given time for analysis.


We have used 2 modules mainly ChooseNode which chooses node in each iteration to be merged to the network and UpdateCommunity which will update the community or clusters from the choosen node I/P : initial set of clustering , Initial network, cost and budget O/P : final network and nodes with clusters formed from nodes we have discovered


Information Retrieval and Extraction Course

IIIT-H Major Project'

update community

network discovery

ChooseNode Module:

ChooseNode module takes current network, initial clustering, costs, budget as input and it computes the node which must be chosen for updating the community under that budget constraints.

Computescore function can be implemented in 2 ways using 2 formulas Ncut Measure and Modularity

Ncut Measure : minimize the similarity across a cut, while simultaneously maximizing the similarity within the same community.

Modularity : additional fraction of the edges that fall within the given communities over the expected fraction, networks with high modularity have dense connections between the nodes within the same community and sparse connections between nodes in different communities.

Using any of the measures we calculate the score and select the node i accordingly that is to be chosen and is given to that to update community and in current network.

UpdateCommunity Module:

UpdateCommunity function is executed during each iteration together with locality discovery process. The value θ ik · θ jk represents the expected number of edges of community k that lie between nodes i and j. And the exact number A ij is Poisson distributed around this expected value.

Authors and Contributors

Nikhil Daliya

Athresh G

Support or Contact

Research paper : On integrating Network and Community Discovery