Academic Work


The IEEE provisional copyright policies require the following message be posted:
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

     Publication List (pdf)
     Talks (and Posters)     

2016; 2015; 2014; 2013; 2012; 2011; 2010; 2009; 2008; 2007; 2006; 2005; 2004; 2003; 2002; 2001; 2000; 1999 and before.


Publications:

2016:

  1. (2016 WkgPap) P. Drineas, I. Ipsen, E. Kontopoulou, Malik Magdon-Ismail " Structural Convergence Results for Low-Rank Approximations from Block Krylov Spaces", (arXiv).
    Summary: This paper is concerned with approximating the dominant left singular vector space of a real matrix A of arbitrary dimension, from block Krylov spaces q(AAT,AX). Two classes of results are presented. First are bounds on the distance, in the two and Frobenius norms, between the Krylov space and the target space. The distance is expressed in terms of principal angles. Second are quality of approximation bounds, relative to the best low-rank approximation in the Frobenius norm. For starting guesses X of full column-rank, the bounds depend on the tangent of the principal angles between X and the dominant right singular vector space of A. The results presented here form the structural foundation for the analysis of randomized Krylov space methods. The innovative feature is a combination of traditional Lanczos convergence analysis with optimal low-rank approximations via least squares problems.
  2. (2016 WkgPap) A. Kundu, P. Drineas, Malik Magdon-Ismail "Recovering PCA from Hybrid-(ℓ1,ℓ2) Sparse Sampling of Data Elements", (arXiv).
    Summary: This paper addresses how well we can recover a data matrix when only given a few of its elements. We present a randomized algorithm that element-wise sparsifies the data, retaining only a few its elements. Our new algorithm independently samples the data using sampling probabilities that depend on both the squares (ℓ2 sampling) and absolute values (ℓ1 sampling) of the entries. We prove that the hybrid algorithm recovers a near-PCA reconstruction of the data from a sublinear sample-size: hybrid-(ℓ1,ℓ2) inherits the ℓ2-ability to sample the important elements as well as the regularization properties of ℓ1 sampling, and gives strictly better performance than either ℓ1 or ℓ2 on their own. We also give a one-pass version of our algorithm and show experiments to corroborate the theory.
  3. (2016 WkgPap) K. Wu, Malik Magdon-Ismail "Node-By-Node Greedy Deep Learning for Interpretable Features", (arXiv).
    Summary: Multilayer networks have seen a resurgence under the umbrella of deep learning. Current deep learning algorithms train the layers of the network sequentially, improving algorithmic performance as well as providing some regularization. We present a new training algorithm for deep networks which trains \emph{each node in the network} sequentially. Our algorithm is orders of magnitude faster, creates more interpretable internal representations at the node level, while not sacrificing on the ultimate out-of-sample performance.
  4. (2016 Jrnl) S. Das, A. Lavoie, Malik Magdon-Ismail, "Manipulation among the arbiters of collective intelligence: How Wikipedia administrators mold public opinion", ACM Transactions on the Web (pdf preprint)
    Summary: We document that a surprisingly large number of editors change their behavior and begin focusing more on a particular controversial topic once they are promoted to administrator status. The conscious and unconscious biases of these few, but powerful, administrators may be shaping the information on many of the most sensitive topics on Wikipedia; some may even be explicitly infiltrating the ranks of administrators in order to promote their own points of view. In addition, we ask whether administrators who change their behavior in this suspicious manner can be identified in advance. Neither prior history nor vote counts during an administrator’s election are useful in doing so, but we find that an alternative mea- sure, which gives more weight to influential voters, can successfully reject these suspicious candidates. This second result has important implications for how we harness collective intelligence: even if wisdom exists in a collective opinion (like a vote), that signal can be lost unless we carefully distinguish the true expert voter from the noisy or manipulative voter.
  5. (2016 Jrnl) R. Korolov, J. Peabody, A. Lavoie, S. Das, Malik Magdon-Ismail, W. Wallace, "Predicting Charitable Donations Using Social Media", Social Network Analysis and Mining, 6:31. (pdf preprint)
    Summary: We study the relationship between chatter on social media and observed actions concerning charita- ble donation. One hypothesis is that a fraction of those who act will also tweet about it, implying a linear relation. However, if the contagion is present, we expect a super- linear scaling. We consider two scenarios: donations in response to a natural disaster, and regular donations. We empirically validate the model using two location-paired sets of social media and donation data, corresponding to the two scenarios. Results show a quadratic relation between chatter and action in emergency response case. In case of regular donations, we observe a near-linear relation. Additionally, regular donations can be explained by demographic factors, while for a disaster response social media is a much better predictor of action. A contagion model is used to predict the near-quadratic scaling for the disaster response case. This suggests that diffusion is pre- sent in emergency response case, while regular charity does not spread via social network.
  6. (2016 Jrnl) S. Paul, Malik Magdon-Ismail, P. Drineas, "Feature selection for linear SVM with provable guarantees", Pattern Recognition, 60, pages 205--214. (pdf preprint)
    Summary: We give two provably accurate feature-selection techniques for the linear SVM. The algorithms run in deterministic and randomized time respectively. Our algorithms can be used in an unsupervised or supervised setting. The supervised approach is based on sampling features from support vectors. We prove that the margin in the feature space is preserved to within ε-relative error of the margin in the full feature space in the worst-case. In the unsupervised setting, we also provide worst-case guarantees of the radius of the minimum enclosing ball, thereby ensuring comparable generalization as in the full feature space and resolving an open problem posed in Dasgupta et al. (2007).
  7. (2016 Jrnl) K. Clarkson, P. Drineas, Malik Magdon-Ismail, M. Mahoney, X. Meng, D. Woodruff "The Fast Cauchy Transform and Faster Robust Regression", SIAM J. on Computing. (pdf preprint)
    Summary: We provide fast algorithms for robust (L_1) and general L_p regression using a fast projection of the design matrix with a Hardmard scaled by Cauchy random variables (hence the name Fast Cauchy Transform, FCT). Our projection algorithm runs in O(ndlogn) and provides O(d^(2+)) L_1 distortion obliviously for an arbitrary subspace of dimension d. We give applications of our fast embedding algorithm to robust regression, L_p regression and L_1 subspace approximation.
  8. (2016 Conf) Malik Magdon-Ismail, C. Boutsidis, "Optimal Sparse Linear Encoders and Sparse PCA", NIPS 2016, Barcelona, Spain, Dec 2016. (pdf) ( ppt)

  9. (2016 Conf) K. Hegde, Malik Magdon-Ismail, B. Szymanski, K. Kuzmin "Clustering, Prominence and Social Network Analysis on Incomplete Networks", Complex Networks 2016, Milan, Italy, Nov-Dec 2016. (pdf) ( ppt)

  10. (2016 Conf) K. Wu, P. Waters, Malik Magdon-Ismail, "Network Classification Using Adjacency Matrix Embeddings and Deep Learning", ASONAM 2016, San Francisco, Aug 2016. (pdf) ( ppt)

2015:

  1. (2015 WkgPap) Malik Magdon-Ismail, Christos Boutsidis "Optimal Sparse Linear Auto-Encoders and Sparse PCA", (arXiv).
    Summary: Principal components analysis (PCA) is the optimal linear auto-encoder of data, and it is often used to construct features. Enforcing sparsity on the principal components can promote better generalization, while improving the interpretability of the features. We study the problem of constructing optimal sparse linear auto-encoders. Two natural questions in such a setting are: i) Given a level of sparsity, what is the best approximation to PCA that can be achieved? ii) Are there low-order polynomial-time algorithms which can asymptotically achieve this optimal tradeoff between the sparsity and the approximation quality? In this work, we answer both questions by giving efficient low-order polynomial-time algorithms for constructing asymptotically \emph{optimal} linear auto-encoders (in particular, sparse features with near-PCA reconstruction error) and demonstrate the performance of our algorithms on real data.
  2. (2015 WkgPap) Malik Magdon-Ismail "NP-Hardness and Inapproximability of Sparse PCA", (arXiv).
    Summary: We give a reduction from {\sc clique} to establish that sparse PCA is NP-hard. The reduction has a gap which we use to exclude an FPTAS for sparse PCA (unless P=NP). Under weaker complexity assumptions, we also exclude polynomial constant-factor approximation algorithms.
  3. (2015 WkgPap) Mark Goldberg, Mykola Hayvanovych, Malik Magdon-Ismail, William Wallace "Extracting Hidden Groups and their Structure from Streaming Interaction Data", (arXiv).
    Summary: When actors in a social network interact, it usually means they have some general goal towards which they are collaborating. This could be a research collaboration in a company or a foursome planning a golf game. We call such groups \emph{planning groups}. Our particular focus is hidden planning groups who have not "declared" their membership explicitly. We formulate the problem of hidden group discovery from streaming interaction data, and we propose efficient algorithms for identifying the hidden group structures by isolating the hidden group's non-random, planning-related, communications from the random background communications. We validate our algorithms on real data (the Enron email corpus and Blog communication data).
  4. (2015 Conf) S. Paul, Malik Magdon-Ismail, P. Drineas "Column Selection via Adaptive Sampling ", NIPS 2015, Montreal, Canada, Dec 2015. (pdf) ( ppt)

  5. (2015 Conf) A. Kundu, P. Drineas, Malik Magdon-Ismail, "Approximatinig Sparse PCA from Incomplete Data", NIPS 2015, Montreal, Canada, Dec 2015. (pdf) ( ppt)

  6. (2015 Conf) R. Korolov, J. Peabody, A. Lavoie, S. Das, Malik Magdon-Ismail, W. Wallace "Actions Are Louder than Words in Social Media", Proceedings of 2015 International Conference on Advences in Social Networks Analysis and Mining (ASONAM), Paris, France, August 2015. (pdf) ( ppt)

  7. (2015 Conf) S. Paul, Malik Magdon-Ismail, P. Drineas "Feature Selection for Linear SVM with Provable Guarantees", Proceedings of the 17th International Conference on Artificial Intelligence and Statistics (AISTATS), San Diego, CA, May 2015. (pdf) (supplementary material) ( ppt)

  8. (2015 Conf) E. Gertle, E. Mackin, , Malik Magdon-Ismail, L. Xia, Y. Yi, "Computing Manipulations of Ranking Systems", Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Istanbul, Turkey, May 2015. (pdf) ( ppt)

