Conference Papers
Permanent URI for this collectionhttps://idr.nitk.ac.in/handle/123456789/28506
Browse
6 results
Search Results
Item Dynamic structure for web graphs with extended functionalities(Association for Computing Machinery acmhelp@acm.org, 2016) Goyal, S.; Bindu, P.V.; Santhi Thilagam, P.S.The hyperlink structure of World Wide Web is modeled as a directed, dynamic, and huge web graph. Web graphs are analyzed for determining page rank, fighting web spam, detecting communities, and so on, by performing tasks such as clustering, classification, and reachability. These tasks involve operations such as graph navigation, checking link existence, and identifying active links, which demand scanning of entire graphs. Frequent scanning of very large graphs involves more I/O operations and memory overheads. To rectify these issues, several data structures have been proposed to represent graphs in a compact manner. Even though the problem of representing graphs has been actively studied in the literature, there has been much less focus on representation of dynamic graphs. In this paper, we propose Tree- Dictionary-Representation (TDR), a compressed graph representation that supports dynamic nature of graphs as well as the various graph operations. Our experimental study shows that this representation works efficiently with limited main memory use and provides fast traversal of edges. © 2016 ACM.Item Diffusion models and approaches for influence maximization in social networks(Institute of Electrical and Electronics Engineers Inc., 2016) Tejaswi, V.; Bindu, P.V.; Santhi Thilagam, P.S.Social Network Analysis (SNA) deals with studying the structure, relationship and other attributes of social networks, and provides solutions to real world problems. Influence maximization is one of the significant areas in SNA as it helps in finding influential entities in online social networks which can be used in marketing, election campaigns, outbreak detection, and so on. It deals with the problem of finding a subset of nodes called seeds such that it will eventually spread maximum influence in the network. This paper focuses on providing a complete survey on the influence maximization problem and covers three major aspects: i) different types of input required ii) influence propagation models that map the spread of influence in the network, and iii) the approximation algorithms suggested for seed set selection. We also provide the state of the art and describe the open problems in this domain. © 2016 IEEE.Item Deriving temporal trends in user preferences through short message strings(Institute of Electrical and Electronics Engineers Inc., 2016) Deb, S.; Mohan, S.; Venkatraman, P.; Bindu, P.V.; Santhi Thilagam, P.S.Short message strings are widely prevalent in the age of social networking. Taking Facebook as an example, a user may have many other users in his contact list. However, at any given time frame, the user interacts with only a small subset of these users. In this paper, we propose a recommender system that determines which users have common interests based on the content of the short message strings of different users. The system calculates the similarity between two users based on the contents of short message strings by the users over a certain time period. A similarity measure based on short message strings must be temporal study as the contents of the short messages vary rapidly over time. Experimental study is conducted in the Facebook domain using status updates of users. © 2016 IEEE.Item In-memory representations for mining big graphs(Institute of Electrical and Electronics Engineers Inc., 2017) Goyal, S.; Bindu, P.V.; Santhi Thilagam, P.S.Graphs are ubiquitous and are the best data structure for representing linked data because of their flexibility, scalability, and power to deal with complexity. Storing big graphs in graph databases leads to difficult computation and increased time complexity. The best alternative is to use inmemory representations such as compact data structures. They compress the graph sufficiently such that it can be stored in memory and can allow all the possible operations in compressed form itself. In this paper we discuss about five compression techniques: WebGraph, Re-pair, BFS, k2, and dk2. In addition, we compare them based on four parameters: compression ratio, supported functionalities, supported graph types, and dynamic support. The paper is concluded by bringing out the need to have a more advanced, dynamic, and versatile compression technique. © 2016 IEEE.Item Target specific influence maximization: An approach to maximize adoption in labeled social networks(Institute of Electrical and Electronics Engineers Inc., 2017) Tejaswi, V.; Bindu, P.V.; Santhi Thilagam, P.S.Influence maximization deals with finding a small set of nodes, called seed set, to be initially influenced such that they will eventually spread the influence to maximum number of users in the social network. This paper deals with a specialization of the basic problem called labeled influence maximization that identifies seeds that will maximize the influence spread among a specific set of target users identified by their attribute values. In a social setting, a large difference exists between awareness and adoption of an idea/product. This notion fits well in case of labeled influence maximization where any user can become 'aware' about a product whereas only specific users 'adopt' the product. This work considers the problem of labeled influence maximization by incorporating the difference between awareness and adoption. Due to the inherent difference in nature, characteristics, and interests of every user, the number of users who adopt a product varies depending on the type of users in the network and the suitability of the product being marketed. Most of the existing diffusion models do not take this into account. This paper proposes a target adoption model that accounts for both awareness and adoption spread in the network, and a heuristic based discounting approach to find the seed set. The proposed approach is evaluated on different datasets and found to outperform the existing heuristics and discounting approaches. The approach causes maximum adoption in the given social network. © 2017 IEEE.Item Identifying Provenance of Information and Anomalous Paths in Attributed Social Networks(Institute of Electrical and Electronics Engineers Inc., 2018) Trivedi, H.; Bindu, P.V.; Santhi Thilagam, P.S.Information provenance problem is an important and challenging problem in social network analysis and it deals with identifying the origin or source of information spread in a social network. In this paper, an approach for detecting the source of an information spread as well as suspicious anomalous paths in a social network is proposed. An anomalous path is a sequence of nodes that propagates an anomalous information to the given destination nodes who cause an anomalous event. The proposed approach is based on attribute-based anomalies and information cascading technique. The anomalous paths are identified in two steps. The first step assigns an anomalous score to each and every vertex in the given graph based on suspicious attributes. The second step detects the source and suspicious anomalous paths in the network using the anomaly scores. The approach is tested on datasets such as Enron and Facebook to demonstrate its effectiveness. Detecting anomalous paths is useful in several applications including identifying terrorist attacks communication path, disease spreading pattern, and match-fixing hidden path between bookie and a cricketer. © 2018 IEEE.