2021年运筹信息论坛

时间：2021年11月20日

地点：腾讯会议：575 323 436   密码：0266     

主办：中国科学院数学与系统科学研究院运筹信息研究室

 

 

Mining in Online Social Networks

李响，Santa Clara University

 

摘要：Online Social Networks (OSNs) are a rich repository of information. They have grown to billion scale with billions of nodes and edges. Also, the impact of certain actions like sharing, posting, and accepting friend requests in OSNs are not deterministic. With such big data and probabilistic actions, it becomes very challenging to mine the OSNs. In this talk, we address the above problems via two primary approaches: 1) Develop novel dynamic sampling techniques with the performance bound guarantee to exactly perform the big data mining in OSNs; and 2) Develop active learning methods to support more accurate decisions where decisions are made based on the outcomes of previous decisions. To confirm the practical uses of these mathematical techniques, we develop the first almost exact solution to an NP-complete problem, Influence Maximization, which can run on the billion scale Twitter network within 3 hours. Also, we propose a new model that the information propagation speed may change during diffusion and develop a solution with performance guarantee. The results of active learnings are used to not only unveil the near-optimal attack strategies of adaptive crawling, one of the most persistent attacks in OSNs, but also advance the research front of adaptive stochastic optimization, including: active learning with batch, adaptive theory under the matroids intersection, and providing the first tools to analyze greedy algorithms for optimization problems where the objective function is non-submodular. 

 

报告人简介： Xiang Li is currently a tenure-track Assistant Professor in the Department of Computer Science and Engineering in Santa Clara University. She received her Ph.D. degree from University of Florida, her research interests are centered on large-scale optimization and its intersection with cyber-security of networking systems, big data analysis, and cyber physical systems. More specifically, the focus of her research is to develop models, theories, and data-driven optimization algorithms for many computationally hard problems in Online Social Networks, Device-to-Device Networks, Internet of Things, and Smart Grids. She has published more than 30 articles in various prestigious journals and conferences such as IEEE/ACM Transactions on Networking, IEEE Transactions on Wireless Communications, IEEE Transactions on Mobile Computing, IEEE Transactions on Smart Grids, IEEE INFOCOM, IEEE ICDM, including Best Paper Awards in IEEE SocialSec 2018 and IEEE MSN 2014, and Best Paper Nominee at IEEE ICDCS 2017.

Xiang is an associate editor for Journal of Combinatorial Optimization and Computational Social Networks Journal. She has served as a reviewer for several journals such as IEEE Transactions on Knowledge and Data Engineering, IEEE Computer Magazine, IEEE Transactions on Mobile Computing, IEEE Transactions on Networks Science and Engineering, IEEE Internet of Things Journal and Journal of Combinatorial Optimization, etc. She is a recipient of many awards, including NSF CISE Research Initiation Initiative (CRII) award, UF Graduate School Fellowship, UF Informatics Institute Fellowship, UF Outstanding Merits Award, Travel Grant Awards at ACM SIGMETRICS, IEEE INFOCOM, IEEE ICDCS, IEEE ICDM, and IEEE INFOCOM Best-in-Section-Presentation Award.

 

 

Optimal Sales Strategies under Trade-in Programs for Quality Differentiated Recycled Products

杨磊，华南理工大学

 

摘要：To entice customers to purchase products，many firms offer different trade-in programs，including the traditional trade-in mode and trade-in mode that requires customers to pay an up-front fee. Since the up-front fee is non-refundable, whether or not to participate in the trade-in service can lead to different utility of customers, which will affect the customer's purchase decision. For the quality difference in returned products, the trade-in program with up-front fees can be divided into three types: only low quality (L), only high quality (H), both low quality and high quality (LH). This paper divides consumers in the market into two types: the primary consumer and the replacement consumer. First, a benchmark model, a traditional trade-in model and three trade-in models with up-front fees are construct used game theory, respectively. Then, analyzes the customer's purchase decision through the customer's utility function, obtain firm's optimal sales strategy and pricing decision. Finally, the five models are compared with each other. The results show that: (1) compared with the benchmark model, four trade-in models earn a higher profit and greater demand; when the consumers’ value discount for used product is relatively low, for the primary consumer market, the profit of trade-in models is lower than that of the benchmark model, for the replacement consumer market, the conclusion is the opposite; (2) among the four trade-in models, LH mode has the highest profit and the largest recycling quantity; (3) differences in up-front fees and quality of recycled products have a certain impact on the comparison between these models.

 

报告人简介： 杨磊，华南理工大学电子商务系教授、博士生导师。主要研究领域：智慧供应链、低碳运营管理、大数据优化等。主持和参与多个国家自然科学基金项目、教育部人文社科基金项目、广东省自然科学以及软科学项目。曾获得第八、九届广东省哲学社会科学优秀成果奖二等奖。近年来论文主要发表在《Production and Operations Management》、《European Journal of Operational Research》、《Transportation Research Part E》、《International Journal of Production Economics》、《International Journal of Production Research》、《Electronic Commerce Research and Applications》、《Applied Mathematical Modeling》、《Journal of Cleaner Production》、《Computers & Industrial Engineering》、《管理科学学报》、《系统工程理论与实践》、《中国管理科学》、《系统管理学报》等国内外知名期刊上。

 

 