2014:

  1. (2014 Talk) Malik Magdon-Ismail, "Machines that Learn From Data", Rensselaer - TALKS, December 6, 2014. (pdf)
  2. (2014 Talk) Malik Magdon-Ismail, "Using Social Media to Predict Material Convergence", RPI Workshop on Disaster Response Logistics, December 4, 2014. (pdf)
  3. (2014 Talk) Malik Magdon-Ismail, "Learning, Sparsity and Big Data", Bloomberg ML Group (pdf)
    Summary: PCA, Clustering and Regression with sparse features: compute them efficiently and not sacrifice in in-sample performance too much. Mostly show and tell. A little SVM.
  4. (2014 Jrnl) S. Adali, X. Lu, Malik Magdon-Ismail "Local, community and global centrality methods for analyzing networks", Social Network Analysis and Mining (SNAM) (Vol. 4, No 1). (pdf preprint)
    Summary: We introduce different notions of prominence in a network based on its community structure: a local rank, which is the prominence of an actor within its communities (the communities are computed using a clustering algorithm) and its community rank, which is the rank of an actor's community within the "graph of communities". We show in a variety of real networks that these two measures of prominence capture different effects. On these same real networks, we show that external measures of prominence (like an authors citation prominence, or an actors ability to feature in big-budget movies) can be deconstructed into a contribution from local rank and community rank. Local and community ranks also play differing roles depending on the nature of the network and the type of external prominence one wishes to capture.
  5. (2014 Jrnl) C. Boutsidis, P. Drineas, Malik Magdon-Ismail "Near-Optimal Column-Based Matrix Reconstruction", SIAM Journal on Computing (Vol. 43, Issue 2). (pdf)
    Summary: We give o(SVD) algorithms that construct O(k/e) columns to reconstruct a matrix to within O(1+e)| |A-Ak||_F, where Ak is the best rank k reconstruction from the SVD. The number of columns is near optimal, asymptotically matching a known lower bound. We introduce two new tools in our algorithm - fast approximate matrix factorizations, and dual set sparsification results which may be of independent interest.
  6. (2014 Jrnl) C. Boutsidis, Malik Magdon-Ismail "A Note on Sparse Least-squares Regression", Information Processing Letters, accepted. (arXiv version)
    Summary: We give additive error bounds on sparse regression (where the regression vector is required to have a small number of non-zeros) in terms of the top-k PCA regression.
  7. (2014 Jrnl) S. Paul, C. Boutsidis, Malik Magdon-Ismail, P. Drineas "Random Projections for Linear Support Vector Machines", ACM Transactions on Knowledge Discovery from Data, accepted. (arXiv version)
    Summary: We show that using random projections for dimensionality reduction in SVM preserves (to within relative error) both the margin and the radius of the data. Since the margin and data radius are the two quantities parametrizing the statistical generalization error, these statistical bounds are preserved during the feature selection.
  8. (2014 WkgPap) Christos Boutsidis Malik Magdon-Ismail, "Faster SVD-truncated Regularized Least-squares", (arXiv).
    Summary: We develop a new algorithm that computes the SVD-truncated solution to a least squares problem (regression onto the top-k principal components) in time faster than SVD, while guaranteeing an additive error. The algorithm first quickly constructs an approximation to the top-k PCA and uses that approximation in the regression. We give a lower bound showing that our quality of approximation is the best one can expect of such algorithms which first approximate PCA.
  9. (2014 Conf) C. Boutsidis, Malik Magdon-Ismail "Faster SVD-truncated Regularized Least-squares", IEEE International Symposium on Information Theory (ISIT), July 2014, Honolulu, HI, USA. (pdf)
    Summary: We give additive error bounds on sparse regression (where the regression vector is required to have a small number of non-zeros) in terms of the top-k PCA regression.

2013:

  1. (2013 Talk) Malik Magdon-Ismail, "Efficiently Implementing Sparsity in Learning", NIPS Workshop on Large Scale Matrix Analysis and Inference (pdf)
    Summary: This talk describes ways to do PCA, Clustering and Regression with sparse features: compute them efficiently and not sacrifice in in-sample performance too much.
  2. (2013 Talk) Malik Magdon-Ismail, "Learning, Sparsity and Big Data", RPI Dean's Seminar Series (pdf)
    Summary: This talk describes ways to do PCA, Clustering and Regression with sparse features: compute them efficiently and not sacrifice in in-sample performance too much. Mostly show and tell.
  3. (2013 Talk) Malik Magdon-Ismail, "Sparsity in Machine Learning", Talk at ICML Workshop on Numerical Linear Algebra in Machine Learning (pdf)
    Summary: This talk describes ways to do PCA, Clustering and Regression with sparse features: compute them efficiently and not sacrifice in in-sample performance too much.
  4. (2013 Jrnl) C. Boutsidis, Malik Magdon-Ismail, "Near-Optimal Coresets for Least-Squares Regression", IEEE Transactions on Infomation Theory, Vol 59, No. 10, 2013. (pdf, coming soon)
    Summary: We give linear coresets for linear regression in both the spectral and Frobenius norms. Our algorithms are deterministic. We also provide lower bounds on coreset size for both deterministic and randomized algorithms.
  5. (2013 Jrnl) C. Boutsidis, Malik Magdon-Ismail, "Deterministic Feature Selection for k-means Clustering", IEEE Transactions on Infomation Theory, Vol 59, No. 9, 2013. (pdf, coming soon)
    Summary: We give new deterministic algorithms for selecting O(k) features to perform clustering. The resulting features give a relative error approximation to the optimal objective when considering the clustering error in the full space.
  6. (2013 Jrnl) Matthew Newby, Nathan Cole, Heidi Jo Newberg, Travis Desell, Malik Magdon-Ismail, Boleslaw Szymanski, Carlos Varela, Benjamin Willett, and Brian Yanny, "A Spatial Characterization of the Sagittarius Dwarf Galaxy Tidal Tails", The Astronomical Journal Volume 145 Number 6, 2013. (pdf,print version)
    Summary: Using a maximum likelihood algorithm, we simultaneously estimate the dynamical parameters of the Saggitarius Dwarf galaxy stream as well as the parameters of the Milky Way galaxy. As a by-product, we present the first catalog of stars having the same density profile as the Saggitarius stream. These results were achieved by leveraginig the MilkyWay@home volunteer computing platform.
  7. (2013 Jrnl) Sibel Adali, Malik Magdon-Ismail, Xiaohui Lu, "iHypR: Prominence Ranking in Networks of Collaborations with Hyperedges", ACM Transactions on Knowledge Discovery from Data (TKDD), 2013. (accepted) (pdf, coming soon)
    Summary: We give new algorithms for ranking in collaborative networks based on [i]clustering[/i] the collaborative artifacts into hyperedges and using an iterative pagerank type algorithm to obtain the rankings from these hyperedges.
  8. (2013 WkgPap) Elliot Anshelevich, Ameya Hate, Malik Magdon-Ismail, "Seeding Influential Nodes in Non-Submodular Models of Information Diffusion", (arXiv).
    Summary: We develop new algorithms to seed an information diffusions for a non-submodlar model. The model is built to mimic social proceeses that are likely to occur in information diffusion. Our approach is to project the non-submodular model to a class of submodular models for which an efficient solution can be constructed. We demonstrate significantly better performance as compared to using random or high degree seeding strategies on real and synthetic networks.
  9. (2013 WkgPap) Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff, "The Fast Cauchy Transform and Faster Robust Linear Regression", submitted, 2013. (arXiv).
    Summary: We develop the Fast Cauchy Transform (FCT), the L1 equivalent of the Fast Johnson Lindenstrauss Transform, which allows us to develop a fast algorithm for robust (L1) regression. This can be extended to Lp regression for p in the range [1,2]. We also give experimental simulations which show that the practice follows the theory closely.
  10. (2013 Conf) Sanmay Das, Allen Lavoie, Malik Magdon-Ismail, "Manipulation Among the Arbiters of Collective Intelligence: How Wikipedia Administrators Mold Public Opinion", ACM Conference on Information and Knowledge Management (CIKM), 2013. Pages 1097-1106. (pdf) (slides)

  11. (2013 Conf) Sibel Adali, Xiaohui Lu, Malik Magdon-Ismail, "Deconstructing centrality: thinking locally and ranking globally in networks", Proceedings 5th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Niagara Falls, Canada, August 2013. (pdf) (slides)

  12. (2013 Conf) S. Paul, C. Boutsidis, Malik Magdon-Ismail, P. Drineas "Random Projections for Support Vector Machines", Proceedings of the 16th International Conference on Artificial Intelligence and Statistics (AISTATS) Scottsdale, AZ, April 2013. (pdf, coming soon) ( ppt)

  13. (2013 Conf) Elliot Anshelevich, Ameya Hate, Malik Magdon-Ismail, "Seeding Influential Nodes in Non-Submodular Models of Information Diffusion", Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), St. Paul, Minnesota, May 2013. (pdf) (arXiv) ( ppt)

  14. (2013 Conf) Kenneth Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael Mahoney, Xiangrui Meng, David Woodruff, "The Fast Cauchy Transform and Faster Robust Linear Regression", Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, Louisiana, January 2013. (pdf) ( ppt)

