The information revolution has given birth to Social Networks, which allows structured flow of data, information, and knowledge. Social networks are nodes of individuals, groups, organizations, and related systems that are linked by one or more types of interdependencies. The defining feature of social network analysis is its focus on the structure of relationships. Social network analysis is a set of theories, tools, and processes for better understanding the relationships and structure of a network. Identification of Clusters in Social network is an active area research in artificial intelligence and pattern matching. Adding constraints to clustering improves the performance of a variety of algorithms. Cluster analysis is concerned with the problem of partitioning a given set of entities into homogeneous and well-separated subsets called clusters. Cluster Analysis aims at finding subsets, called clusters, which are homogeneous and/or well separated. Minimum sum of diameters clustering for two clusters can be solved by reduction constraints into the 2- Conjunctive Normal Form statement. Hansen [4] uses Boolean approach to represent constraint in 2-cluster analysis, Identified constraints are represented in the form of 2-SAT statement. Constraint representation of 3-cluster or more then 3-cluster is not possible using Boolean approach. In our earlier paper [11], an approach was proposed “Belonging approach” using that constraints of 2-Cluster are represented in 2-SAT form. In this paper “Belonging approach” is extended for the representation of constraints in K-cluster. This approach can be used to generate constraints for 3-cluster for any value positive integer value of k. Constraints is generated in the form of K-SAT statement. This paper presents a formulation that find out the constraints in k- cluster based on concept of bonding and bridging in social network.

1. B. Aspvall, M.F. Plass and R.E. Tarjan. A Linear-time Algorithm for Testing the Truth of Certain Quantified Boolean Expressions, IPL, 8, 1979, pp 121-123
2. A.V. Aho, I.E. Hopcroft and J.D. Ullman: The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974, pg no. 189- 194
3. John E. Hopcroft, Jefrry D. Ullman: Introduction to automaton theory, languages and computation. pg no. 324- 325
4. P.Hansen, B. Jaumard: Minimum Sum of Diameters, Journal of Classification 4: 215- 226(1987)
5. John F. Kohen: An on Line Satisfiability For Conjunctive Normal form Expressions with two literals, Flairs -02, Proceedings,187 – 191
6. Wagsta, Cardie,” Clustering with Instance-level Constraints”, Proceedings of the Seventeenth International Conference on Machine Learning, 2000, p. 1103-1110.
7. Wagstaff, K., Cardie, C., Rogers, S., & Schroedl, S. (2001) Constrained k-means clustering with background knowledge Proc. of 18th Intl. Conf. on Machine Learning.
8. I. Davidson and S. S. Ravi, “Identifying and Generating Easy Sets of Constraints For Clustering”, Proceedings of the Twenty-First National Conference on artificial Intelligence (AAAI 2006), Boston, MA, July 2006, 6 pages
9. I. Davidson, S. S. Ravi & Shamis, ”A SAT-based Framework for Efficient Constrained Clustering” Proceedings of the SIAM International Conference on Data Mining, SDM 2010, April 29 - May 1, 2010 94-105.
10. Davidson and S. S. Ravi, “Using Instance-Level Constraints in Hierarchical Agglomerative Clustering: Theoretical and Empirical Results”, Data Mining and Knowledge Discovery, Vol. 18, No. 2, Apr. 2009,
11. R. K. Jain, N.S. Chaudhari: Identification and Generation of Constraints in Social Network, Proceedings of International Conference on Emerging Trends in Networks and Computer Communications (ETNCC), 2011, IEEE pp no 11-14
12. Delattre, M., And Hansen, P. (1980): Bicriterion Cluster Analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-2(4), 277-291.
13. P.Hansen, B. Jaumard: Cluster Analysis and Mathematical Programming, Mathematical Programming, 79, 1997, pp 191 - 215.
14. Jiang and Carroll, “Social Capital, Social Network and Identity Bonds: A Reconceptualization” C&T '09 Proceedings of the fourth international conference on Communities and technologies, ACM, pg no 51-60.
15. Nina Mishra, Robert Schreiber, Isabelle Stanton and Robert E. Tarjan, Clustering Social Networks, Springer Lecture Notes in Computer Science,2007, Volume 4863/2007,56-67.

Must Link Constraint Can Not Link Constraint Belonging approach Bonding Bridging