Title: A mixed graph model for community detection

Authors: Anita Keszler; Tamás Szirányi

Addresses: Distributed Events Analysis Research Group, MTA SZTAKI, Kende utca 13-17, Budapest, Hungary. ' Distributed Events Analysis Research Group, MTA SZTAKI, Kende utca 13-17, Budapest, Hungary

Abstract: A mixed graph theoretic model is proposed for finding communities in a social network. Information on the habits (shopping habits, free time activities) is considered to be known at least for part of the society. The presented model is based on applying parallelly a standard and a bipartite graph. Compared to previous methods, the introduced algorithm has the advantage of noise-tolerance and is suitable independently of the size of the clusters in the graph. Clusters in the dataset tend to form dense subgraphs in both graph models. The idea is to speed up cluster core mining by a modified MST algorithm. Noise in the dataset is defined as missing information on a person's habits. Clustering noisy data is done by using a bipartite graph and fuzzy membership functions. The proposed algorithm can be used for predicting the missing data estimated on the available information patterns. The presented mixed graph model might also be used for image processing tasks.

Keywords: community detection; clustering; noise tolerance; dense subgraph mining; social networks; incomplete data; graph theory; virtual communities; online communities; web based communities; user habits; information patterns; image processing.

DOI: 10.1504/IJIIDS.2012.049316

International Journal of Intelligent Information and Database Systems, 2012 Vol.6 No.5, pp.479 - 494

Received: 03 Mar 2011
Accepted: 25 Nov 2011
Published online: 16 Aug 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article