2012:

  1. (2012 Book) Yaser Abu-Mostafa, Malik Magdon-Ismail, Hsuan-Tien Lin "Learning from Data: A Short Course", amlbook.com, ISBN-13: 978-1600490064, March 2012.
    This book is Part I of our text book on Machine Learning that is on the foundations and basic principles of learning from data. Roughly speaking, the book addresses the following topics: What is learning? Is learning feasible? Can we do it efficiently (linear models)? Can we do it well (overfitting and regularization)? Lesons learned - what are the take home messages?
  2. (2012 Jrnl) Petros Drineas, Malik Magdon-Ismail, Michael Mahoney, David Woodruff, "Fast Approximation of Matrix Coherence and Statistical Leverage", Journal of Machine Learning Research (JMLR), Volume 13, pages 3441-3472, Dec 2012. (pdf)
    Summary: We give the first algorithms to compute statistical leverage and coherence in sub-SVD time using random projections. The algorithms are accurate to within relative error. Datapoints with high statistical leverage are important in that they are likely to belong to good coresets that can reproduce a linear regression to within relative error.
  3. (2012 Jrnl) Sibel Adali, Tina Liu, Malik Magdon-Ismail, "An Analysis of Optimal Link Bombs", Theoretical Computer Science, volume 437, pages 1-20, 2012. (preprint pdf) (print version online).
    Summary: We consider the optimal attack pattern to spam the page rank algorithm. It turns out to be particularly simple: all attackers point to the victim. This optimally increases not only the page-rank of the victim but also the rank (based on the page-rank) of the victim. We also consider optimal 'disguised' attacks, i.e. attacks where the attackers do not want to be directly associated to the victim. A similar result holds in that setting.
  4. (2012 Jrnl) Ali Civril, Malik Magdon-Ismail, "Column subset selection via sparse approximation of SVD", Theoretical Computer Science, Volume 421, pages 1-14, 2012. (preprint pdf) (print version).
    Summary: We give one of the first deterministic algorithms for provable reconstruction of a matrix using a small subset of its columns. The method is based on a greedy approximation of the SVD. In order to greedily approximate the SVD from a dictionary, we extend Natarajan's result for greedy approximation of a vector from a dictionary.
  5. (2012 WkgPap) Saurabh Paul, Christos Boutsidis, Malik Magdon-Ismail, Petros Drineas, "Random Projections for Support Vector Machines", submitted, 2012. (arXiv).
    Summary: We give an oblivious random projection algorithm which samples a number features proportional to the rank of the data matrix such that the margin and radius of the data in the dimensionally reduced space are comparable to those in the original full-dimension space. Thus the generalization properties of the SVM are preserved. We give experimental simulations which bear out the theory.
  6. (2012 WkgPap) Christos Boutsidis, Petros Drineas, Malik Magdon-Ismail, "Rich Coresets For Constrained Linear Regression", submitted, 2012. (arXiv).
    Summary: We give the first polynomial algorithms which find a coreset of size order the number of variables, such that the regression on this coreset gives a relative error approximation to the regression on the full data set.
  7. (2012 WkgPap) P. Horn, Malik Magdon-Ismail, "Spreading Processes and Large Components in Ordered, Directed Random Graphs", submitted, 2011. (arXiv).
    Summary: We consider a spreading process that can be mapped onto a random graph model: order the vertices and randomply place directed edges from lower ranked to higher ranked vertices; each such edge exists independently with probability \math{p}. If the spread starts at the first vertex, the size of the infection is the component reachable from this vertex. We prove existence of a sharp threshold \math{p^*=\log n/n} at which this reachable component transitions from \math{o(n)} to \math{\Omega(n)}.
  8. (2012 WkgPap) Malik Magdon-Ismail, "A Note On Estimating the Spectral Norm of A Matrix Efficiently". (arXiv).
    Summary: A random projection based power iteration for estimating spectral norms to within relative error.
  9. (2012 Conf) Sibel Adali, Xiaohui Lu, Malik Magdon-Ismail, "Attentive Betweenness Centrality (ABC): Considering Options and Bandwidth when Measuring Criticality", Proceedings IEEE Conference on Social Computing (SocialCom), Amsterdam, The Netherlands, September 2012. (pdf) (slides)

  10. (2012 Conf) Pranay Anchuri, Malik Magdon-Ismail, "Communities and Balance in Signed Networks: A Spectral Approach", Proceedings of 4th International on Advances in Social Networks Analysis and Mining (ASONAM), Istanbul, Turkey, August 2012. (pdf) ( ppt)

  11. (2012 Conf) Mark Goldberg, Malik Magdon-Ismail, James Thompson "Identifying Long Lived Social Communities Using Structural Properties", Proceedings of 4th International on Advances in Social Networks Analysis and Mining (ASONAM), Istanbul, Turkey, August 2012. (pdf) ( ppt)

  12. (2012 Conf) Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, David P. Woodruff "Fast Approximation of Matrix Coherence and Statistical Leverage", Proceedings of 25th International Conference on Machine Learning (ICML), Edinburgh, Scotland, June 2012. (pdf) ( ppt)

  13. (2012 Wkshp) Hsuan-Tien Lin, Malik Magdon-Ismail, Yaser S. Abu-Mostafa "Teaching Machine Learning to a Diverse Audience: the Foundation-based Approach", Teaching Machine Learning Workshop at the 25th International Conference on Machine Learning (ICML), Edinburgh, Scotland, June 2012. (pdf) ( ppt)

  14. (2012 Conf) Mark Goldberg, Malik Magdon-Ismail, William Wallace, John Schwartz and Bridget Gutting "Graph Search Beyond Text: Relational Searches in Semantic Hyperlinked Data", Proceedings of 10th International Conference on Intelligence and Security Informatics (ISI), Washington DC, June 2012. (pdf) ( ppt)

  15. (2012 Conf) Malik Magdon-Ismail, Brian Orecchio "Guard Your Connections: Infiltration of a Trust/Reputation Based Network", Proceedings of 4th International Conference on Web Science (WebSci) in conjunction with NetSci 2012, Evanston IL, June 2012. ( pdf) ( ppt)

  16. (2012 Wkshp) Sanmay Das, Allen Lavoie, Malik Magdon-Ismail, "Pushing Your Point of View: Behavioral Measures of Manipulation in Wikipedia", Workshop on Social Computing and User Generated Content at ACM Conference on Electronic Commerce (ACM-EC), Valencia, Spain, June 2012. (pdf) ( ppt)

  17. (2012 Conf) Aseem Brahma, Mithun Chakraborty, Sanmay Das, Allen Lavoie, Malik Magdon-Ismail, "A Bayesian Market Maker", Proceedings of 13th International Conference on Electronic Commerce (EC), Valencia, Spain, June 2012. ( pdf) ( ppt)

  18. (2012 Conf) Cindy Hui, William Wallace, Malik Magdon-Ismail, Mark Goldberg "Information Cascades in Social Media in Response to a Crisis: a Preliminary Model and a Case Study", Proceedings of Workshop on Social Web for Disaster Management (SWDM) at World Wide Web Conference (WWW), April 2012. pdf. Poster: ppt.

  19. (2012 Conf) Sibel Adali, Fred Sisenda, Malik Magdon-Ismail, "Actions Speak as Loud as Words: Predicting Relationships from Social Behavior Data", Proceedings of World Wide Web Conference (WWW), April 2012. pdf. Poster: ppt.

2011:

  1. (2011 BkChap) S. Kelley, M. Goldberg, Malik Magdon-Ismail, K. Mertsalov, W. Wallace, "Defining and Discovering Communities in Social Networks", Book Chapter in Handbook of Optimization in Complex Networks, eds. M. Thai and P. Pardalos, Chapter 6, pages, 2011. (pdf).
    Summary: Overlapping communities play a large role in the functioning of social networks. We give a definition based on minimal properties that such communities should have, and develop efficient algorithms to find such comunities. We give some methods for validating that the communities found are "real" and compare this minimal axiomatic approach to several other benchmark algorithms which take a specific view as to the structure of the communities.
  2. (2011 BkChap) C. Busch, Malik Magdon-Ismail, J. Xi, "Oblivious Routing for Sensor Network Topologies", Book Chapter in Theoretical Aspects of Distributed Computing in Sensor Networks, eds. S. Nikoletseas and J. D. P. Rolim, Chapter 13, pages 381-400, Springer, 2011. (pdf).
    Summary: We collect some of our previous results on oblivious routing algorithms with near-optimal congestion and dilation (as compared with optimal offline routing) for sensor network topologies which include the d-dimensional mesh and uniform geometric networks.
  3. (2011 Jrnl) Ali Civril, Malik Magdon-Ismail "Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix", Algorithmica, pages 1-18 Journal Version: pdf. (arXiv).
    Summary: We show that selecting columns of a data matrix to have maximum "numerical rank" (as measured by the volume of the data vectors selected) is exponentially hard to approximate.
  4. (2011 Jrnl) S. Das, Malik Magdon-Ismail, "A Model for Information Growth in Collective Wisdom Processes", ACM Transactions on Knowledge Discovery from Data (TKDD), volume 6, issue 2, article 6, July 2011. preprint (pdf). (pdf).
    Summary: We give a succint model for edit dynamics in collective wisdom processes in which users (the collective) arrive sequentially and contribute to the wisdom on a particular topic. The model captures the arrival of new information, together with the saturation of information on a particular topic. As the quality of a particular topic increases, there is a tradeoff between more uses arriving and those users having less to contribute. We demonstrate the model on Wiki and Blog edit behavior, in particular capturing the main observed phenomenological dynamics within just this simple model.
  5. (2011 Jrnl) M. Goldberg, Malik Magdon-Ismail, "Embedding a Forest in a Graph", Electronic Journal of Combinatorics (EJC), Volume 18(1), P99, Apr 29, 2011. (pdf).
    Summary: For p\ge 1, we prove that every forest with p trees whose sizes are a_1, . . . , a_p can be embedded in any graph containing at least \sum_{i=1}^p (a_i + 1) vertices and having minimum degree at least \sum_{i=1}^p a_i.
  6. (2011 Jrnl) Malik Magdon-Ismail, Jonathan Purnell, "Approximating the Covariance Matrix of GMMs with Low-rank Perturbations", International Journal of Data Mining, Modelling and Management, Special issue on the best papers of IDEAL'10 (invited), pp 300--307. preprint (pdf).
    Summary: We present a method for using Gaussian Mixture Models (GMMs) efficiently using low rank perturbations to a diagonal covariance matrix. The full covariance matrix has O(d^2) free parameters and could be prone to overfitting as well as inefficient. The diagonal covariance matrix has O(d) parameters and is efficient but can be restrictive. The low rank perturbation to a diagonal covariance matrix has O(d) parameters, is efficient and offers a middle ground between full and diagonal covariance which can capture correlations but using linear (in d) parameters.
  7. (2011 WkgPap) C. Boutsidis Malik Magdon-Ismail, "Deterministic Feature Selection for k-means Clustering", submitted, 2011. (arXiv).
    Summary: We show that it is possible to reduce the feature dimension and provably obtain clusterings which are comparable to the good clusterings in the original dimension.
  8. (2011 WkgPap) Sanmay Das, Allen Lavoie, Malik Magdon-Ismail, "Pushing Your Point of View: Behavioral Measures of Manipulation in Wikipedia", 2011. (arXiv).
    Summary: We develop edit behavioral indices that capture change in behavior and show correlation between blocked (potentially manipulative) editors and adverse changes in this index.
  9. (2011 Conf) , M. Goldberg, J. Greenman, B. Gutting, Malik Magdon-Ismail, J. Schwartz, W. Wallace, "Toward Efficient Search for a Fragment Network in a Large Semantic Database", Proc.6th Annual Network Science Workshop, West Point, Oct 23-24 2011. pdf Talk: pdf.

  10. (2011 Conf) T. Desel, Malik Magdon-Ismail, H. Newberg, L. Newberg, B. Szymanski, and C. Varela, "A Robust Asynchronous Newton Method for Massive Scale Computing Systems", In the 2011 IEEE International Conference on Computational Intelligence and Software Engineering (CiSE 2011). Wuhan, China. December 9-11, 2011. pdf Talk: pdf.

  11. (2011 Conf) T. Desel, Malik Magdon-Ismail, L. Newberg, B. Szymanski, "Finding Protein Binding Sites Using Volunteer Computing Grids", Proc. 2nd International Congress on Computer Applications and Computational Science (CACS 2011), Bali, Indonesia, Nov 15-17 2011. pdf Talk: pdf.

  12. (2011 Conf) C. Boutsidis, P. Drineas, Malik Magdon-Ismail, "Sparse Features for PCA-like Regression", Proc. 25th Conference on Neural Information Processing Systems (NIPS 2011), Granada, Spain, Dec 13-15 2011. pdf (coming soon) Talk: pdf.

  13. (2011 Conf) C. Boutsidis, P. Drineas, Malik Magdon-Ismail, "Near-Optimal Column Based Matrix Reconstruction", Proc. 52nd IEEE Symposium on Foundations of Computer Science (FOCS 2011), Palm Springs, CA, Oct 23-25 2011. pdf (full version: arXiv). Talk: pdf.

  14. (2011 Conf) M. Goldberg, Malik Magdon-Ismail, S. Nambirajan, J. Thompson "Tracking and Predicting Evolution of Social Communities", Proc. 3rd IEEE International Conference on Social Computing (SocialCom2011), MIT, Boston, MA, Oct 9-11 2011. pdf. Talk: pdf.

  15. (2011 Conf) Malik Magdon-Ismail, J. Purnell "SSDE-CLuster: Fast Overlapping Clustering of Networks Using Sampled Spectral Distance Embedding and GMMs", Proc. 3rd IEEE International Conference on Social Computing (SocialCom2011), MIT, Boston, MA, Oct 9-11 2011. pdf. Talk: pdf.

  16. (2011 Conf) C. Hui, Malik Magdon-Ismail, W. Wallace, M. Goldberg "Aborting a Message Flowing Through Social Communities", Proc. 3rd IEEE International Conference on Social Computing (SocialCom2011), MIT, Boston, MA, Oct 9-11 2011. pdf. Talk: pdf.

  17. (2011 Conf) Mithun Chakraborty, Sanmay Das, Allen Lavoie, Malik Magdon-Ismail, Yonatan Naamad, "Instructor Rating Markets", (abstract only appeared) at Workshop on Social Computing and User Generated Content at the ACM Conference on Electronic Commerce, June 2011 and Proc. 2nd Conference on Auctions, Market Mechanisms, and Their Applications (AMMA), August 2011. pdf. Poster: pdf.

  18. (2011 Conf) Mithun Chakraborty, Sanmay Das, Malik Magdon-Ismail, "Near-Optimal Target Learning With Stochastic Binary Signals", Proc. 27th Conference on Uncertainty in Artificial Intelligence (UAI), Barcelona, Spain, July 14-17, 2011. pdf. Poster: pdf.

  19. (2011 Conf) Cindy Hui, Malik Magdon-Ismail, Mark Goldberg, William Wallace, "Effectiveness of Information Retraction", 1st IEEE International Workshop on Network Science (NSW 2011), West Point, NY, June 22-24, 2010. pdf. Poster: pdf.

  20. (2011 Conf) Sibel Adali, Xiaohui Lu, Malik Magdon-Ismail, Jonathan Purnell, "Prominence Ranking in Graphs with Community Structure", Proceedings of the Fifth International AAAI Conference on Weblogs and Social Media (ICWSM), July 2011. pdf. Poster: ppt.

