Sitaram Asur
Abstract
Interaction graphs are ubiquitous in many fields such as bioinformatics, sociology and physical sciences. There have been many studies in the literature targeted at studying and mining these graphs. However, almost all of them have studied these graphs from a static point of view. The study of the evolution of these graphs over time can provide tremendous insight on the behavior of entities, communities and the flow of information among them. In this work, we present an event-based characterization of critical behavioral patterns for temporally varying interaction graphs. We use nonoverlapping snapshots of interaction graphs and develop a framework for capturing and identifying interesting events from them. We use these events to characterize complex behavioral patterns of individuals and communities over time. We show how semantic information can be incorporated to reason about community-behavior events. We also demonstrate the application of behavioral patterns for the purposes of modeling evolution, link prediction and influence maximization. Finally, we present a diffusion model for evolving networks, based on our framework.
- Alkemade, F. and Castaldi, C. 2005. Strategies for the diffusion of innovations on social networks. Computat. Econ. 25, 1--2. Google Scholar
Digital Library
- Asur, S., Parthasarathy, S., and Ucar, D. 2007. An event-based framework for characterizing the evolution of interaction graphs. Tech. Rep. Feb 2007, OSU-CISRC-2/07-TR16.Google Scholar
- Asur, S., Ucar, D., and Parthasarathy, S. 2007. An ensemble framework for clustering protein protein interaction networks. Bioinformatics 23, 13, i29--40. Google ScholarDigital Library
- Backstrom, L., Huttenlocher, D. P., and Kleinberg, J. M. 2006. Group formation in large social networks: membership, growth, and evolution. In Proceedings of the SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York. Google ScholarDigital Library
- Barabasi, A.-L. and Bonabeau, E. 2003. Scale-free networks. Scient. Amer. 288, 60--69.Google ScholarCross Ref
- Barabasi, A.-L., Jeong, H., Ravasz, R., Nda, Z., Vicsek, T., and Schubert, A. 2002. On the topology of the scientific collaboration networks. Physica A. 311, 590--614.Google ScholarCross Ref
- Chakrabarti, D., Kumar, R., and Tomkins, A. 2006. Evolutionary clustering. In Proceedings of the SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York. Google ScholarDigital Library
- Chi, Y., Song, X., Zhou, D., Hino, K., and Tseng, B. L. 2007. Evolutionary spectral clustering by incorporating temporal smoothness. In Proceedings of the SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, 153--162. Google ScholarDigital Library
- Clauset, A., Newman, M. E. J., and Moore, C. 2004. Finding community structure in very large networks. Physical Review E 70.Google Scholar
- Cowan, R. and Jonard, N. 2004. Network structure and the diffusion of knowledge. J. Econ. Dynam. Cont. 28, 1557--1575.Google ScholarCross Ref
- Falkowski, T., Bartelheimer, J., and Spiliopoulou, M. 2006. Mining and visualizing the evolution of subgroups in social networks. In Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence. ACM, New York. Google ScholarDigital Library
- Ferlez, J., Faloutsos, C., Leskovec, J., Mladenic, D., and Grobelnik, M. 2008. Monitoring network evolution using MDL. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). IEEE Computer Society Press, Los Alamitos, CA, 1328--1330. Google ScholarDigital Library
- Flake, G. W., Lawrence, S. R., Giles, C. L., and Coetzee, F. M. 2002. Self-organization and identification of web communities. IEEE Comput. 36, 66--71. Google ScholarDigital Library
- Gabrilovich, E. and Markovitch, S. 2007. Computing semantic relatedness using wikipedia-based explicit semantic analysis. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). Google ScholarDigital Library
- Ganesan, P., Garcia-Molina, H., and Widom, J. 2003. Exploiting hierarchical domain structure to compute similarity. ACM Trans. Inf. Syst 21, 1. Google ScholarDigital Library
- Girvan, M. and Newman, M. E. J. 2002. Community structure in social and biological networks. Proc. Nat. Acad. Sci. USA 99, 12, 7821--7826.Google ScholarCross Ref
- Hopcroft, J., Khan, O., Kulis, B., and Selman, B. 2004. Tracking evolving communities in large linked networks. Proc. Nat. Acad. Sci. 101, 5249--5253.Google ScholarCross Ref
- Kempe, D., Kleinberg, J., and Tardos, E. 2003. Maximizing the spread of influence through a social network. In Proceedings of the SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York. Google ScholarDigital Library
- Kempe, D., Kleinberg, J., and Tardos, E. 2005. Influential nodes in a diffusion model for social networks. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP). ACM, New York. Google ScholarDigital Library
- Lada, A. A. and Adar, E. 2003. Friends and neighbors on the web. Social Netw. 25, 3 (July), 211--230.Google Scholar
- Leskovec, J., Kleinberg, J. M., and Faloutsos, C. 2005. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York. Google ScholarDigital Library
- Leskovec, J., Lang, K. J., Dasgupta, A., and Mahoney, M. W. 2008. Statistical properties of community structure in large social and information networks. In WWW '08: Proceeding of the 17th International Conference on World Wide Web. ACM, New York, 695--704. Google ScholarDigital Library
- Liben-Nowell, D. and Kleinberg, J. M. 2003. The link prediction problem for social networks. In Proceedings of the ACM CIKM International Conference on Information and Knowledge Management. ACM, New York. Google ScholarDigital Library
- Lin, D. 1998. An information-theoretic definition of similarity. In Proceedings of the 15th International Conference Machine Learning. Google ScholarDigital Library
- Lord, P., Stevens, R., Brass, A., and Goble, C. 2003. Semantic similarity measures as tools for exploring the gene ontology. In Proceedings of the Pacific Symposium on Biocomputing, 601--612.Google Scholar
- Newman, M. 2001. Clustering and preferential attachment in growing networks. Phys. Rev. E 64.Google ScholarCross Ref
- Newman, M. E. J. 2006. Modularity and community structure in networks. Proc. Nat. Acad. Science of the USA 103, 23, 8577--8582.Google ScholarCross Ref
- Otey, M. E., Parthasarathy, S., and Trost, D. C. 2006. Dissimilarity measures for detecting hepatotoxicity in clinical trial data. In Proceedings of the SIAM International Conference on Data Mining (SDM).Google Scholar
- Palla, G., Barabasi, A.-L., and Vicsek, T. 2007. Quantifying social group evolution. Nature 446, 7136 (April), 664--667.Google ScholarCross Ref
- Resnik, P. 1999. Semantic similarity in a taxonomy: An information-based measure and its application to problems of ambiguity in natural language. J. Artif. Intell. Res. 11, 95--130.Google ScholarCross Ref
- Richardson, R., Smeaton, A. F., and Murphy, J. 1994. Using WordNet as a knowledge base for measuring semantic similarity between words. In Proceedings of the Artif. Intel. Cognit. Sci. (AICS).Google Scholar
- Samtaney, R., Silver, D., Zabusky, N., and Cao, J. 1994. Visualizing features and tracking their evolution. IEEE Comput. 27, 7, 20--27. Google ScholarDigital Library
- Strehl, A. and Ghosh, J. 2002. Cluster ensembles a knowledge reuse framework for combining multiple partitions. J. Mach. Learn. Res. 3, 583--617. Google ScholarDigital Library
- Tadepalli, S., Ramakrishnan, N., Watson, L. T., Mishra, B., and Helm, R. F. 2008. Simultaneously segmenting multiple gene expression courses by analyzing cluster dynamics. In Proceedings of the Asia Pacific Bioinformatics Conference (APBC), 297--306.Google Scholar
- Tantipathananandh, C., Berger-Wolf, T. Y., and Kempe, D. 2007. A framework for community identification in dynamic social networks. In Proceedings of the SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, 717--726. Google ScholarDigital Library
- Wasserman, S. and Faust, K. 1994. Social network analysis. Cambridge University Press.Google Scholar
- Yang, H., Parthasarathy, S., and Mehta, S. 2005. A generalized framework for mining spatio-temporal patterns in scientific data. In Proceedings of the SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York. Google ScholarDigital Library
- Yang, X., Asur, S., Parthasarathy, S., and Mehta, S. 2008. A visual-analytic toolkit for dynamic interaction graphs. In Proceedings of the SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York. Google ScholarDigital Library
Index Terms
- An event-based framework for characterizing the evolutionary behavior of interaction graphs
Recommendations
An event-based framework for characterizing the evolutionary behavior of interaction graphs
KDD '07: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data miningInteraction graphs are ubiquitous in many fields such as bioinformatics, sociology and physical sciences. There have been many studies in the literature targeted at studying and mining these graphs. However, almost all of them have studied these graphs ...
Characterizing defect n-extendable graphs and (2n+1) -critical graphs
A near perfect matching is a matching saturating all but one vertex in a graph. Let G be a connected graph. If any n independent edges in G are contained in a near perfect matching where n is a positive integer and n=<(|V(G)|-2)/2, then G is said to be ...
Characterizing 2-crossing-critical graphs
It is very well-known that there are precisely two minimal non-planar graphs: K 5 and K 3 , 3 (degree 2 vertices being irrelevant in this context). In the language of crossing numbers, these are the only 1-crossing-critical graphs: they each have ...
Reviews
Kalman Balogh
The behavior of interactions can be analyzed with the help of interaction graphs that represent the existence of relationships between entities. Temporal change of relationships is investigated by comparing consecutive snapshots of the graph, reflecting events that have happened. The paper shows the types of events that "characterize complex behavioral patterns of individuals and communities over time. [...] Behavioral measures for stability, sociability, influence, and popularity" are defined with the help of suitable elementary events. These measures are applied in the analysis of networks: diffusion of information/influence, link prediction, and influence maximization. In the case of textual domains, the authors show how semantic content can be taken into consideration, in order to analyze semantic information content similarity, group merge and split, entropy, and information gain. The authors also explore the kinds of weights that can be attached to nodes, in order to simulate the diffusion of information. The measures and notions introduced and the algorithms outlined-under conditions that are being satisfied in many application domains-are efficiently computable in parallel architectures, implemented by incremental algorithms involving bit-matrix computations. The authors show the efficacy of the notions introduced and compare their framework to others. The notions and methods introduced are applied to three real-life domains, showing their behavioral differences: a clinical trials patient network supporting drug design, Wikipedia, and a coauthorship network. The notation and formalism are rather rough in places, but the meaning is made clear by explanations and examples. I recommend this valuable and thought-provoking paper, particularly to those interested in social network analysis. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments