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 non-overlapping 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 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.
- F. Alkemade and C. Castaldi. Strategies for the diffusion of innovations on social networks. Computational Economics, 25(1-2), 2005. Google Scholar
Digital Library
- S. Asur, S. Parthasarathy, and D. Ucar. An event-based framework for characterizing the evolutionf interaction graphs. Technical Report Oct 2006, Updated Jun 2007, OSU-CISRC-2/07-TR16., 2007.Google Scholar
- L. Backstrom, D. P. Huttenlocher, and J. M. Kleinberg. Group formation in large social networks: membership, growth, and evolution. SIGKDD, 2006. Google ScholarDigital Library
- A. L. Barabasi and E. Bonabeau. Scale-free networks. Scientific American, 288:60--69, 2003.Google ScholarCross Ref
- A. L. Barabasi, H. Jeong, R. Ravasz, Z. Nda, T. Vicsek, and A. Schubert. On the topology of the scientific collaboration networks. Physica A, 311:590--614, 2002.Google ScholarCross Ref
- D. Chakrabarti, R. Kumar, and A. Tomkins. Evolutionary clustering. SIGKDD, 2006. Google ScholarDigital Library
- A. Clauset, M. E. J. Newman, and C. Moore. Finding community structure in very large networks. Physical Review E, 70, 2004.Google Scholar
- R. Cowan and N. Jonard. Network structure and the diffusion of knowledge. Journal of Economic Dynamics and Control, 28:1557--1575, 2004.Google ScholarCross Ref
- T. Falkowski, J. Bartelheimer, and M. Spiliopoulou. Mining and visualizing the evolution of subgroups in social networks. IEEE/WIC/ACM International Conference on Web Intelligence, 2006. Google ScholarDigital Library
- G. W. Flake, S. R. Lawrence, C. L. Giles, and F. M.Coetzee. Self-organization and identification of web communities. IEEE Computer, 36:66--71, 2002. Google ScholarDigital Library
- M. Girvan and M. E. J. Newman. Community structure in social and biological networks. Proc. National Academy of Sciences of the United States of America, 99(12):7821--7826, 2002.Google ScholarCross Ref
- D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. SIGKDD, 2003. Google ScholarDigital Library
- D. Kempe, J. Kleinberg, and E. Tardos. Influential nodes in a diffusion model for social networks. Proc. Intl. Colloquium on Automata, Languages and Programming (ICALP), 2005. Google ScholarDigital Library
- J. Leskovec, J. M. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. SIGKDD, 2005. Google ScholarDigital Library
- D. Liben-Nowell and J. M. Kleinberg. The link prediction problem for social networks. Proc. ACM CIKM Intl. Conf. on Information and Knowledge Management, 2003. Google ScholarDigital Library
- J. Lin, M. Vlachos, E. Keogh, and D. Gunopulos. Iterative incremental clustering of time series. EDBT, pages 106--122, 2004.Google ScholarCross Ref
- M. E. J. Newman. Modularity and community structure in networks. Proc. National Academy of Sciences of the United States of America, 103(23):8577--8582, 2006.Google ScholarCross Ref
- J. Reichardt and S. Bornholdt. Detecting fuzzy community structures in complex networks with a potts model. Physical Review Letters, 93, 2004.Google Scholar
- R. Samtaney, D. Silver, N. Zabusky, and J. Cao. Visualizing features and tracking their evolution. IEEE Computer, 27(7):20--27, 1994. Google ScholarDigital Library
- M. Spiliopoulou, I. Ntoutsi, Y. Theodoridis, and R. Schult. Monic - modeling and monitoring cluster transitions. SIGKDD, 2006. Google ScholarDigital Library
- S. van Dongen. A cluster algorithm for graphs. Technical Report INS-R0010, National Research Institute for Mathematics and Computer Science in the Netherlands, Amsterdam, 2000. Google ScholarDigital Library
- S. Wasserman and K. Faust. Social network analysis. Cambridge University Press, 1994.Google ScholarCross Ref
- H. Yang, S. Parthasarathy, and S. Mehta. Mining spatial object patterns in scientific data. Proc. 9th Intl. Joint Conf. on Artificial Intelligence, 2005.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
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 ...
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 subgraphs of Hamming graphs
Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced ...
Comments