Browsing by Author "Ahmed, Rezwan"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Algorithms for mining evolving patterns in dynamic relational networks
    (2014-09) Ahmed, Rezwan
    Dynamic networks have recently being recognized as a powerful abstraction to model and represent the temporal changes and dynamic aspects of the data underlying many complex systems. This recognition has resulted in a burst of research activity related to modeling, analyzing, and understanding the properties, characteristics, and evolution of such dynamic networks. The focus of this growing research has been mainly defining important recurrent structural patterns and developing algorithms for their identification. Most of these tools are not designed to identify time-persistent relational patterns or do not focus on tracking the changes of these relational patterns over time. Analysis of temporal aspects of the entity relations in these networks can provide significant insight in determining the conserved relational patterns and the evolution of such patterns over time. Computational methods and tools that can efficiently and effectively analyze the changes in dynamic relational networks can substantially expand the types and diversity of dynamic networks that can be analyzed and the information that can be gained from such analysis. This may provide information on the recurrence and the stability of its relational patterns, help in the detection of abnormal patterns potentially indicating fraudulent or other malevolent behaviors, and improve the ability to predict the relations and their changes in these networks. In this dissertation we present new data mining methods for analyzing the temporal evolution of relations between entities of relational networks. Different classes of evolving relational patterns are introduced that are motivated by considering two distinct aspects of relational pattern evolution. The first is the notion of state transition and seeks to identify sets of entities whose time-persistent relations change over time and space. The second is the notion of coevolution and seeks to identify recurring sets of entities whose relations change in a consistent way over time and space. We first present a new class of patterns, referred as the evolving induced relational states (EIRS), which is designed to analyze the time-persistent relations or states between the entities of the dynamic networks. These patterns can help identify the transitions from one conserved state to the next and may provide evidence to the existence of external factors that are responsible for changing the stable relational patterns in these networks. We developed an algorithm to efficiently mine all maximal non-redundant evolution paths of the stable relational states of a dynamic network. Next we introduce a class of patterns, referred to as coevolving relational motifs (CRM), which is designed to identify recurring sets of entities whose relations change in a consistent way over time. CRMs can provide evidence to the existence of, possibly unknown, coordination mechanisms by identifying the relational motifs that evolve in a similar and highly conserved fashion. An algorithm is presented to efficiently analyze the frequent relational changes between the entities of the dynamic networks and capture all frequent coevolutions as CRMs. At last, we define a new class of patterns built upon the concepts of CRMs, referred as coevolving induced relational motifs (CIRM), is designed to represent patterns in which all the relations among recurring sets of nodes are captured and some of the relations undergo changes in a consistent way across different snapshots of the network. We also present an algorithm to efficiently mine all frequent coevolving induced relational motifs.A comprehensive evaluation of the performance and scalability of all the algorithms is presented through extensive experiments using multiple dynamic networks derived from real world datasets from various application domains. The detailed analysis of the results from the experiments illustrate the efficiency of these algorithms. In addition, we provide a qualitative analysis of the information captured by each class of the discovered patterns. For example, we show that some of the discovered CRMs capture relational changes between the nodes that are thematically different (i.e., edge labels transition between two clusters of topics that have very low similarity). Moreover, some of these patterns are able to capture network characteristics that can be used as features for modeling the underlying dynamic network.The new classes of evolving patterns and the algorithms can enable the effective analysis of complex relational networks towards the goal of better understanding of their temporal changes. Knowing these patterns provides strong observational evidence of the existence of mechanisms that control, coordinate, and trigger these evolutionary changes, which can be used to focus further studies and analysis.
  • Thumbnail Image
    Item
    Algorithms for Mining the Coevolving Relational Motifs in Dynamic Networks
    (2014-03-24) Ahmed, Rezwan; Karypis, George
    Computational methods and tools that can efficiently and effectively analyze the temporal changes in dynamic complex relational networks enable us to gain significant insights regarding the entity relations and their evolution. This paper introduces a new class of dynamic graph patterns, referred to as coevolving relational motifs (CRMs), which are designed to identify recurring sets of entities whose relations change in a consistent way over time. Coevolving relational motifs can provide evidence to the existence of, possibly unknown, coordination mechanisms by identifying the relational motifs that evolve in a similar and highly conserved fashion. We developed an algorithm to efficiently analyze the frequent relational changes between the entities of the dynamic networks and capture all frequent coevolutions as CRMs. Our algorithm follows a depth-first exploration of the frequent CRM lattice and incorporates canonical labeling for redundancy elimination. Experimental results based on multiple real world dynamic networks show that the method is able to efficiently identify CRMs. In addition, a qualitative analysis of the results shows that the discovered patterns can be used as features to characterize the dynamic network.
  • Thumbnail Image
    Item
    TOPTMH: Topology Predictor for Transmembrane Alpha-Helices
    (2008-02-13) Ahmed, Rezwan; Rangwala, Huzefa; Karypis, George
    Alpha-helical transmembrane proteins mediate many key biological processes and represent 20-30% of all genes in many organisms. Due to the difficulties in experimentally determining their high-resolution 3D structure, computational methods that predict their topology (transmembrane helical segments and their orientation) are essential in advancing the understanding of membrane proteins structures and functions. We developed a new topology prediction method for transmembrane helices called TOPTMH that combines a helix residue predictor with a helix segment identification method and determines the overall orientation using the positive-inside rule. The residue predictor is built using Support Vector Machines (SVM) that utilize evolutionary information in the form of PSI-BLAST generated sequence profiles to annotate each residue by its likelihood of being part of a helix segment. The helix segment identification method is built by combining the segments predicted by two Hidden Markov Models (HMM)one based on the SVM predictions and the other based on the hydrophobicity values of the sequences amino acids. This approach combines the power of SVM-based models to discriminate between the helical and non-helical residues with the power of HMMs to identify contiguous segments of helical residues that take into account the SVM predictions and the hydrophobicity values of neighboring residues. We present empirical results on two standard datasets and show that both the per-residue (Q2) and per-segment (Qok) scores obtained by TOPTMH are higher than those achieved by well-known methods such as Phobius and MEMSAT3. In addition, on an independent static benchmark, TOPTMH achieved the highest scores on high-resolution sequences (Q2 score of 84% and Qok score of 86%) against existing state-of-the-art systems while achieving low signal peptide error.