2010:

  1. (2010 BkChap) Nathan Cole, Travis Desell, Daniel Lombranaa Gonzalez, Francisco Fernandez de Vega, Malik Magdon-Ismail, Heidi Newberg, Boleslaw Szymanski and Carlos A. Varela, "Evolutionary Algorithms on Volunteer Computing Platforms: The MilkyWay@Home Project", Bookchapter In F. Fernandez de Vega, E. Cantu-Paz (Eds.): Parallel and Distributed Computational Intelligence, SCI 269, pp. 63-90. Springer-Verlag Berlin Heidelberg 2010. preprint (pdf). Available at springer.com.

  2. (2010 Jrnl) Malik Magdon-Ismail, Konstantin Mertsalov, "A Permutation Approach to Validation", Statistical Analysis and Data Mining Special issue on the best papers of SDM'10 (invited), Vol. 3, No. 6, pp 361-380. preprint (pdf).
    Summary: We present a method for "estimating" the out-sample error (validation) using a permutation estimate. For classification, one can bound the out-sample error using a permutation complexity which is related to the permutation estimate. The permutation estimate, however, applies to classification, regression, multiclass, ... and can be extended to different error measures (other than squared error) -- the paper primarily focusses on classification and L2-regression. Our experiments show that the permutation estimate performs well for model selection, outperforming a variety of other model methods including LOO-CV and 10-fold CV. The permutation estimate general, easy to compute and efficient, relying only on being able to run the learning algorithm on data.
    Erratum: Rudiger Hewer, in his bachelor thesis graciously pointed out to me that the bound in Lemma 8 should be corrected by a factor of 2 which propagates to the error term in Theorem 5, which should be 5*sqrt(8/n...) instead of 3*sqrt(8/n...).
  3. (2010 Jrnl) Cindy Hui, Mark Goldberg, Malik Magdon-Ismail, William Wallace, "Simulating the Diffusion of Information: An Agent-based Modeling Approach", Special Issue on Agent-Directed Simulation, International Journal of Agent Technologies and Systems (invited paper, in press) pdf.
    Summary: We develop an agent based model for information diffusion in social networks based on information fusion, propagation and querying. We validate the model on real data from the San Diego wild fires evacuation in 2007.
  4. (2010 WkgPap) Aseem Brahma, Sanmay Das Malik Magdon-Ismail, "Comparing Prediction Market Structures, With an Application to Market Making", 2010. (arXiv).
    Summary: We develop a novel 2-d ball mechanism for comparing prediction market microstructures, and use it to compare two market makers LMSR and BMM.
  5. (2010 Conf) Costas Busch, Malik Magdon-Ismail, "Optimal Oblivious Routing in Hole-Free Networks", Proceedings of the 7th International Conference on Heterogeneous Networking for Quality, Reliability, Security, and Robustness (QShine), Houston, Texas, November 2010. (invited) pdf. Slides: ppt.

  6. (2010 Conf) Cindy Hui, Malik Magdon-Ismail, Mark Goldberg, William Wallace, "Importance of Ties in Information Diffusion", Extended Abstract, Workshop on Information In Networks (WIN), NY, NY, Sept 24-25, 2010. pdf. Poster: pdf.

  7. (2010 Conf) Cindy Hui, Malik Magdon-Ismail, Mark Goldberg, William Wallace, "Weak Ties and the Diffusion of Information in Dynamic Networks", NetSci 2010, poster presentation, Boston, MA. pdf. Poster: pdf.

  8. (2010 Conf) Malik Magdon-Ismail, "Permutation Complexity Bound on Out-Sample Error", Proc. 24th Annual Conference on Neural Information Processing Systems (NIPS), pages, Dec. 6-9, 2010. pdf. Poster: pdf.

  9. (2010 Conf) Travis Desell, Anthony Waters, Malik Magdon-Ismail, Boleslaw Szymanski, Carlos A. Varela, Matthew Newby, Heidi Newberg, Andreas Przystawik, David Anderson, "Accelerating the MilkyWay@Home Volunteer Computing Project with GPUs", 8th International Conference on Parallel Processing and Applied Mathematics, Part I (PPAM), pages 276-288 pdf. Slides: pdf.

  10. (2010 Conf) Goldberg, M. K., Kelley, S., Magdon-Ismail, M., Wallace, W., "Overlapping Communities in Social Networks", Proc. 2nd Confernence on Social Computation (SocialCom), pages 104-113, Aug 20-22, Minneapolis, Minnesota, 2010; also appeared in Proc. Workshop on Social Network Analysis (SNAKDD) at KDD, pages 43-52, July 25-28, Washington, DC, 2010 pdf. Slides: pdf.

  11. (2010 Conf) Jonathan Purnell, Malik Magdon-Ismail, "Approximating the Covariance Matrix with Low Rank Perturbations", Proc. 11th Int. Conf. on Intelligent Data Engineering and Automated Learning (IDEAL), 1-3 Sept., Paisley, Scotland, 2010. pdf. Slides: pdf.

  12. (2010 Conf) Goldberg, M. K., Hayvanovych, M., Magdon-Ismail, M., "Measuring Similarity between Sets of Overlapping Clusters", Proc. Workshop on Social Network Analysis (SNAKDD) at KDD, pages 62-68, July 25-28, Washington, DC, 2010 ; also appeared in Proc. Workshop on Social Intelligence (SIN) at SocialCom, pages 303-308, Aug 20-22, Minneapolis, Minnesota, 2010 pdf. Slides: pdf.

  13. (2010 Conf) Travis Desell, David P. Anderson, Malik Magdon-Ismail, Heidi Newberg, Boleslaw Szymanski, Carlos A. Varela, "An Analysis of Massively Distributed Evolutionary Algorithms", Proc. 2010 IEEE Congress on Evolutionary Computation (CEC), pages (to appear), Barcelona, Spain, July 18-23 2010. pdf. Slides: ppt.

  14. (2010 Conf) Travis Desell, Malik Magdon-Ismail, Bolek Szymanski, Carlos Varela, Heidi Newberg, David P. Anderson, "Validating Evolutionary Algorithms on Volunteer Computing Grids", Proc. 10th IFIP International Conference on Distributed Applications and Interoperable Systems (DAIS 2010), pages 29-41, Amsterdam, Netherlands, June 7-10 2010. pdf. Slides: ppt.

  15. (2010 Conf) Adali, S., Escriva, R., Goldberg, M. K., Hayvanovych, M., Magdon-Ismail, M., Szymanski, B. K., Wallace, W. A., Williams, G.M, "Measuring Behavioral Trust in Social Networks", Proc. International Conference on Intelligence and Security Informatics (ISI), pages 150-152, Vancouver, BC, May 23-26, 2010. pdf. Technical Report: pdf. Slides: pdf.

  16. (2010 Conf) Sanmay Das, Malik Magdon-Ismail, "Collective Wisdom: Information Growth in Wikis and Blogs", ACM Conference on E-Commerce (EC 2010), pages 231-240, June 7-8 , Cambridge Massachusetts, 2010. pdf. Slides: pdf.

  17. (2010 Conf) Cindy Hui, Mark Goldberg, Malik Magdon-Ismail, William Wallace, "Agent Based Simulation of Diffusion Warnings", Proc. Agent-Directed Simulation Symposium (ADS), Orlando FL, April 12-May 14, 2010. pdf. Slides: pdf. [Best Paper]

  18. (2010 Conf) Malik Magdon-Ismail, Konstantin Mertsalov, "A Permutation Approach to Validation", Proc. 10th SIAM International Conference on Data Mining (SDM), pages 882-983, Columbus Ohio, April 29-May 1, 2010. pdf. Slides: pdf. [Best paper, top 3]

2009:

  1. (2009 Jrnl) Ali Civril, Malik Magdon-Ismail "On Selecting a Maximum Volume Sub-Matrix of a Matrix and Related Problems", Theoretical Computer Science, Journal Version: postscript, pdf.
    Summary: We study the problem of selecting a set of columns of a matrix with maximum volume. This is useful in trying to construct representative columns of high "numerical rank", which may be of use in matrix reconstruction. We study the algorithmic problem, showing that it is NP-hard and inapproximable. We then study a natural greedy algorithm for this problem, giving a worst case approximation guarantee, also demonstrating a problem which almost achieves this worst case. The performance of greedy is considerably worse than the inapproximability result we prove, suggesting avenues for further work in strengthening the inapproximability result or finding better algorithms.
  2. (2009 Jrnl) Costas Busch, Malik Magdon-Ismail "Atomic Routing Games on Maximum Congestion", Theoretical Computer Science, Volume 410, Issue 36, Pages 3337-3347, 2009. Journal Version: postscript, pdf. (link to journal web version) Conference Version: AAIM 2006, ps, pdf.
    Summary: We study atomic routing games on networks in which players choose a path with the objective of minimizing the maximum congestion along the edges of their path. The social cost is the global maximum congestion over all edges in the network. We show that the price of stability is 1. The price of anarchy, PoA, is determined by topological properties of the network. In particular, PoA=O(L+logn), where L is the length of the longest path in the player strategy sets, and n is the size of the network. Further, K-1<=PoA<=c(K^2+log^2 n), where K is the length of the longest cycle in the network, and c is a constant.
  3. (2009 Conf) Travis Desell, Malik Magdon-Ismail, Bolek Szymanski, Carlos Varela, Heidi Newberg, Nathan Cole "Robust Asynchronous Optimization for Volunteer Computing Grids", Proc. 5th International Conference e-Science, pages 263-270, Oxford UK, Dec 7-9, 2009. pdf. Slides: ppt.

  4. (2009 Conf) Jonathan Purnell, Malik Magdon-Ismail "Learning American English Accents Using Ensemble Learning with GMMs", Proc. 8th International Conference on Machine Learning and Applications (ICMLA), pages 47-52, 2009. pdf. Slides: pdf.

  5. (2009 Conf) Christopher Wynnyk, Malik Magdon-Ismail "Pricing the American Option using Reconfigurable Hardware", Proc. 7th IEEE/IFIP Conference on Embedded and Ubiquituous Computing (EUC-2009) pages 532-536, 2009. pdf. Slides: pdf.

  6. (2009 Conf) Mark Goldberg, Malik Magdon-Ismail, Konstantin Mertsalov, "Models of Communication Dynamics for Simulation of Information Diffusion", Proceedings of Advances in Social Networks Analysis and Mining (ASONAM 2009), pages 44-49, 2009. pdf. Slides: ppt.

  7. (2009 Conf) Stephen Kelley, Mark Goldberg, Malik Magdon-Ismail, Konstantin Mertsalov,William Wallace, Mohammed Zaki "graphOnt: An Ontology Based Library for Conversion from Semantic Graphs to JUNG", Proceedings 2009 IEEE International Conference on Intelligence and Security Informatics, pages 170-172, 2009. pdf. Slides: pdf.

  8. (2009 Conf) Stephen Kelley, Mark Goldberg, Malik Magdon-Ismail, Konstantin Mertsalov "Stability of Individual and Group Behavior in a Blog Network", Proceedings 2009 IEEE International Conference on Intelligence and Security Informatics, pages 7-12, 2009. pdf. Slides: pdf.

  9. (2009 Conf) C. Hui, Malik Magdon-Ismail, Mark Goldberg, William A. Wallace "The Impact of Changes in Network Structure on Diffusion of Warnings", Proc. Workshop on Analysis of Dynamic Networks (SIAM International Conference on Data Mining), pages, 2009. pdf. Slides: pdf.