非匹配数据的优化模型

都仁扎那，Clemson University

 

摘要： 单细胞基因组学产生了很多非匹配的数据，比如在一些细胞上测量基因表达，在另一些数据上测量染色质开放状态。我们目的是计算出两组特征之间的关联以及细胞-细胞的相似性。数据的非匹配特性给数据分析带来了很大的挑战。在这个报告中，我们讨论我们开发的非匹配数据的优化模型。在实际数据上应用显示我们的预测精度跟匹配数据上的结果不相上下。

 

报告人简介： 都仁扎那，2012-2017年在AMSS运筹室学习并获得博士学位。现在是美国Clemson University遗传与生化系的助理教授。研究方向为计算生物学。更多信息请见个人主页：https://durenlab.com/。

 

 

Generalized Network Dismantling via a Novel Spectral Partition Algorithm

亓兴勤，山东大学（威海）

 

摘要： Network dismantling problem aims to find a node subset whose removal from a network results in the fragmentation of the network into subcritical connected components at the minimal overall cost. People have always been more interested in the unweighted case where each node has the same cost, while there are few results for the weighted case when nodes have different costs. It is a much more challenging problem in network science. In this talk, we present a novel strategy for this generalized network dismantling problem by characterizing the relationship between blocks and cut nodes. We firstly construct an auxiliary block-cut-tree T from the original network G, where the nodes in the tree T have two types which correspond to either blocks or cut nodes of G, and edges of T only exist between two different type of nodes. Then we transform the problem of partitioning G by removing nodes to the problem of partitioning T by removing edges, both at a minimum overall cost. Finally partitioning T can be solved by a weighted spectral clustering algorithm. When we apply this new strategy on real-world networks, it performs equally or even better than the current state-of-the-art methods.

 

报告人简介： 亓兴勤，山东大学数学与统计学院教授，博士生导师。2006年6月毕业于山东大学数学学院运筹学与控制论专业，获理学博士。2009年5月至2011年5月期间，于美国西弗吉尼亚大学数学系做博士后研究，合作导师为Eddie Fuller及张存铨教授。2006年7月至今在山东大学数学与统计学院任教。目前主要从事图与复杂网络、数据挖掘等领域的研究。主要研究兴趣包括复杂网络中重要节点寻找问题，及复杂网络中社团结构划分问题等。目前为中国运筹学会图论与组合分会理事，中国工业与应用数学学会信息和通讯技术领域的数学专委会委员。 

 

 

Gene Regulation Inference using High Throughput Sequencing Data

刘丙强，山东大学数学学院

 

摘要： Reconstruction and analysis of transcriptional regulatory networks is a key to understand the intrinsic mechanism of the life. Currently, numbers of challenging questions in this research area need to be answered such as how the TFs regulate genes, how the genes be organized in transcription, and so on. High throughput sequencing data provides unprecedented opportunities to overcome these difficulties. Meanwhile, it also brings new computational and modeling challenges in high-dimensional data mining and heterogeneous data integration. To infer gene expression regulation mechanisms, we developed a series of computational frameworks focusing on several important computational problems including regulatory motif finding, regulon prediction, transcriptional unit prediction etc., both on bacterial and human genomes. These studies provided fundamental knowledge to guide the reconstruction and analysis of transcriptional regulatory networks, improved our understanding of how gene expression is controlled by the underlying regulatory systems, and have promising potentials on the research of regulatory mechanisms underlying complex diseases.

 

报告人简介： 刘丙强，山东大学数学学院教授、博士生导师，系统与运筹学研究所所长，院长助理。2003年毕业于山东大学数学学院基础数学专业，获学士学位。2010年毕业于山东大学数学学院运筹学与控制论专业，获博士学位。其间于2007年1月至2010年1月赴美国乔治亚大学联合培养。毕业后留山东大学数学学院从事教学科研工作。主要研究方向为利用图与组合优化的模型与理论针对基因表达调控中的系列计算问题进行算法设计与数据分析，包括转录因子结合位点计算预测、转录单元和调节子预测、调控网络构建与分析等。

 

 

Identifying Phenotype-associated Subpopulations by Integrating Bulk and Single-cell Sequencing Data

孙端辰，Oregon Health & Science University

 

