Ijettjournal.org

International Journal of Engineering Trends and Technology (IJETT) – Volume 4 Issue 10 - Oct 2013
A Novel Framework for Aggloramative Performance 1M.Tech Scholar, 2Assistant Professor 1,2 Department of Computer Science and Engineering University College of Engineering Kakinada, JNTU Kakinada.
Abstract: There is more scalability of individual in present
edge set and Yi ⊆ Y are the class labels of a vertex vi∈ V , social media. If we want to know similar behaviour of the
and known values of Yi for some subsets of vertices VL , individuals in the social media that study is known as
how can we infer the values of Yi (or an estimated collective behaviour study. This is more complexity that the
probability over each label) for the remaining vertices V information of a individual over more scalability of the social
media. So we introduced a process to retrieve the behaviour of
an individual and it includes incremental clustering and the
naives Bayesian classification on the social media for
by Robert E. Park, and employed definitively by Herbert retrieving the information. It gives good results on social
Blumer, to refer to social processes and events which do media data and makes computational operations easier and
not reflect existing social structure (laws, conventions, easily comparative to the information of an individual.
and institutions), but which emerge in a "spontaneous" way. Collective behaviour might also be defined as action which is neither conforming (in which actors follow Recently, Social media like Face book and prevailing norms) nor deviant (in which actors violate those YouTube are becoming increasingly popular. But how to norms). Collective behaviour, a third form of action, takes monetize the rocketing online traffic in social media is a place when norms are absent or unclear, or when they big challenge. Unfortunately, in normal social networking contradict each other. Scholars have devoted far less sites, not like search engines, very limited user profile or attention to collective behaviour than they have to either intention information are available. Given the social network information, is it possible to infer the user preference or potential behaviour? We change intellectual gears when we confront Blumer's final form of collective behaviour, the social When people are exposed in a social network movement. He identifies several types of these, among environment, their behaviours can be influenced by the which are active social movements such as the French behaviours of their friends. People are more likely to Revolution and expressive ones such as Alcoholics connect to others sharing certain similarity with them. This Anonymous. An active movement tries to change society; naturally leads to behaviour correlation between connected an expressive one tries to change its own members. The users [5].Take marketing as an example: if our friends buy social movement is the form of collective behaviour which something, there is a better-than-average chance that we satisfies least well the first definition of it which was will buy it, too. This behaviour correlation can also be offered at the beginning of this article. These episodes are explained by homophile [6]. Given a network with the less fluid than the other forms, and do not changes as often behavioural information of some actors, how can we infer as other forms do. Furthermore, as can be seen in the the behavioural outcome of the remaining actors within the history of the labour movement and many religious sects, a same network? Here, we assume the studied behaviour of social movement may begin as collective behaviour but one actor can be described with K class labels {c1 , · · · , cK over time become firmly established as a social institution. }. Each label, ci , can be 0 or 1. For instance, one user might join multiple groups of interest, so c the user subscribes to group i, and ci = 0 otherwise. Likewise, a user can be interested in several topic homogeneous. People can connect to their family, simultaneously, or click on multiple types of ads. One colleagues, college classmates, or buddies met online. special case is K = 1, indicating that the studied behavior Some relations are helpful in determining a targeted can be described by a single label with 1and 0. For behavior (category) while others are not. This relation-type example, if the event is the presidential election, 1 or 0 information, however, is often not readily available in indicates whether or not a voter voted for Barrack Obama social media. A direct application of collective inference .The problem we study can described formally as follows. [9] or label propagation [12] would treat connections in a Suppose there are K class labels Y ={c1 , · · · , cK }. Given social network as if they were homogeneous. To address network G = (V, E, Y ) where V is the vertex set, E is the the heterogeneity present in connections, a framework ISSN: 2231-5381 http://www.ijettjournal.org Page 4400 International Journal of Engineering Trends and Technology (IJETT) – Volume 4 Issue 10 - Oct 2013
(SocioDim) [2] has been proposed for collective behavior social dimensions can be categorized into node-view and The framework SocioDim is composed of two steps: 1) social dimension extraction, and 2) discriminative learning. In the first step, latent social dimensions are extracted based on network topology to capture the potential affiliations of actors. These extracted social dimensions represent how each actor is involved in diverse affiliations. One example of the social dimension representation is shown in Table 1. The entries in this table denote the degree of one user involving in an affiliation. These social dimensions can be treated as features of actors for subsequent discriminative learning. Since a network is converted into features, typical classifiers such as support vector machine and logistic regression can be employed. The discriminative learning procedure will determine which social dimension correlates with the targeted behaviour and then assign proper weights. A key observation is that actors of the same affiliation tend to connect with each other. For instance, it is reasonable to expect people of the same department to interact with each other more frequently. Hence, to infer actors’ latent affiliations, we need to find out a group of  Node-view methods concentrate on clustering nodes of people who interact with each other more frequently than at a network into communities. As we have mentioned, the random. This boils down to a classic community detection extraction of social dimensions boils down to a community problem. Since each actor can get involved in more than detection task. The requirement is that one actor should be one affiliation, a soft clustering scheme is preferred. In the allowed to be assigned to multiple affiliations. Many initial instantiation of the framework SocioDim, a spectral existent community detection methods, with the aim of variant of modularity maximization [3] is adopted to partitioning the nodes of a network into disjoint sets, do not extract social dimensions. The social dimensions satisfy this requirement. Instead, a soft clustering scheme is correspond to the top eigenvectors of a modularity matrix. preferred. Hence, variants of spectral clustering, modularity It has been empirically shown that this framework maximization, non-negative matrix factorization or block outperforms other representative relational learning models can be applied. One representative example of methods on social media data. However, there are several node-view methods is modularity maximization [6]. The concerns about the scalability of SocioDim with modularity top eigenvectors of a modularity matrix are used as the social dimensions in [8]. Suppose we are given a toy • Social dimensions extracted according to soft clustering, network as in Figure 3, of which there are 9 actors, with such as modularity maximization and probabilistic each circle representing one affiliation. For k affiliations, methods, are dense. Suppose there are 1 million actors in a typically at least k - 1 social dimensions are required. The network and 1, 000 dimensions are extracted. If standard top social dimension based on modularity maximization of double precision numbers are used, holding the full matrix the toy example is shown in Table 2. The actors of negative alone requires 1M × 1K × 8 = 8G memory. This large-size values belong to one affiliation, and actor 1 and those dense matrix poses thorny challenges for the extraction of actors with positive values belonging to the other social dimensions as well as subsequent discriminative affiliation. Note that actor 1 is involved in both affiliations. Hence, actor 1's value is in between (close to 0). This social • Networks in social media tend to evolve, with new dimension does not state explicitly about the association, members joining and new connections occurring between but presents degree of associations for all actors. existing members each day. This dynamic nature of Edge-view methods concentrate on clustering edges of a networks entails an efficient update of the model for network into communities. One representative edge-view collective behavior prediction. Efficient online updates of method is proposed in [9]. The critical observation is that eigenvectors with expanding matrices remain a challenge. an edge resides in only one affiliation, though a node can SocioDim framework is proposed to address the Reusable:SocioDim is composed of two parts: relation heterogeneity presented in social networks. Thus, a community detection and supervised learning. Both are sensible method for social dimension extraction becomes well-studied. Many algorithms have been developed and critical to its success. Briey, existing methods to extract numerous existing software packages can be plugged in ISSN: 2231-5381 http://www.ijettjournal.org Page 4401 International Journal of Engineering Trends and Technology (IJETT) – Volume 4 Issue 10 - Oct 2013
instantaneously, enabling code reuse and saving many minimum distanced edge put on the cluster of Efficient: A key difference of SocioDim framework 3. Save centroids. If we add affiliation, repeat step 2. from collective inference is that it is very efficient for prediction by trading more time in network pre-processing and training. Collective inference typically requires many we keep only a vector of MaxSim to represent the scans of the whole network for prediction while SocioDim maximum similarity between one data instance and a accomplishes the task in one shot. SocioDim is more centroid. In each iteration, we first identify the instances suitable for online applications as a majority of them relevant to a centroid, and then compute similarities of emphasize more on prompt response for predictions. these instances with the centroid. This avoids the iteration over each instance and each centroid, which will cost O(mk) otherwise. Note that the centroid contains one Given a network, graph partition algorithms can be applied feature (node), if and only if any edge of that node is to its corresponding line graph. The set of communities in the line graph corresponds to a disjoint edge partition in the After clustering of the edges we construct classifier original graph. Recently, such a scheme has been used to based on the social dimensions. We designed a new detect overlapping communities [16], [17]. It is, however, classifier. This classification is based on the cluster prohibitive to construct a line graph for a mega-scale probability and testing edge. If any unlabeled edge network. We notice that edges connecting to the same node connected to a network, we have classify that edge belongs in the original network form a clique in the corresponding to which cluster. So we used most efficient classification line graph. For example, edges e(1, 3), e(2, 3), and e(3, 4) that is Bayesian classification to find the new belongs to are all neighbouring edges of node 3 in Figure 1. Hence, which cluster. A naive Bayes classifier is a simple they are adjacent to each other, forming a clique. This property leads to many more edges in a line graph than in theorem with strong (naive) independence assumptions. A the original network. In our framework the given network more descriptive term for the underlying probability model is scanned and divides into disjoints sets. Then it is would be "independent feature model". converted into edge centric view shown in table 1. The discussion so far has derived the independent feature model, that is, the naive Bayes probability model. The naive Bayes classifier combines this model with a decision rule. One common rule is to pick the hypothesis that is most probable; this is known as the maximum a By dividing into edge centric view it easy to identify which nodes are connected each other for further process of our framework. Then we apply edge clustering methods for finding the similarity between the edges that means the In the classification the unlabeled edge is individuals. For this we used incremental clustering. The classified to labelled edge. In this mean, variance main purpose of clustering the edges has two reasons. calculations are more dependent to calculate the probability Those are connections between the users and scalability of the connected users. If a edge connects two nodes definitely the corresponding edge features are non zero numerical. In this mainly we have sparsity that means In the previous sections, we have introduced the problem of scattering of the edges in the network, so we have to gather collective behaviour prediction, covered a social learning similar properties of the nodes. So that we can easily framework based on social dimensions, in the present classify the testing edges of the network. So we use framework we introduced new edge centric based incremental clustering algorithm to cluster the edges in the classification. Compared to existing algorithms it more network. The clustering methodology is shown below: advantageous and reduce time for unlabeled edge classification. We used incremental clustering for grouping the labelled edge, it is one of the best clustering algorithm. output: Clusters having the similar features of edges. We tested theoretically and give best results. 1. Select centroids based on number of affiliations. find distance between the centroid and the edge in [1] L. Tang and H. Liu, “Toward predicting collective behavior via social dimension extraction,” IEEE Intelligent Systems, vol. 25, pp. 19–25, 2010. ISSN: 2231-5381 http://www.ijettjournal.org Page 4402 International Journal of Engineering Trends and Technology (IJETT) – Volume 4 Issue 10 - Oct 2013
dimensions,” in KDD ’09: Proceedings of the 15th ACM http://www.citebase.org/abstract?id=oai: SIGKDD international conference on Knowledge discovery and data mining. New York, NY, USA: ACM, 2009, pp. [18] R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin, “LIBLINEAR: A library for large linear [3] M. Newman, “Finding community structure in classification,” Journal of Machine Learning Research, networks using the eigenvectors of matrices,” Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), http://dx.doi.org/10.1103/PhysRevE.74.036104 [4] L. Tang and H. Liu, “Scalable learning of collective behaviour based on sparse social dimensions,” in CIKM ’09: Proceeding of the 18th ACM conference on Information and knowledge management. New York, NY, [5] P. Singla and M. Richardson, “Yes, there is a correlation: - from social networks to personal behavior on the web,” in WWW ’08: Proceeding of the 17th international conference on World Wide Web. New York, [6] M. McPherson, L. Smith-Lovin, and J. M. Cook, “Birds of a feather: Homophily in social networks,” Annual Review of Sociology, vol. 27, pp. 415–444, 2001. [7] A. T. Fiore and J. S. Donath, “Homophily in online dating: when do you like someone like yourself?” in CHI ’05: CHI ’05 extended abstracts on Human factors in computing systems. New York, NY, USA: ACM, 2005, pp. [8] H. W. Lauw, J. C. Shafer, R. Agrawal, and A. Ntoulas, “Homophily in the digital world: A LiveJournal case study,” IEEE Internet Computing, vol. 14, pp. 15–23, 2010. [9] S. A. Macskassy and F. Provost, “Classification in networked data: A toolkit and a univariate case study,” J. Mach. Learn. Res., vol. 8, pp. 935–983, 2007. [10] X. Zhu, “Semi-supervised learning literature survey,” 2006. http://pages.cs.wisc.edu/ jerryzhu/pub/ssl survey 12 9 2006.pdf [11] L. Getoor and B. Taskar, Eds., Introduction to Statistical Relational Learning. The MIT Press, 2007. [12] X. Zhu, Z. Ghahramani, and J. Lafferty, “Semi-supervised learning using gaussian fields and harmonic functions,” in ICML, 2003. [13] S. White and P. Smyth, “A spectral clustering approach to finding communities in graphs,” in SDM, 2005. [14] M. Newman, “Power laws, Pareto distributions and Zipf’s law,” Contemporary physics, vol. 46, no. 5, pp. 323–352, 2005. [15] F. Harary and R. Norman, “Some properties of line digraphs,” Rendiconti del Circolo Matematico di Palermo, vol. 9, no. 2, pp. 161–168, 1960. [16] T. Evans and R. Lambiotte, “Line graphs, link partitions, and overlapping communities,” Physical Review E, vol. 80, no. 1, p. 16105, 2009. [17] Y.-Y. Ahn, J. P. Bagrow, and S. Lehmann, “Link communities reveal multi-scale complexity in networks,” ISSN: 2231-5381 http://www.ijettjournal.org Page 4403

Source: http://www.ijettjournal.org/volume-4/issue-10/IJETT-V4I10P122.pdf