2008:

  1. (2008 Jrnl) Hung-Ching (Justin) Chen, Mark Goldberg, Malik Magdon-Ismail, William Wallace "Reverse Engineering an Agent-Based Hidden Markov Model for Complex Social Systems", International Journal of Neural Systems, pdf.
    Summary: We give heuristics for learning the parameters of a HMM describing dynamics of social groups in social networks. The input data are communications for the social network. The HMM is an agent based micro-law model which is highly interdependent. We apply our methodology to real data from blogs, newsgroups.
  2. (2008 Jrnl) Jeffery Baumes, Hung-Ching (Justin) Chen, Matthew Francisco, Mark Goldberg, Malik Magdon-Ismail, William Wallace "ViSAGE: A Virtual Laboratory for Simulation and Analysis of Social Group Evolution", ACM Transactions on Autonomous and Adaptive Systems (TAAS), postscript, pdf.
    Summary: We give a parameterised generative HMM model for social group evolution based on social capital theory, and demonstrate its potential for modeling of social groups in social networks. In particular, one may observe certain abrupt changes in the behavior of macroscopic properties such as the group size distribution as one continuously changes some of the parameters. Within this model we can reproduce many observed phenemona within the social science literature.
  3. (2008 Jrnl) Nathan Cole, Heidi Joe Newberg, Malik Magdon-Ismail, Travis Desell, Kristopher Dawsey, Warren Hayashi, Xinyang (Fred) Liu, Jonathan Purnell, Boleslaw Szymanski, Carlos Varela, James Wisniewski, "Maximum Likelihood Fitting of Tidal Streams with application to the Sagittarius Dwarf Tidal Tails", the Astrophysical Journal, Vol 683, pages 750-766 (2008). Journal Version: postscript, pdf. Conference Versions: eScience 2007 (pdf) . ISMIS 2005 (pdf).
    Summary: We give a maximum likelihood algorithm to identify streams in from SDSS like data. In particular, we use a cylindrical profile for the stream over small length scales and a Hernquist profile for the Milky Way halo. The algorithm finds the stream and separates it from the background halo, thus producing more accurate parameters of the stream and giving the first catalogue of stars extracted from the data to have the stream density profile. In general, we are studying the problem of separating geometric objects in spatial data bases.
  4. (2008 Conf) Nathan Cole, Heidi Joe Newberg, Malik Magdon-Ismail, Travis Desell, Boleslaw Szymanski, Carlos Varela, "Tracing the Sagittarius Tidal Stream with Maximum Likelihood", Proc. AIP Conference, Volume 1082, pages 216--220, December 5th, 2008. pdf. Slides: pdf.

  5. (2008 Conf) Ali Civril, Malik Magdon-Ismail "Deterministic Sparse Column Based Matrix Reconstruction via Greedy Approximation of SVD", Proc. 19th International Symposium on Algorithms and Computation (ISAAC), pages, December 2008. pdf. Slides: pdf.

  6. (2008 Conf) Sanmay Das, Malik Magdon-Ismail "Collective Wisdom: Information growth in Wikis and Blogs", NIPS Workshop "Beyond Search: Computational Intelligence for the Web", December 2008. ps, pdf. Poster: pdf.

  7. (2008 Conf) Sanmay Das, Malik Magdon-Ismail "Adapting to a Market Shock: Optimal Sequential Market-Making", Proc. Advances in Neural Information Processing Systems (NIPS), pages, December 2008. pdf (paper). pdf (supplementary material). Poster: pdf.

  8. (2008 Conf) Mark Goldberg, Stephen Kelley, Malik Magdon-Ismail, Konstantin Mertsalov, William Wallace "Communication Dynamics of Blog Networks", Proc. SIGKDD Workshop on Social Network Mining and Analysis, pages August, 2008. pdf. Slides: pdf.

  9. (2008 Conf) Mark Goldberg, Stephen Kelley, Malik Magdon-Ismail, Konstantin Mertsalov, "Stable Statistics of the Blogograph", Proc.Interdisciplinary Studies in Information Privacy and Security (ISIPS), pages, 2008. pdf. Slides: pdf.

  10. (2008 Conf) C. Hui, Malik Magdon-Ismail, Mark Goldberg, William A. Wallace "Micro-Simulation of Diffusion on Warnings", Proc. 5th Int. Conf. on Information Systems for Crisis Response and Management ISCRAM, pages 424-430, 2008. pdf. Slides: pdf.

  11. (2008 Conf) M. Hayvanovych, A. Hoonlor, M. Goldberg, S. Kelley, Malik Magdon-Ismail, K. Mertsalov, B. Szymanski, W. Wallace, "Discovery, analysis and monitoring of hidden social networks and their evolution", Proc. IEEE Conference on Technologies for Homeland Security, pages 1--6 May, Boston, 2008. pdf. Slides: pdf.

  12. (2008 Conf) Yingjie Zhou, Malik Magdon-Ismail, William A. Wallace, Mark Goldberg, "A Generative Model for Statistical Determination of Information Content from Conversation Threads", Proc. International Conference on Intelligencs and Security Informatics (ISI), pages 331--342 June 17-20, Taipei, Taiwan, 2008. pdf. Slides: pdf.

  13. (2008 Conf) Mark Goldberg, Stephen Kelley, Malik Magdon-Ismail, Konstantin Mertsalov, "A Locality Model of the Evolution of Blog Networks", Proc. International Conference on Intelligencs and Security Informatics (ISI), pages 191--193 June 17-20, Taipei, Taiwan, 2008. pdf. Slides: ppt.

  14. (2008 Conf) Baumes, Jeffery, Goldberg, Mark K., Malik Magdon-Ismail, Wallace, William "Discovering Hidden Groups in Communication Networks", Invited Book Chapter, in "Security Informatics and Terrorism: Patrolling the Web",NATO Science for Peace and Security Series, Sub-series D: Information and Communication Security, eds.Cecilia S. Gal and Paul B. Kantor and Bracha Shapira, NATO, pages 82--108. ps (preprint) , pdf (preprint).

2007:

  1. (2007 Jrnl) Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas, "Efficient Bufferless Packet Switching on Trees and Leveled Networks", Journal of Parallel and Distributed Computing, Volume 67 (2007), pages 1168-1186. Journal Version: postscript, pdf. Conference Versions: EUROPAR 2005 (Leveled), EUROPAR 2004 (Trees), ps, pdf. (Leveled) ps, pdf. (Trees)
    Summary: We give bufferless hot-potato style scheduling algorithms for trees and leveled networks. For leveled networks, we give centralized and distributed algorithms. The centralized algorithm has routing time within a logarithmic factor of optimal, and the distributed algorithm is a logarithmic factor worse than the centralized. For trees, we give deterministic and randomized algorithms. The deterministic algorithm applies to bounded degree networks and has routing time within a logaritmic factor of optimal. The randomized algorithm applies to arbitrary networks, and has routing time within a log-squared factor from optimal.
  2. (2007 Jrnl) Costas Busch, Malik Magdon-Ismail, Jing Xi, "Optimal Oblivious Path Selection on the Mesh", IEEE Transactions on Computers, Vol. 57, No. 5, pages 660-671 Journal Version: postscript, pdf. Conference Version: International Parallel and Distributed Processing Symposium (IPDPS), 2005, postscript, pdf.
    Summary: We give an oblivious algorithm for the d-dimensional mesh in which packets select their paths independently of each other. The stretch and congestion are both within O(d^2) from the optimal stretch and congestion attainable by oblivious algorithms, and for oblivious algorithms, the congestion is within a logarithmic factor from the optimal congestion attainable by non-oblivious algorithms. Our algorithm is randomized, and we show that significant randomization is required for any algorithm which attains near optimal congestion. In particular, we show that our algorithm uses at most a factor O(d) more bits per packet than any algorithm which attains a comparable congestion.
  3. (2007 Jrnl) Costas Busch, Malik Magdon-Ismail Fikret Sivrikaya, Bulent Yener "Contention-free MAC protocols for asynchronous wireless sensor networks", Distributed Computing, Vol. 21, No. 1, pages 23-42, 2008 Journal Version: ps, pdf. Conference Version: 18th Annual Conference on Distributed Computing (DISC), 2004, postscript, pdf.
    Summary: We study TDMA-based MAC protocols for asynchronous wireless sensor networks in very harsh environments. Specifically, the protocols are contention-free (avoid collisions), distributed and self-stabilize to topological changes in the network; any topological changes are contained, namely, affect only the nodes in the vicinity of the change; our protocols do not assume that nodes have a global time reference, that is, nodes may not be time-synchronized, and nodes may wake up in an arbitrary order. We also discuss how to accomodate clock skew, slot misalignment and inability for collision detection at a node.
  4. (2007 Jrnl) Volkan Isler, Malik Magdon-Ismail "Sensor Selection in Arbitrary Dimension", IEEE Transactions on Automation Science and Engineering (TASE), Vol. 5, No. 4, pages 651-660, 2008 ps, pdf.
    Summary: We address the problem of localizing an object in many dimensions by selecting a small number of sensors from which to obtain a measurement. We abstract a sensor measurement as a convex set in R^n and a localization as the intersection of all measurments available to the object. We show that a constant number of sensors is all that is required to obtain a constant factor approximation to the localization error obtained from using all the sensors. Instrumental in our proof is a new construction of an enclosing simplex of a convex polygon with bounded volume.
  5. (2007 Jrnl) Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas, "Universal Bufferless Packet Switching", Siam Journal on Computing, Volume 37, Issue 4, pages 1139-1162, 2007. Journal Version: ps, pdf. Conference Version: Workshop in Approximate and On-line Algorithms (WAOA), 2004, postscript, pdf.
    Summary: We give universal packet switching algorithms for bufferless networks, settling an open question regarding the possibility of optimal (to within poly-log factors) bufferless packet switching algorithms. Our argument is constructive and the algorithm is polynomial time. The main idea is to convert a bufferless scheduling problem with prespecified paths in a graph G to a new routing problem in a related graph G'. The problem in G' is solved using buffers, and the solution in G' is emulated in a deterministic bufferless manner in G to give the final bufferless schedule. Buffering in G' is emulated by packet circulation in regions of G.
  6. (2007 Jrnl) Malik Magdon-Ismail, and Joseph Sill "A Linear Fit Gets the Correct Monotonicity Directions", Machine Learning, Volume 70, Number 1 / January, 2008, pages 21-43. Journal Version: postscript , pdf. Conference Version: Conference on Learning Theory (COLT), 2003, postscript, pdf.
    Summary: It is often the case that learning with a monotonicity constraint is appropriate, however the directions of the monotonicity constraints may not be available in a general d-dimensional setting. One approach is to use a simple learning model to learn the monotonicity constraints, which can then be applied to constrain a more complex learning model. We show that the optimal linear fit can extract the correct monotonicity directions in one dimension, which remains true in multi-dimensions provided that the input distribution is of a Mahalanobis type. The same results remain true asymptotically when the the OLS estimator is used instead of the optimal linear fit.
  7. (2007 Jrnl) Sibel Adali, Brandeis Hill, Malik Magdon-Ismail, "Information vs. Robustness in Rank Aggregation: Models, Algorithms and a Statistical Framework for Evaluation", (accepted to appear in) Journal of Digital Information Management (JDIM), special issue on Web Information Retrieval pdf.
    Summary: We develop a statistical framework for studying ranker aggregation and a new algorithm for ranker aggregation based on a Kernigan-Lin style iterative best flip approach. We give experimental results for varying amounts of noise in the rankers as well as dis-similarity in the rankers (mis-information). In this space the optimal ranker can vary significantly, illustrating an information vs. robustness tradeoff for ranker aggregation.
  8. (2007 Conf) Hung-Ching (Justin) Chen, Mark Goldberg, Malik Magdon-Ismail and Al Wallace, "Reverse Engineering an Agent-Based Hidden Markov Model for Complex Social Systems", Proc. International Conference on Intelligent Data Engineering and Automated Learning (IDEAL), pages 940-949, December 16-19, Birmingham, UK, 2007. postscript, pdf. Slides: postscript, pdf.

  9. (2007 Conf) Hung-Ching (Justin) Chen, Mark Goldberg, Malik Magdon-Ismail and Al Wallace, "Discover The Power of Social and Hidden Curriculum to Decision Making: Experiments with Enron Email and Movie Newsgroups", Proc. International Conference on Machine Learning and Applications (ICMLA), pages 154--159, December 13-15, 2007, Cincinnati, Ohio, 2007. postscript, pdf. Slides: postscript, pdf.

  10. (2007 Conf) Travis Desell, Nathan Cole, Malik Magdon-Ismail, Heidi Newberg, Bolek Szymanski, Carlos Varela "Distributed and Generic Maximum Likelihood Evaluation", [Best paper Award, 2nd place] Proc. 3rd International Conference on e-Science and Grid Computing, pp , Bangalore, India, Dec 10-13, 2007. pdf. Slides: pdf.

  11. (2007 Conf) Hung-Ching (Justin) Chen, Mark Goldberg, Malik Magdon-Ismail and Al Wallace, "Learning What Makes a Society Tick", Proc. Worksop on Optimization-based Data Mining Techniques with Applications at the Seventh IEEE International Conference on Data Mining (ICDM), pages 195--200, October 28-31, Omaha, Nebraska, 2007. pdf. Slides: postscript, pdf.

  12. (2007 Conf) Fikret Sivrikaya, Costas Busch, Malik Magdon-Ismail, Bulent Yener "ASAND: Asynchronous Slot Assignment and Neighbor Discovery Protocol for Wireless Networks", OPNETWORK 2007, August 27-31,Washington DC. postscript, pdf. Slides: powerpoint,

  13. (2007 Conf) Hung-Ching (Justin) Chen, Mark Goldberg, Malik Magdon-Ismail and Al Wallace, "Inferring Agent Dynamics from Social Communication Network", Proc. Joint 9th Web Mining (WebKDD) and 1st Social Network Analysis (SNA-KDD) Workshop and KDD 2007, August 12-15, San Jose, CA, 2007. postscript, pdf. Slides: ppt,

  14. (2007 Conf) Hung-Ching (Justin) Chen, Mark Goldberg, Malik Magdon-Ismail and Al Wallace, "Extracting Agent Based Models from a Social Communication Network", Conference of Agent-based Modelers and Agent-based Modeling Platform Users (SwarmFest 2007), July 12-14, Chicago, IL USA, 2007. abstract(pdf), Slides: ppt,

  15. (2007 Conf) Yingjie Zhou, Mark Goldberg, Malik Magdon-Ismail and Al Wallace, "Strategies for Cleaning Organizational Emails with an Application to Enron Email Dataset", 5th Conf. of North American Association for Computational Social and Organizational Science (NAACSOS 07), Emory - Atlanta, Georgia , USA. June 7-9, 2007. postscript, pdf. Slides: ppt,

  16. (2007 Conf) Jeffery Baumes, Mark Goldberg, Mykola Hayvanovych, Stephen Kelley, Malik Magdon-Ismail Konstantin Mertsalov and Al Wallace, "SIGHTS: A Software System for Finding Coalitions and Leaders in a Social Network", Proc. 5th Conference on Intelligence and Security Informatics (ISI), May 23-24, Rutgers, NJ, 2007. postscript, pdf. Slides: postscript, pdf.

  17. (2008 Conf) Baumes, Jeffery, Goldberg, Mark K., Malik Magdon-Ismail, Wallace, William "Identification of Hidden Groups in Communications", Invited Book Chapter, in "Handbooks in Information Systems 2 (National Security)", Elsevier, eds. , pages 209--242. ps (preprint) , pdf (preprint). Technical Report

2006:

  1. (2006 Jrnl) Victor Boyarshinov, Malik Magdon-Ismail, "Efficient Optimal Linear Boosting of a Pair of Classifiers", IEEE Transactions on Neural Networks, Vol. 18, No. 2, pages 317-328, 2007. postscript, pdf.
    Summary: We relate the problem of boosting a pair of classifiers to an optimal weighted linear separation problem in two dimensions. We give efficient algorithms to perform this separation and compute the leave one out error. The main idea is to carefully enumerate the possible separators to finally obtain an O(n^2logn) algorithm, where n is the number of data points.
  2. (2006 Jrnl) Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas, Paul Spirakis "Direct Routing: Algorithms and Complexity", Algorithmica, Volume 45, Number 1, Pages 45--68, June 2006. (Invited submission from ESA 2004). Journal Version: postscript , pdf. Conference Version: European Symposium on Algorithms (ESA), 2004, postscript , pdf.
    Summary: We consider the direct routing problem, in which packets must follow pre-specified paths in a bufferless network. In this routing model, the only parameter to be determined for a packet is the injection time. We give a general greedy algorithm which has routing time O(C D), and we show that there are routing problems where this is the best achievable by a direct algorithm. We show that optimal direct routing is NP-hard to approximate by gap preserving reduction from graph coloring. We give versions of the greedy algorithm which have optimal or near optimal routing time for trees, multi-dimensional meshes, hypercubes and the butterfly. Finally, we use hard direct routing problems to obtain lower bounds on the buffering requirements of any algorithm that requires packets to follow pre-specified paths. If such algorithms obtain near optimal routing time, then packets must be buffered Omega(N^{1/3}) times (on average), where N is the number of packets.
  3. (2006 Conf) Hung-Ching (Justin) Chen, Malik Magdon-Ismail, "Learning Martingale Measures From High Frequency Finiancial Data to Help Option Pricing", 5th International Conference on Computational Intelligence in Economics and Finance (CIEF 2006) in conjunction with 9th Joint Conference on Information Sciences (JCIS 2006) October 8 - 11, Kaohsiung, Taiwan. postscript, pdf. Slides: postscript, pdf.

  4. (2006 Conf) Hung-Ching (Justin) Chen, Malik Magdon-Ismail, "NN-OPT: Neural Networks for Option Pricing Using Multinomial Trees", The 13th International Conference on Neural Information Processing (ICONIP2006), October 3-6, Hong Kong. postscript, pdf. Slides: postscript, pdf.

  5. (2006 Conf) Matthew Francisco, Jeffery Baumes, Hung-Ching Chen, Mark Goldberg, Malik Magdon-Ismail and Al Wallace, "Using Agent-Based Modeling to Traverse Frameworks in Theories of the Social", International Conference on Complex Systems (ICCS06), Boston, MA, June 25-30, 2006. postscript, pdf. Slides: postscript, pdf.

  6. (2006 Conf) Jeffery Baumes, Hung-Ching Chen, Matthew Francisco, Mark Goldberg, Malik Magdon-Ismail and Al Wallace, "Modeling the Cultural Subjectivity: Towards Computational Critique", 4th Conf. of North American Association for Computational Social and Organizational Science (NAACSOS 06), Notre-Dame, Indiana, June 22-23, 2006. postscript, pdf. Slides: postscript, pdf.

  7. (2006 Conf) Petros Drineas, Asif Javed, Malik Magdon-Ismail, Gopal Pandurangan, Reino Virrankoski, Andreas Savvides "Distance Matrix Reconstruction from Incomplete Distance Information for Sensor Network Localization", Third Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (IEEE SECON06), Sep. 25-28, Reston, VA, USA. postscript, pdf.

  8. (2006 Conf) Ali Civril, Malik Magdon-Ismail and Eli Bocek-Rivele, "SSDE: Fast Graph Drawing Using Sampled Spectral Distance Embedding", 14th International Symposium on Graph Drawing (GD2006), Karlsruhe, Germany, Sept 18-20, 2006. postscript, pdf. Slides: powerpoint.

  9. (2006 Conf) Jeffery Baumes, Hung-Ching Chen, Matthew Francisco, Mark Goldberg, Malik Magdon-Ismail, and Al Wallace "Social Capital Experiments", 4th Conf. of North American Association for Computational Social and Organizational Science (NAACSOS 06), Notre-Dame, Indiana, June 22-23, 2006. postscript, pdf. Slides: ps, pdf, powerpoint,

  10. (2006 Conf) Jeffery Baumes, Mark Goldberg, Mykola Hayvonovych, Malik Magdon-Ismail, William Wallace, Mohammed Zaki, "Finding Hidden Group Structure in a Stream of Communications", [Top 3 Paper Award] Proceedings of the 4th Symposium on Intelligence and Security Informatics (ISI 06), San Diego, CA, May 23-24 2006. postscript, pdf. Slides: ps, pdf,

  11. (2006 Conf) Costas Busch, Malik Magdon-Ismail, "Atomic Routing Games on Maximum Congestion", Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management (AAIM), Hong Kong, June 22-23, 2006. postscript, pdf. Slides: postscript, pdf.

  12. (2006 Conf) Sibel Adali, Brandeis Hill and Malik Magdon-Ismail, "The Impact of Ranker Quality on Ranker Aggregation Algorithms: Information vs. Robustness", Proc. ICDE Workshop on Challenges in Web Information Retrieval and Integration (WIRI), pp 10-19, Atlanta, Georgia, April 3, 2006. postscript, pdf. Slides: postscript, pdf.

2005:

  1. (2005 Jrnl) Malik Magdon-Ismail, Fikret Sivrikaya, Bulent Yener "Joint Problem of Power Optimal Connectivity and Coverage in Wireless Sensor Networks", Wireless Networks, Vol. 13, No. 4, pages 537-550, 2006. postscript , pdf.
    Summary: We model a node using a Markovian automaton which transitions between various modes which offer different capabilities and use power at different states. We develop a mean field theoretic analysis for the behavior of the system, which we optimize with respect to power consumption using connectivity and coverage as constraints. We apply the methodology to a 3 state automaton with off, listen and transmit states. We give results comparing the mean field theory analysis with a simulation, and we compare our approach with existing power saving approaches, which do not necessarily offer connectivity and coverage.
  2. (2005 Jrnl) Victor Boyarshinov, Malik Magdon-Ismail "Linear Time Isotonic and Unimodal Regression in the L1 and Linfinity Norms", Journal of Discrete Algorithms, Vol. 4, No. 4, pages 676-691, 2006. postscript , pdf.
    Summary: We give linear time algorithms for (unweighted) isotonic and unimodal regression in the Linfinity norm. For the L1 norm, we give linear time algorithms when the output values are in a bounded, finite set, and an approximation algorithm when the output values are in a bounded range. An open question that remains is to construct linear time isotonic regression in the L1 norm for the arbitrary case.
  3. (2005 Jrnl) Costas Busch, Malik Magdon-Ismail and Mukkai Krishnamoorthy "Hardness Results for Cake-Cutting", Bulletin of the European Association for Theoretical Computer Science, Number 86, pp. 85-106, June 2005. Journal Version: postscript , pdf. Conference Version: Symposium on the Theoretical Aspects of Computing (STACS), 2003, postscript, pdf.
    Summary: We consider the algorithm aspects of fair division of a resource, in which limited input from the users may be obtained regarding how much they value a certain part of the resource. If there are n users, it is known that a fair division of the resource (one in which no user thinks they have a less than 1/n of the resource) can be obtained using n logn cuts of the resource (which is modeled as the unit interval). No matching lower bound is available. We take a first step in this direction by showing (through reduction from sorting) that Omega(n logn) comparisons are made by any fair division algorithm. We also consider strong envy-free division (in which no user thinks she has a lesser share than any other user), and give lower bounds of Omega(n^2) on the number of cuts that must be made.
  4. (2005 Conf) Hung-Ching (Justin) Chen, Malik Magdon-Ismail, "Learning Martingale Measures to Price Options", 1st Workshop on Machine Learning in Finance at NIPS 2005 Vancouver/Whistler, Dec 9, 2005. postscript, pdf. Slides: postscript, pdf.

  5. (2005 Conf) Ali Civril, Malik Magdon-Ismail and Eli Bocek-Rivele, "SDE: Graph Drawing Using Spectral Distance Embedding", 13th International Symposium on Graph Drawing (GD05), Limerick, Ireland, Sept 12-14, 2005. postscript, pdf. Slides: postscript, pdf. powerpoint. Technical Report: postscript, pdf.

  6. (2005 Conf) Sibel Adali, Tina Liu and Malik Magdon-Ismail, "Optimal Link Bombs are Uncoordinated", First International Workshop on Adversarial Information Retrieval on the Web (AIRWeb 05) at the 14th International World Wide Web Conference (WWW2005), Chiba, Japan, 10-14 May, 2005. postscript, pdf. Slides: ps, pdf, powerpoint,

  7. (2005 Conf) Jeffery Baumes, Hung-Ching Chen, Matthew Francisco, Mark Goldberg, Malik Magdon-Ismail, and Al Wallace "Dynamics of Bridging and Bonding in Social Groups, a Multi-Agent Model", 3rd Conf. of North American Association for Computational Social and Organizational Science (NAACSOS 05), Notre-Dame, Indiana, June 26-28, 2005. postscript, pdf. Slides: ps, pdf, powerpoint,

  8. (2005 Conf) Jeffery Baumes, Mark Goldberg, Malik Magdon-Ismail, "Efficient Identification of Overlapping Communities", IEEE International Conference on Intelligence and Security Informatics (ISI 05), Atlanta, Georgia, May 19-20 2005. postscript, pdf. Slides: ps, pdf, powerpoint,

  9. (2005 Conf) Costas Busch, Malik Magdon-Ismail, Jing Xi "Oblivious Routing on Geometric Networks", 17th ACM Symp. on Parallelism in Alg. and Arch. (SPAA) 2005, July 17-20, Las Vegas, Nevada, USA. postscript, pdf. Slides: ps, pdf.

  10. (2005 Conf) Costas Busch, Shailesh Kelkar, Malik Magdon-Ismail "Efficient Bufferless Routing on Leveled Networks", EURO-PAR 2005, Aug 30-Sep 2, Lisboa, Portugal. postscript, pdf. Slides: postscript, pdf.

  11. (2005 Conf) Jonathan Purnell, Malik Magdon-Ismail, Heidi Newberg "A Probabilistic Approach to Finding Geometric Objects in Spatial Datasets of the Milky Way", 15th International Symposium on Methodoligies for Intelligent Systems (ISMIS 2005), May 25-28, Saratoga Springs, NY, USA. postscript, pdf. Slides: ps, pdf, powerpoint,

  12. (2005 Conf) Mark Goldberg, David Hollinger, Malik Magdon-Ismail "Experimental Evaluation of the Greedy and Random Algorithms for Finding Independent Sets in Random Graphs", 4th International Workshop on Efficient and Experimental Algorithms (WEA 2005), May 10-13, Santorini, Greece. postscript, pdf. Slides: postscript, pdf.

  13. (2005 Conf) Costas Busch, Malik Magdon-Ismail, Jing Xi "Optimal Oblivious Path Selection on the Mesh", International Parallel and Distributed Processing Symposium (IPDPS 2005), Apr 3-8, Denver, Colorado, USA. postscript, pdf. Slides: postscript, pdf.

  14. (2005 Conf) Jeffrey Baumes, Mark Goldberg, Mukkai Krishnamoorthy, Malik Magdon-Ismail, Nathan Preston "Finding Communities by Clustering a Graph into Overlapping Subgraphs", International Conference on Applied Computing (IADIS 2005), Feb 22-25, Algarve, Portugal. postscript, pdf, doc. Slides: ps, pdf, powerpoint,

  15. (2005 Conf) Seyit Ahmet Camtepe, Mark Goldberg, Malik Magdon-Ismail, Mukkai Krishnamoorthy "Detecting Conversing Groups of Chatters: A Model, Algorithms and Tests", International Conference on Applied Computing (IADIS 2005), Feb 22-25, Algarve, Portugal. postscript, pdf, doc. Slides: ps, pdf, powerpoint,

2004:

  1. (2004 Jrnl) Malik Magdon-Ismail, Amir F. Atiya, "Maximum Drawdown", Risk Magazine, Volume 17, Number 10, pages 99-102, October, 2004. postscript (preprint) , pdf (preprint). Print Version.
    Summary: We use some recent results on the behavior of the Maximum Drawdown of a Brownian motion to develop a scaling law for the Maximum Drawdown which allows one to compare the Sterling/Calmar ratios of trading strategies when the historical data available for the different trading strategies extends over different lengths of time.
  2. (2004 Jrnl) Malik Magdon-Ismail, Amir F. Atiya, Amrit Pratap, and Yaser S. Abu-Mostafa "On the Maximum Drawdown of a Brownian Motion", Journal of Applied Probability, Volume 41, Number 1, pages 147-161, March, 2004. Journal Version: postscript (preprint) , pdf (preprint). Print Version. Conference Version: Conference on Computational Intelligence for Financial Engineering (CIFEr), 2003, postscript, pdf.
    Summary: We develop the distribution for the Maximum Drawdown (largest drop from a peak to a bottom) of a Brownian motion. We compute the expected value as an infinite integral series. We reduce this function to a single "universal" function, which can be computed numerically once, and used to compute the expected drawdown for any Brownian motion. We compute the asymptotic behavior of this infinite series to reveal three regimes for the behavior of the MDD -- logarithmic, square-root and linear, depending on the sign of the drift parameter in the Brownian motion.
  3. (2004 Conf) Costas Busch, Malik Magdon-Ismail, Fikret Sivrikaya, Bulent Yener "Contention-Free MAC Protocols for Wireless Sensor Networks", 18th Annual Conference on Distributed Computing (DISC 2004), Oct 4-7, Amsterdam, the Netherlands. postscript, pdf. Slides: ps, pdf, powerpoint,

  4. (2004 Conf) Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas, "Universal Bufferless Routing", Workshop in On-line Algorithms (with ESA 2004 in conjunction with ALGO 2004), Sept 14-17, Bergen, Norway. postscript, pdf. Slides: ps, pdf, powerpoint,

  5. (2004 Conf) Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas, Paul Spirakis "Direct Routing: Algorithms and Complexity", 12th European Symposium on Algorithms (ESA 2004 in conjunction with ALGO 2004), Sept 14-17, Bergen, Norway. postscript, pdf. Slides: postscript, pdf.

  6. (2004 Conf) Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas, Roger Wattenhofer "Near-Optimal Hot Potato Routing on Trees", EURO-PAR 2004, 31 Aug-3 Sept, Pisa, Italy. postscript, pdf. Slides: ps, pdf, powerpoint,

  7. (2004 Conf) Hung-Ching Chen, Mark Goldberg, Malik Magdon-Ismail, "Identifying Multi-ID users in Open Forums", 2nd NSF/NIJ Symposium on Intelligence and Security Informatics (ISI 04), Tucson, AZ, June 11-12 2004. postscript, pdf. Slides: ps , pdf , powerpoint ,

  8. (2004 Conf) Jeffery Baumes, Mark Goldberg, Malik Magdon-Ismail, William Wallace "Discovering Hidden Groups in Communication Networks", 2nd NSF/NIJ Symposium on Intelligence and Security Informatics (ISI 04), Tucson, AZ, June 11-12 2004. postscript, pdf. Slides: ps, pdf, powerpoint,

2003:

  1. (2003 Jrnl) Malik Magdon-Ismail and Amir F. Atiya "A Maximum Likelihood Approach to Variance Estimation of a Brownian Motion Using the High, Low and Close", Quantitative Finance, volume 3, issue 5, pages 376 - 384, August 2003. Pre-print versions: postscript , pdf. Print version
    Summary: Since joint distribution of the high, low and close (conditioned on the open, drift and variance parameters) can be computed, we use this distribution to develop a likelihood for observing the high, low and close conditioned on the drift and variance parameters. By maximizing this likelihood, we construct an estimate of the variance parameter, which we compare to other well known estimators of variance parameter. Maximizing the likelihood yields a systematic gain in performance.
  2. (2003 Conf) Malik Magdon-Ismail and Joseph Sill "Using a Linear Fit to Determine Monotonicity Directions", The 16th Annual Conference on Learning Theory (COLT 2003), Washington, DC, USA, August 24-27 2003. ps pdf Slides: postscript, pdf.

  3. (2003 Conf) Mark Goldberg, Paul Horn, Malik Magdon-Ismail, Jessie Riposo, David Siebecker and William Wallace Bulent Yener "Statistical Modeling of Social Groups on Communication Networks", First conference of the North American Association for Computational Social and Organizational Science (CASOS 03), Pittsburgh PA, June 22-25, 2003. postscript, pdf. Slides: postscript, pdf.

  4. (2003 Conf) Malik Magdon-Ismail, Mark Goldberg, David Siebecker and William Wallace "Locating Hidden Groups in Communication Networks Using Hidden Markov Models ", NSF/NIJ Symposium on Intelligence and Security Informatics (ISI 03), Tucson, AZ, June 2-3 2003. postscript, pdf. Slides: postscript, pdf.

  5. (2003 Conf) Malik Magdon-Ismail, Amir Atiya, Amrit Pratap, and Yaser S. Abu-Mostafa "The Maximum Drawdown of the Brownian Motion", International Conference on Computational Intelligence for Financial Engineering (CIFEr 03), Hong Kong, March 2003. postscript, pdf. Slides: postscript, pdf.

  6. (2003 Conf) Malik Magdon-Ismail "Pricing the American Put Using a New Class of Tight Lower Bounds", International Conference on Computational Intelligence for Financial Engineering (CIFEr 03), Hong Kong, March 2003. postscript, pdf. Slides: postscript, pdf.

  7. (2003 Conf) Malik Magdon-Ismail, Costas Busch and Mukkai Krishnamoorthy "Cake-Cutting is Not A Piece of Cake", Symposium on the Theoretical Aspects of Computer Science (STACS 03), Berlin, February 27 - March 1, 2003. postscript, pdf. Slides: ps, pdf, powerpoint,

2002:

  1. (2002 Jrnl) Malik Magdon-Ismail and Amir F. Atiya "Density Estimation and Random Variate Generation Using Multi-Layer Networks", IEEE Transactions on Neural Networks, Volume 13, Number 3, pp 497--520, May 2002. Journal Version: postscript , pdf. Conference Versions: Advances in Neural Information Processing Systems (NIPS), 1998, postscript, pdf. (Density Estimation) Neural Networks for Signal Processing (NNSP99), 1999 postscript, pdf. (Control Theory Formulation of Random Variate Generation)
    Summary: We consider density estimation and random variate generation using neural networks. For density estimation, we give two methods, both based on learning the sample cumulative distribution function, one is randomized (SLC) and one is a deterministic interpolation using a smoothness constraint. We prove that the randomized algorithm converges to the deterministic version, asymptotically, however practically, randomization offers an additional smoothness property. We prove convergence of the deterministic algorithm to the true density given bounded derivative constraints on the true density.
  2. (2002 Conf) Malik Magdon-Ismail, Hung-Ching (Justin) Chen and Yaser S. Abu-Mostafa "The Multilevel Classification Problem and a Monotonicity Hint", Intelligent Data Engineering and Learning, Third International Conference, Manchester, UK, August, 2002. Springer. postscript, pdf. Slides: postscript, pdf.

  3. (2002 Conf) Malik Magdon-Ismail, Yu Shao, Daniel Freedman and Chris Bystroff "Compressing Protein Conformational Space", ISMB02: Tenth International Conference on Intelligent Systems for Molecular Biology, August 2002. postscript, pdf. (submitted, rejected)

  4. (2002 Conf) Yu Shao, Malik Magdon-Ismail, Daniel Freedman, Srinivas Akella, Mohammed Zaki and Chris Bystroff "Compressing Protein Conformational Space", RECOMB02: Sixth International Conference on Research in Computational Molecular Biology, April 2002 (poster). postscript, pdf. (abstract)

  5. (2002 BkChap) Malik Magdon-Ismail "Maximum Likelihood Estimation (MLE)", Book Chapter, to appear in "Encyclopedia of Financial Engineering and Risk Management", commissioning editor Gillian Lindsey, Fitzroy Dearborn Publishers, 2002. postscript , pdf.

  6. (2002 BkChap) Malik Magdon-Ismail "Ordinary Least Squares (OLS)", Book Chapter, to appear in "Encyclopedia of Financial Engineering and Risk Management", commissioning editor Gillian Lindsey, Fitzroy Dearborn Publishers, 2002. postscript , pdf.

  7. (2002 BkChap) Malik Magdon-Ismail "Expected Value / Mathematical Expectation", Book Chapter, to appear in "Encyclopedia of Financial Engineering and Risk Management", commissioning editor Gillian Lindsey, Fitzroy Dearborn Publishers, 2002. postscript , pdf.

2001:

  1. (2001 Jrnl) Malik Magdon-Ismail "The Equivalent Martingale Measure: An Introduction to Pricing Using Expectations", IEEE Transactions on Neural Networks, Volume 12, Number 4, pp 684-693, July 2001. postscript , pdf.
    Summary: We give an introduction to the Martingale measure, a tool for pricing options, which forml a link between pricing of financial derivatives and Monte Carlo simulation. We use this approach together with a limiting argument to give an elementary derivation of the price of the European call option, and discuss American options.
  2. (2001 Jrnl) Eric Breimer, Mark K. Goldberg, Brian Kolstad and Malik Magdon-Ismail "On the Height of a Random Set of Points in a d-Dimensional Unit Cube", Journal of Experimental Mathematics, Volume 10, Number 4, pp 583-597, 2001. Journal Version: postscript , pdf, source code. Conference Version: Workshop on Algorithm Engineering and Experiments (ALENEX), 2001, postscript, pdf.
    Summary: We give give efficient algorithms for estimating the height (maximum antichain) of a set of random points in a d-dimensional unit cube. The algorithms are based on a result we show which states that it suffices to consider only points near the diagonal of the cube. We develop efficient algorithms for generating these points directly, together with an efficient algorithm for constructing the height of this set. We use the co-convergence of estimates from different sized regions around the diagonal to the same value too develop an improved estimate. As a result, we give the first accurate estimates of c_d, the coefficients governing the convergence rate.
  3. (2001 Conf) Mark K. Goldberg, Darren T. Lim and Malik Magdon-Ismail "A Learning Algorithm for String Assembly", BIOKDD01: Workshop on Data Mining in Bioinformatics (with SIGKDD01 Conference), August 2001. postscript, pdf. Slides: postscript, pdf.

  4. (2001 Conf) Eric Breimer, Mark K. Goldberg, Brian Kolstad and Malik Magdon-Ismail "Experimental Evaluation of the Height of a Random Set of Points in a d-Dimensional Cube", 3rd Workshop on Algorithm Engineering and Experiments (ALENEX), January 2001. postscript, pdf. Slides: postscript, pdf.

2000:

  1. (2000 Jrnl) Malik Magdon-Ismail and Amir F. Atiya "The Early Restart Algorithm", Neural Computation, Volume 12, Number 6, pp 1303-1313, June 2000. postscript , pdf.
    Summary: We give an analysis of the early restart phenomenon which can be used to speed up an algorithm whose running time is a function of the initial conditions. For some initial conditions, the runtime may be excessively long or unbounded (for example local minima in an optimization). Given some probability distribution over which the initial conditions are sampled, there is some distribution for the stopping time of the process. We give a analysis of how using restart can improve the expected runtime, and develop a condition for selecting the optimal restart time. Essentially, if the algorithm has run for long enough, it may be favorable to restart the algorithm.
  2. (2000 Jrnl) Malik Magdon-Ismail "No Free Lunch for Noise Prediction", Neural Computation, Volume 12, Number 3, pp547-565, March 2000. postscript , pdf.
    Summary: We show that if the noise is additive, then the prior and posterior distributions of the noise are equal when the prior over target functions is uniform. There is no free lunch in the sense that if no useful assumptions can be made about the target function, then it is not possible gain any extra information regarding the nature of the noise.
  3. (2000 Conf) Malik Magdon-Ismail and Amir F. Atiya "Volatility Estimation Using High, Low and Close Data - A Maximum Likelihood Approach", Computational Finance (CF2000), Proceedings, June 2000. postscript, pdf.

  4. (2000 Conf) Malik Magdon-Ismail Amir F. Atiya, Yaser Abu-Mostafa "Pricing the quality option for the bond futures contract in a multifactor Vasicek framework", Proceedings of the 16th IMACS World Congress, Lausanne, Switzerland, August 2000. postscript, pdf.

1999 and before:

  1. (1998 Jrnl) Malik Magdon-Ismail, Alexander Nicholson and Yaser Abu-Mostafa, "Financial Markets, Very Noisy Information Processing", Proceedings of the IEEE, Special Issue on Intelligent Signal Processing, Volume 86, Number 11, pp 2184-2195, November 1998. postscript , pdf. addendum to definition A.1, postcript , pdf.
    Summary: We give a general characterization of the performance of a general class of learning systems. Specifically, when the learning system is stable (satisfies certain regularity conditions) and the noise is additive with bounded variance and the input distribution has compact support, the test performance approaches the optimal test performance at a universal rate of O(1/N), where N is the number of data points.
  2. (1999 Jrnl) Zehra Cataltepe, Yaser Abu-Mostafa and Malik Magdon-Ismail "No Free Lunch for Early Stopping", Neural Computation, Volume 11, Number 4, pp 995-1010, May 1998. postscript , pdf.
    Summary: We show that the success of early stopping is an artifact of training dynamics which tends to initialize the weights at smaller values and so the resulting function tends to have smaller magnitude weights, and hence tends to be smoother, which corresponds to having a smoothness prior on the target functions. When no such hidden prior assumption is made, i.e., when early stopping chooses uniformily among all hypotheses with the same (higher than optimal) error, we show that the resulting classifier has performance which is monotonically decreasing in the value of the early stopping error. Thus there is No Free Lunch for early stopping, in that it can only be succesfull if some bias is given toward the target function prior -- which means that some prior on the target function is necessary.
  3. (1998 Jrnl) Malik Magdon-Ismail and Yaser Abu-Mostafa, "Validation of Volatility Models", Journal of Forecasting, Volume 17, pp 349-368, 1998. Journal Version: postscript , pdf. Conference Version: Conference on Neural Networks in the Capital Markets (NNCM), 1996. postscript, pdf.
    Summary: We analyse some systematic errors in the prediction of volatility using Maximum Likelihood methods. In particular, there is a systematic underprediction even when the mean is predicted well. Further, Maximum Likelihood methods can systematically select the wrong model over the correct model, when faced with a choice of two models. We develop an expression for a correction factor for systematically correcting for this systematic underprediction.
  4. (1999 Conf) Malik Magdon-Ismail and Amir F. Atiya "A Control Formulation for Random Variate Generation", Neural Networks for Signal Processing (NNSP99) IX, Proceedings of the 1999 IEEE Workshop, eds. Yu-Hen Hu, Jan Larsen, Elizabeth Wilson, Scott Douglas, August 1999. postscript, pdf.

  5. (1999 Conf) Malik Magdon-Ismail and Amir Atiya, "A Bayesian Approach to Estimating Mutual Fund Returns", Computational Finance (CF99), eds Yaser S. Abu-Mostafa, Blake LeBaron, Andrew W. Lo and Andreas S. Weigend, MIT Press, 1999. postscript, pdf.

  6. (1998 Conf) Malik Magdon-Ismail and Amir Atiya, "Neural Networks for Density Estimation", Advances in Neural Information Processing Systems (NIPS) 11, Proceedings of the 1998 Conference, pp522-528, eds. Michael S. Kearns, Sara A. Solla and David A. Cohen, MIT Press, 1998. postscript, pdf.

  7. (1998 Conf) Malik Magdon-Ismail and Amir Atiya "Neural Networks for Density Estimation in Financial Markets", Intelligent Data Engineering and Learning, First International Symposium, pp 171-178, eds. L. Xu, L. W. Chan, I. King and A. Fu, Springer, October, 1998. postscript, pdf.

  8. (1998 Conf) Malik Magdon-Ismail, Alexander Nicholson and Yaser Abu-Mostafa, "Estimating Model Limitation in Financial Markets", Intelligent Data Engineering and Learning (IDEAL), First International Symposium, pp 19-26, eds. L. Xu, L. W. Chan, I. King and A. Fu, Springer, October, 1998. postscript, pdf.

  9. (1997 Conf) Zehra Cataltepe and Malik Magdon-Ismail "Incorporating Test Inputs into Learning", Advances in Neural Information Processing Systems (NIPS) 10, Proceedings of the 1997 Conference, pp 437-443, eds. Michael I. Jordan, Michael J. Kearns and Sara A. Solla, MIT Press, 1997. postscript, pdf.

  10. (1996 Conf) Malik Magdon-Ismail and Yaser Abu-Mostafa, "Systematic Underprediction of Volatility in Maximum Likelihood Methods", Decision Technologies for Financial Engineering, Proceedings of the Fourth International Conference on Neural Networks in the Capital Markets, NNCM 96 (currently Computational Finance), pp 125-137, eds. Andreas S. Weigend, Yaser S. Abu-Mostafa and A.-Paul N. Refenes, World Scientific, 1996. postscript, pdf.

  11. (1998 BkChap) Malik Magdon-Ismail, Alexander Nicholson and Yaser Abu-Mostafa, "Learning in the Presence of Noise", Book Chapter, in "Intelligent Signal Processing", eds. Simon Haykin and Bart Kosko, IEEE Press, 2001. postscript , pdf.