Context Inference from Social Networks

Context Inference from Social Networks Context Inference from Social Networks: A Tie Strength Based Approach Sneha Kamal Reshmi.S Abstract— All online sharing systems gather data that reflects user’s behavior and their shared activities. Relationship degree between two users is varying continuously. Static friend list in the social network is unable to express it completely. Tie strength is used to quantitatively describe real social relations. It is based on lots of features derived from activities of a user’s in social network. We introduce a model to measure tie strength between users in a given context. Here a novel definition of tie strength is introduced which exploits the existence of multiple online social links between the individuals. The proposed system infer the context from user’s interaction using the applications of Natural language processing methods and clustering techniques. From this context the tie strength between users are found. Then evaluates and analysis the performance of this model. Keywords- Clustering, Natural Language Processing, Social Context, Social Network, Tie Strength I. Introduction A tie is formed between two persons it they are friends or they have interactive behaviors in social network. Strength of a tie represents the degree of relationship between two entities and it can be various. Tie strength in social network depends upon the exchange and transmission of information, and influence between social network users. The friend list of user is incompetent to reflect real social relation of users directly, because all friends are equally treated. Interactive activities such as comment make more sense in maintaining the relationship. So strong tie may have more interactions. Strong ties are peoples which are we really trusted. Although such trusted friendships can provide emotional and economic support. The majority of social media do not incorporate tie strength in the creation and management of relationships, and treat all users the same either friend or stranger. The first attempt to take into consideration is the social role of a friendship was done by Facebook and Google+ by the introduction of the circles. Users can use circles as a technique to organize their contacts, creating different groups for relatives, work colleagues, close friends and so on. But this group of contacts does not provide quantitative information about the real strength of the ties. The most common technique used to measure the tie strength is the closeness of relationship. Thus close friends have strong tie while others have weak ties. Numerous other methods of strengthens have also been proposed. This includes frequency of contacts and mutual acknowledgement of contacts. Other possible indicators of tie strength include extend of multiplicity with a tie, the duration of the contacts, the overlap of membership in an organization between the parties to a tie and the overlap of social circles. However, in our opinion these approaches have some shortcomings. Firstly, the intensity of conversations strongly depends from user to user, making it difficult to understand which of these conversations are dedicated to intimate relationships. Secondly, do not take into account that strong ties must be powered by a form of social grooming that is mainly based on geographical nearness and face-to-face contacts. Our contribution in this paper is assessing the tie strength between two friends on social network. Although distinguishing between strong and weak ties. For that we infer the thematic fields talked about by users with their contacts, is called the social contexts of a user. For this purpose we use the textual information such as photo descriptions, comments, post of users. With users permission we gather such information. NLP techniques are applied to gather such information and find most relevant information is called tag or word. A set of such a tag of a user is called the user’s personomy. The user’s social contexts come out after applying a clustering algorithm over this personomy and classifying the user’s contacts in these clusters. From this clusters find the users with more tie strength. II. Related Works The community can be extracted from social network based on the actions of users in [2]. This method extracts the users that are similar in actions, interests or tastes as a community. Initially a small community will be formed consists of two or more users. Seeing the actions performed by their friends may make users curious. Therefore, similar small communities can be extended to form a larger community. Compared to other method extracted nodes in the communities may not have the best density. In [3] introduce the Virtual Tie Strength (VTS)-scale and their scoring methods appear to provide a valid and reliable measure of tie strength in virtual communities. They developed a model that measures the tie-strength in virtual communities. The VTS-scale is able to distinguishing between two components of tie-strength associates and friendship. But, the content of each component needs more investigation. In [4] observe the communication patterns of millions of mobile phone users. That helps to concurrently study the local and the global structure of a society-wide communication network. Observe the coupling between interaction strengths and the network’s local structure. Then weak ties are removed. In [5] four factors are proposed which depends upon the strength of the tie. They are time closeness intensity and reciprocal service. They argued that degree of overlap between the two individuals friendship network varies depending on the tie strength between the users. Tie strength is depends on the diffusion of influence and information. Most of the network model deals implicitly with strong ties. III. Proposed System The model takes the advantage of users interactions in social networks. It infers the social contexts in which users are involved and which of their contacts belongs to that context. The proposed method consists of 4 modules. They are context data generation, affinity propagation algorithm, context based clustering, tie strength of users. And the output is a community with set of users. Figure 1. Proposed method A. Context Data Generation In this step obtain the interaction of a given user with all other users. In the case of facebook data of a particular user is obtained from the post of the users and comments given to the photos etc. Then apply Natural Language Processing (NLP) to this collected information. It provides a predefined model for sentence splitting, tokenizing and POS tagging. POS tag method in NLP is applied here. B. Tag Cloud Generation Initially from the interaction of users stop words such as ‘and’,’the’,’at’ etc. are removed. This will pass as an input to NLP. NLP will split the given text, using POS tagging. Which identifies each word as part-of-speech category such as Noun, Verb, etc. After keeping the noun and verb all other are removed. The resulting words will consider as a set of tags of a user whose interaction with others. The set of tag of u and v in a social interaction is denoted by T(lu|v), whose tag cloud is denoted by TC(lu|v). Figure 3: Tag Cloud of each user C. Similarity Measurement The main features of the algorithm are Tri-set calculation, similarity computation, seed construction and clustering.Tri set will consist of Cofeature Set (CFS), Unilateral Feature Set (UFS), and Significant Cofeature Set (SCS). Cofeature Set: Consider di and dj, be the two objects in a data set. Suppose that some features of di is also belong to dj. Therefore, construct a new subset consisting of these features and their values in dj. Unilateral Feature Set: Suppose that some features of di, does not belong to dj. Therefore, construct a new subset consisting of these features and their values in di. Significant Cofeature Set: Suppose that some features of di, also belong to the most significant features of dj. So, Therefore, construct a new subset consisting of these features and their values as the most significant features in dj. From this we can calculate the similarity between two points as (1) Where nm ,nq and np are the values of the features with in the set CFS SCS and UFS respectively. And |CFS|,|UFS|, and |SCS|, indicate the number of tuples in CFS(i,j), UFS(i,j), and SCS(i,j)respectively. The set CFS is result of the intersection of the objects. UFS consists of unshared Features. SCS takes into account the most significant features. D. Inferring the Social Context Seed Affinity Propagation Algorithm: Seed Affinity Propagation (SAP) is a semi supervised clustering. The aim is from the initial labeled object we cluster the large number of unlabeled object efficiently. To guarantee accuracy and avoid a blind search for seeds we use Mean Features Selection method. The similarities between tags are passed as input to the algorithm in the form of matrix. The different steps involved in algorithm are: Let D be a data set which consists of set of features of each object and the value associated with these object. Construct the seed from a few labeled object using Mean feature selection Method. Calculate the tri set between the object i and j(CFS(i,j), UFS(i,j), and SCS(i,j)). Similarity calculation between the object using the equation (1). Self similarity computation: Calculate s (l,l) is the mean value of the similarities. These values are referred to as preferences. Initialize the matrixes of messages Message Matrix Computation: Compute availability matrix a (i,j) and responsibility matrix r(i,j). Exemplar selection: By adding the availability and responsibility matrixes we find the exemplar for each object i is the maximum of r(i,j) + a (i,j). Update the matrix using Rt+1 = (1-)Rt+ Rt-1 (2) At+1 = (1-)At+ At-1 (3) Where â‚ ¬ [0,1] is a damping factor. R and A represent the responsibility matrix and availability matrix respectively, and t indicate the iteration times. Iterating steps 6,7and 8 until the exemplar selection result stays constant for a number of iterations. Here the input to the algorithm is is the similarity between the tags mentioned above. It find a number of clusters, but we does not consider all the clusters. We choose K number of clusters base on a threshold value. 2) Other users to social context: After finding the context of a user, we find the other users with the same context. For finding the similarity compare the tag cloud formed during the interaction of u and v (TC(Iu|v)), with the tags in the context of user u TC(cti). ctu|v= (4) Similarity is calculated by using cosine similarity method. Two inputs will consider as vectors. And calculate the angle between these vectors. So the output will be a cluster consists of several users. From this cluster also we find users with strong tie strength. Then the ads will post to this the wall of users who have strong tie strength. Figure 2. Inferring Social context E. Tie Strength Measurements Cluster consists of set of users. They are represented as a graph where nodes are users and edges represent the link between the users. From the given graph we find the tie strength between the users by using similarity and node interaction methods. Output is a weighted graph, where weight in the edge represents the value of tie strength between the two users. Where w represents the intensity of interaction between the nodes, so here we pass the tag weight between the users as w. Td is the set of neighbors of the nodes. If the value of Str(u,v) is greater, indicate that the tie strength between u and v is strong. Figure.5: Graphical Representation of Tie Strength between Users IV. Applications Find the community based on tie strength, so the users in the community may have similar interest. For providing publicity when the ad is posted in the user’s wall, its visibility will be limited to those of his contacts that share a strong tie with the user. So the companies can target the potential customers. V. Conclusion The model takes the advantage of tie strength between the users in the social network to provide publicity to users. Here we applied NLP and data mining techniques. Interaction of users in social network is analyzed using NLP and find Tag cloud of each user. Then calculated the semantic relationship between each tag in the tag cloud. Then apply affinity propagation and obtain the social context of each user. Then associate users in his contacts to the clusters. From this cluster we find the users with strong tie strength. The method will help the companies to find their potential users. Based on the interest of users we can post the corresponding ads to their walls. References Luca Pappalardo, Giulio Rossetti and Dino Pedreschi. â€Å" How well do we know each other? detecting tie strength in multidimensional social networks,† 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Seyed Ahmad Moosavi and MehrdadJalali. â€Å"Community Detection in Online Social Networks Using Actions of Users,†978-1-4799-3351-8/14/$31.00  ©2014 IEEE. Andrea Petrà ³czi and Tamà ¡s Nepusz. â€Å"Measuring tie-strength in virtual social networks† http://www.insna.org/Connections-Web/Volume27-2/5.Petrà ³czi.pdf. J.P. Onnela and J. Sarama ¨ ki. â€Å"Structure and tie srength in mobile communication network, † PNAS published online April 24, 2007. Mark S. Granovetter â€Å" The Strength of Weak Ties,† American Journal of Sociology Volume 78 Issue6 (May 1973) 1360-1380. Yaxi He, Chunhong Zhang and Yang Ji. â€Å" Principle Features for Tie Strength Estimation in Micro-blog Social Network † 2012 IEEE 12th International Conference on Computer and Information Technology. Renchu Guan and Xiaohu Shi,† Text Clustering with Seeds Affinity Propagation,† IEEE Transactions on Knowledge and Data Engineering, Vol. 23, NO. 4, April 2011. T. Pedersen, S. Patwardhan, and J. Michelizzi â€Å"Wordnet:: Similarity: Measuring the relatedness of concepts,† .Demonstration Papers atHLT-NAACL 2004, 2004, pp. 38–41, Association for Computational Linguistics. FakhriHasanzadeh and MehrdadJalali, â€Å"Detecting Communities in Social Networks by Techniques of Clustering and Analysis of Communications,†978-1-4799-3351-8/14/$31.00  ©2014 IEEE. B. Frey and D. Dueck,†Clustering by passing messages between datapoints,† Science, vol. 315, no. 5814, pp. 972–976, 2007. Sandra Servia-Rodrà ­guez, Ana Fernà ¡ndez-Vilas, Rebeca P. Dà ­az-Redondo, and Josà © J. Pazos-Arias. â€Å"Inferring Contexts From Facebook Interactions: A Social Publicity Scenario,† IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 15, NO. 6, OCTOBER 2013.