摘要： Single-cell RNA sequencing distinguishes cell types, states, and lineages within the context of heterogeneous tissues. However current single-cell data cannot directly link cell clusters with specific phenotypes. Here we present Scissor, a method that identifies cell subpopulations from single-cell data that are associated with a given phenotype. Scissor integrates phenotype-associated bulk expression data and single-cell data by first quantifying the similarity between each single cell and each bulk sample. It then optimizes a regression model on the correlation matrix with the sample phenotype to identify relevant subpopulations. Applied to a lung cancer single-cell RNA-seq dataset, Scissor identified subsets of cells associated with worse survival and with TP53 mutations. In melanoma, Scissor discerned a T cell subpopulation with low PDCD1/CTLA4 and high TCF7 expression associated with an immunotherapy response. Beyond cancer, Scissor was effective in interpreting Facioscapulohumeral muscular dystrophy and Alzheimer’s disease datasets. Scissor identifies biologically and clinically relevant cell subpopulations from single-cell assays by leveraging phenotype and bulk-omics datasets.

 

报告人简介： Duanchen Sun was a postdoctoral associate in the Computational Biology Program at the Oregon Health &Science University. He got his Ph.D. degree at the Academy of Mathematics and Systems Science, Chinese Academy of Sciences in 2017. His current research field mainly focuses on mathematical modeling and novel computational methods design using high-throughput sequencing data. Such as building new tools for applications in single-cell sequencing data and designing novel network-based biomarker identification algorithms, etc.

 

 

Signaling Service Quality Through Queue Disclosure 

罗振伟，香港理工大学

 

摘要： In this paper, we consider a single-server queueing system whose service quality is either high or low. The server, who knows the actual quality level, can signal such quality information to customers via revealing or concealing his queue length. Based on this and the observed queue length in the case of a revealed queue, customers decide whether or not to join. A signaling game is formed, and we adopt the sequential equilibrium concept to solve our game and apply the perfect sequential equilibrium as an equilibrium-refinement criterion. In a basic model where customers are all uninformed of service quality, the pure-strategy perfect sequential equilibrium is always a pooling one except at several discrete values of the market size (measured by the potential arrival rate). When the markets size is below a threshold value, both high- and low-quality servers adopt queue concealment; otherwise, both types of the server adopt queue revelation. Then, we consider a general scenario in which the market is composed of both quality informed and uninformed customers. Under such a setting, when the server conceals his queue, we can fully characterize customers' equilibrium strategy and the corresponding effective arrival rate. The unique equilibrium outcome is still a pooling strategy when the market size is either below a lower threshold or above an upper threshold. And the separating equilibria may exist only when the market size falls between these two thresholds, under which uninformed customers can infer the server's quality type based on his queue disclosure behavior and thus behave in an informed way. Compared with the research tradition where the queue disclosure action is not regarded as a quality signal, such a signaling effect increases (resp. decreases) the effective arrival rate to the high-quality (resp. low-quality) server, and increases the total utility of all customers from the low-quality server.

 

报告人简介： Dr. Zhenwei Luo is now a research assistant professor in The Hong Kong Polytechnic University. He received his BS in information and computing science from Beijing Jiaotong University, MSc in operational research and cybernetics from University of Chinese Academy of Sciences, and PhD in Operations Management from The Hong Kong Polytechnic University. His research interests include inventory and supply chain management, queueing theory, and healthcare systems.

 

 

Solving Nonsmooth Nonconvex Compound Stochastic Programs with Applications to Risk Measure Minimization

刘俊驿，清华大学

 

摘要： In this talk, we study a structural compound stochastic program (SP) involving multiple expectations coupled by nonconvex and nonsmooth functions. We present a successive convex-programming based sampling algorithm and establish its subsequential convergence. We describe stationary properties of the limit points for several classes of the compound SP. We further discuss probabilistic stopping rules based on the computable error-bound for the algorithm. We present several risk measure minimization problems that can be formulated as such a compound SP; these include generalized deviation optimization problems based on the optimized certainty equivalent and multi-class classification problems employing the cost sensitive error criteria based on buffered probability of exceedance.

 

报告人简介： Junyi Liu is currently an assistant professor at the Department of Industrial Engineering at Tsinghua University. She obtained the Ph.D. degree in Industrial and Systems Engineering at the University of Southern California at 2019, and the B.S. degree in Statistics in the School of Gifted Young at the University of Science and Technology of China at 2015. She was a postdoctoral researcher working with Prof. Jong-Shi Pang from Sep 2019 till March 2021. Her research interests lie into the nondifferentiable and nonconvex stochastic optimization with intersections of machine learning and statistics.

 

 

Rainbow Disconnection Coloring of 2-trees

李碧，西安电子科技大学

 

摘要： Let G be a nontrivial connected, edge-colored graph. An edge-cut R of G is called a rainbow cut if no two edges in R are colored the same. An edge-coloring of G is a rainbow disconnection coloring if for every two distinct vertices u and v of G, there exists a rainbow cut in G, where u and v belong to different components of G ？ R. In this talk, we discuss recent progress on rainbow disconnection coloring of 2-trees.

 

报告人简介： 李碧，博士，西安电子科技大学副教授，分别于2014年在法国尼斯大学和2015年在中国科学院数学与系统科学研究院获得博士学位。研究兴趣包括图论与组合优化、算法复杂性与算法设计。主持国家自然科学基金青年项目、陕西省自然科学基础研究计划青年项目各一项。