摘要
随着信息科技的高速发展，各个应用领域的的信息量都呈现了爆炸性的增长趋势。因此，不同应用领域所关注的实体对象之间的关系也变得愈加庞大和复杂。在这些复杂关系的背后，往往蕴含着巨大的科学价值和商业价值。近年来，许多领域的研究者都开始专注于实体对象之间关系的研究。“图”作为计算机科学中一般性的数据结构，它可以很好的反映数据对象之间的复杂关系。因此，图数据被广泛地用来刻画现实世界中各种各样实体间的复杂关系。
然而，在现实世界中，实体对象间的关系每时每刻都在发生着变化。例如：在蛋白质交互网络中，各类蛋白质分子相互作用有着先后顺序，这使得整个蛋白质交互过程要随着时间顺序进行；在社会关系网络中，各类人和各类社会团体之间的交互关系会随着时间发生变化；在交通网络中，通过每条公路的时间和费用因交通拥塞的发生而随着时间发生变化。因此，描述实体间关系的图数据也会随着时间发生变化。
动态图是指会随时间发生变化的图数据。动态图可以根据其变化的形式分为两类：(1)图中拓扑结构关系发生变化；(2)图中顶点和边所代表数据对象内容、或者图中某一特定对象的评价方式发生变化。我们分别称之为图的结构变化和图的内容变化。由于动态图在现实世界中广泛存在，因此对动态图上各类问题的研究就有着十分重要的意义。然而，传统静态图数据上解决各类问题的算法无法用于解决动态图数据上的各类问题，主要有以下几个原因：第一，传统的静态图模型无法描述图数据随时间发生演绎与进化的情况；第二，传统的静态图模型上的各类问题的定义在动态图模型上不再适用；第三，图数据的动态性使得各类问题的计算复杂性大大增加，原有的静态图上的各类方法将无法有效地解决这些问题。此外，现有的动态数据管理的研究主要关注于数据流和传统关系数据的动态维护，这些方法无法处理结构复杂的图数据。
本文运用计算复杂性和算法学的理论和知识，分别对基于结构变化和基于内容变化的动态图上的相关问题开展了研究工作，主要研究成果如下：
(1)本文研究了动态图上结构变化最频繁子图挖掘问题，提出了一个基于“累积连通度变化”概念的评分函数来评价子图的结构变化的频繁程度。本文提出一个两段式算法来计算动态图中任意一对顶点之间的累积连通度变化。进一步地，本文提出一个基于“划分树”结构的算法挖掘目标子图，该算法逐步地将不属于目标子图中的顶点从全图中移除。本文分析了算法的时间复杂度和空间复杂度。真实数据上的实验结果表明，本文算法所挖掘到的子图在整个动态图中变化最频繁。同时，本文算法具有很高的的时间效率。
(2)本文研究了动态图上连通度变化最大的k-顶点集挖掘问题，提出了一种名为“连通等价类树”的结构，利用该结构可以高效地计算图中所有顶点对之间的连通度变化。本文提出了一个高效的连通等价类树构建算法和更新算法。其中，更新算法是一个逐边增量式算法，当动态图发生变化时，该算法只需要更新图中一小部分顶点之间的连通度即可完成连通等价类树的更新。本文证明，在相同的空间复杂度下，本文提出连通等价类树更新算法的时间复杂度远远小于现有最快的连通度更新算法。进一步地，本文提出一种分支界限算法和三种高效的剪枝策略用于挖掘连通度变化最大的k-顶点集。真实数据上的实验结果表明，本文算法所挖掘到的顶点子集可以良好的反映整张动态图中连通度变化情况，因此，其可以作为动态图连通关系变化的一个概括。同时，实验结果表明，本文中算法具有很高的时间效率。
(3)本文研究了多维代价图上动态最优路径查询问题。本文证明了多维代价图上动态最优路径查询问题是一个NP-难问题，并提出了一个分支界限算法和三种高效的剪枝策略用于计算动态最优路径。进一步地，本文提出了一种新的索引结构，k-簇索引，使得本文算法在大规模图上是时间高效和空间高效的。k-簇索引利用“contour skyline”加速查询进程。本文证明计算“contourskyline”是一个NP-难的问题，并提出一个2-近似的算法。本文证明了不存在近似比小于2的多项式时间算法。同时，本文提出一个顶点过滤算法，该算法可将图中大部分不属于最优路径的顶点过滤掉，进一步提高了算法效率。真实数据上的实验结果表明，本文算法具有非常高的时间效率和空间效率。
(4)本文研究了时间依赖图上满足时间限制的费用代价最优路径查询问题，提出了一个两阶段算法计算满足时间限制的费用代价最优路径。算法在第一阶段计算了起点到终点满足时间限制的最小费用代价，在第二阶段根据最小费用代价计算了起点到终点的最优路径。本文分析了查询算法的时间复杂度和空间复杂度。真实数据上的实验结果表明，本文提出的查询算法具有非常高的时间效率和空间效率。
With the development of information technology, the amount of information in eachapplication field presents explosive growth trend. The relationships among various enti-ties become more and more complex and there are the huge scientific value and commer-cial value behind them. Recently, people study the relationships among entities. Graph,as a general data structure in computer science, is a good way to describe the relationship-s among entities. Graphs have been widely used to model complex relationships amongvarious entities in real applications.
However, the relationships among entities often evolve over time. For example, inprotein interaction networks, proteins interact with each other in order, thus the relation-ships of interaction evolve over time. In social networks, the communication relationshipsamong people and communities also change with time. In addition, in road networks, thetime and toll fee through a road are time dependent. Therefore, graphs often evolve overtime.
Dynamic graphs are the graphs that evolve over time. They can be divided into t-wo categories:(1) the topologies of graphs change with time; and (2) the data contentrepresented by vertices or edges changes with time or the evaluation model for a specif-ic data object in graph changes with time. We call them topology change and contentchange respectively. Since there are many dynamic graphs in real applications, it is veryimportant to study the problems on dynamic graphs. However, the existing methods forstatic graphs cannot solve the problems on dynamic graphs. The reasons are as follows.First, the static graph model cannot describe the changes in dynamic graphs. Second,the problem definitions on static graphs are not suitable for dynamic graphs. Third, theinherent computational complexity of problems on dynamic graphs is extremely high, theexisting methods on static graphs cannot solve these problems efficiently and effectively.In addition, the existing methods about dynamic data focus on data stream and relationaldata maintenance, these methods cannot handle the complex graph data.
This thesis investigates the problems for topology dynamic graphs and content dy-namic graphs respectively, utilizing the knowledge of computational complexity theoryand algorithmic technology. The main contributions of this thesis are as follows.
(1) This thesis studies the problem of mining most frequently change componentfrom evolving graphs. An objective function based on “cumulated connectivity change”is proposed to measure the change frequency for a subgraph. A two-way algorithm isproposed to compute the cumulated connectivity change when graph evolves from a snap-shot to the next snapshot. Furthermore, an algorithm based on partition tree is proposedto mine the objective subgraph by removing the vertices not in this subgraph one by one.This thesis analyzes the time and space complexity for algorithms. The experimental re-sults on real-life datasets state the objective subgraph found by algorithm changes mostfrequently in the whole evolving graph and the algorithm is efficient and effective.
(2) This thesis studies the problem of mining k-vertex set with the maximum sumof connectivity change among vertices in this set. A new structure named “connectivitytree” is proposed, it can maintain the connectivity information efficiently for every pairof vertices in graphs. An algorithm is proposed to construct connectivity tree. Further-more, an efficient algorithm is proposed to update connectivity tree. This algorithm is anedge incremental algorithm. When graphs are evolving, by this algorithm, there is onlya small fraction of vertices among which the connectivity needs to be updated. A branchand bound algorithm with three efficient pruning rules is proposed to mine k-vertex set.The experimental results on real-life datasets confirm the k-vertex set can reflect and cap-ture the connectivity change in the whole evolving graphs effectively. Therefore, it canserve as a summary of connectivity change of dynamic graphs. The experimental resultsconfirm the efficiency and effectiveness of algorithms.
(3) This thesis studies the problem of dynamic optimal path over multi-cost graphs.The problem is proved to be NP-hard in this thesis and it cannot be solved by the exist-ing shortest path algorithms. A branch and bound algorithm with three efficient pruningrules is proposed to compute the optimal path. Furthermore, a novel “k-cluster index” isproposed to make our algorithm more efficient on large graphs. k-cluster index utilizes“contour skyline” to facilitate the optimal path query processing. The problem to com-pute contour skyline is proved to be NP-hard in this thesis. A2-approximate algorithm isproposed to compute contour skyline and we show there is no (2)-algorithm in polyno-mial time. Finally, a vertex-filter algorithm is proposed to enhance the efficiency, whichcan filter a large fraction of vertices not in the optimal path. The experimental results onreal-life datasets confirm the efficiency of algorithm.
(4) This thesis studies the problem of the cost-optimal path with time constraint over time-dependent graphs. A two-step algorithm is proposed to find the cost optimalpath with time constraint. In the first step, algorithm computes the minimum cost fromsource to destination. In the second step, algorithm finds the optimal path from sourceto destination. This thesis analyzes the time and space complexity for algorithm. Theexperimental results on real-life datasets confirm the efficiency of algorithm.
引文
[1]吴建平,林嵩,徐恪,等.可演进的新一代互联网体系结构研究进展[J].计算机学报,2012,35(6):1094–1108.
[2]于戈,谷峪,鲍玉斌,等.云计算环境下的大规模图数据处理技术[J].计算机学报,2011,34(10):1753–1767.
[3]周傲英,周敏奇,宫学庆.计算广告：以数据为核心的Web综合应用[J].计算机学报,2011,34(10):1805–1819.
[4] Fakcharoenphol J, Rao S. Planar Graphs, Negative Weight Edges, Shortest Paths,and Near Linear Time[C]//Proceedings of the42nd IEEE Annual Symposium onFoundations of Computer Science (FOCS’01). Las Vegas, Nevada, USA: IEEEComputer Society,2001:232–241.
[5] R. H M, Philip K, Satish R, et al. Faster Shortest Path Algorithms for PlanarGraphs[J]. Journal of Computer System and Science,1997,55(1):3–23.
[6] Surender B, Ramesh H, Sandeep S. Improved Decremental Algorithms for Main-taining Transitive Closure and All Pairs Shortest Paths[C]//Proceedings of the34thAnnual ACM Symposium on Theory of Computing (STOC’02). Montreal, Que-bec, Canada: ACM,2002:117–123.
[7] Frigioni D, Marchetti A, Nanni U. Semidynamic Algorithms for Maintaining Sin-gle Source Shortest Path Trees[J]. Algorithmica,1998,22(1):250–274.
[8] Frigioni D, Marchetti A, Nanni U. Fully Dynamic Output Bounded Single SourceShortest Path Problem[C]//Proceedings of the7th ACM-SIAM Symposium on Dis-crete Algorithms (SODA’96). Atlanta, Georgia, USA: ACM,1996:212–221.
[9] Ramalingam G, Reps T. An Incremental Algorithm for a Generalization of theShortest Path Problem[J]. Journal of Algorithms,1996,21(2):267–305.
[10] Frigioni D, Ioffreda M, Nanni U, et al. Experimental Analysis of Dynamic Algo-rithms for the Single Source Shortest Paths Problem[J]. Journal of Algorithmics,3(5):1–20.
[11] King V. Fully Dynamic Algorithms for Maintaining All Pairs Shortest Paths andTransitive Closure in Digraphs[C]//Proceedings of the40th Annual Symposiumon Foundations of Computer Science (FOCS’99). Washington, DC, USA: IEEEComputer Society,1999:81–91.
[12] Narva′ez P, Siu K Y, Tzeng H Y. New Dynamic Algorithms for Shortest Path TreeComputation[J]. IEEE/ACM Transactions on Networking,2000,8(6):734–746.
[13] Demetrescu C, Italiano G F. A New Approach to Dynamic All Pairs ShortestPaths[J]. Journal of the ACM,2004,51(6):968–992.
[14] Ren C, Lo E, Kao B, et al. On Querying Historical Evolving Graph Se-quences[C]//Proceedings of the37th International Conference on Very Large DataBases (VLDB’11). Seattle, WA, USA: VLDB Endowment,2011:726–737.
[15] Chan E P F, Yang Y. Shortest Path Tree Computation in Dynamic Graphs[J]. IEEETransaction on Computers,2009,58(4):541–557.
[16] Frederickson G N. Data Structures for Online Updating of Minimum SpanningTrees with Applications[J]. SIAM Journal of Computer.,1985,14(4):781–798.
[17] Eppstein D, Galil Z, Italiano G F, et al. Sparsification: a Technique for Speedingup Dynamic Graph Algorithms[J]. Journal of the ACM,1997,44(5):669–696.
[18] Henzinger M R, King V. Maintaining Minimum Spanning Trees in DynamicGraphs[C]//Proceedings of International Colloquium on Automata, Languages andProgramming (ICALP’97). Bologna, Italy: EATCS,1997:594–604.
[19] Even S, Shiloach Y. An Online Edge Deletion Problem[J]. Journal of the ACM,1981,28(1):1–4.
[20] Westbrook J, Tarjan R E. Maintaining Bridge Connected and Biconnected Com-ponents Online[J]. Algorithmica,7(5):433–464.
[21] Liang W, Brent R P, Shen H. Fully Dynamic Maintenance of Connectivity in Paral-lel[J]. IEEE Transaction on Parallel and Distributed System,2001,12(8):846–864.
[22] Dinitz Y, Nossenson R. Incremental Maintenance of the Five Edge ConnectivityClasses of a Graph[C]//Proceedings of the7th Scandinavian Workshop on Algo-rithm Theory (SWAT’00). London, UK: Springer Verlag,2000:272–285.
[23] Inokuchi A, Washio T. A Fast Method to Mine Frequent Subsequences from GraphSequence Data[C]//Proceedings of the8th IEEE International Conference on DataMining (ICDM’08). Pisa, Italy: IEEE Computer Society,2008:303–312.
[24] Robardet C. Constraint Based Pattern Mining in Dynamic Graphs[C]//Proceedingsof the9th IEEE International Conference on Data Mining (ICDM’09). Miami,Florida, USA: IEEE Computer Society,2009:950–955.
[25] Chan J, Bailey J, Leckie C. Discovering and Summarising Regions of Correlat-ed Spatio Temporal Change in Evolving Graphs[C]//Proceedings of the6th IEEEInternational Conference on Data Mining (ICDM’06). Hong Kong, China: IEEEComputer Society,2006:361–365.
[26] Borgwardt K M, Kriegel H P, Wackersreuther P. Pattern Mining in FrequentDynamic Subgraphs[C]//Proceedings of the6th International Conference on DataMining (ICDM’06). Hong Kong, China: IEEE Computer Society,2006:818–822.
[27] Bifet A, Gavalda`R. Mining Frequent Closed Trees in Evolving Data Streams[J].Intelligent Data Analysis,2011,15(1):29–48.
[28] Lahiri M, Berger T Y. Mining Periodic Behavior in Dynamic Social Network-s[C]//Proceedings of the8th IEEE International Conference on Data Mining (ICD-M’08). Pisa, Italy: IEEE Computer Society,2008:373–382.
[29]邹兆年,李建中,高宏,等.从不确定图中挖掘频繁子图模式[J].软件学报,2009,20(11):2965–2976.
[30]王爽,王国仁.面向不确定感知数据的频繁项查询算法[J].计算机学报,2013,36(3):571–581.
[31] Tantipathananandh C, Berger T Y, Kempe D. A Framework for Community Identi-fication in Dynamic Social Networks[C]//Proceedings of the13th ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining (KDD’07).San Jose, California, USA: ACM,2007:717–726.
[32] Tantipathananandh C, Berger T Y. Constant Factor Approximation Algorithms forIdentifying Dynamic Communities[C]//Proceedings of the15th ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining (KDD’09).Paris, France: ACM,2009:827–836.
[33] Aggarwal C C, Li Y, Yu P S, et al. On Dense Pattern Mining in Graph Stream-s[C]//Proceedings of the36th International Conference on Very Large Data Bases(VLDB’10). Singapore: VLDB Endowment,2010:975–984.
[34] Faloutsos M, Faloutsos P, Faloutsos C. On Power Law Relationships of the InternetTopology[C]//Proceedings of the Conference on Applications, Technologies, Ar-chitectures, and Protocols for Computer Communication (SIGCOMM’99). Cam-bridge, Massachusetts, USA: ACM,1999:251–262.
[35] Leskovec J, Kleinberg J, Faloutsos C. Graphs over Time: Densification Laws,Shrinking Diameters and Possible Explanations[C]//Proceedings of the11th ACMSIGKDD International Conference on Knowledge Discovery in Data Mining (KD-D’05). Chicago, Illinois, USA: ACM,2005:177–187.
[36] Sun J, Tao D, Faloutsos C. Beyond Streams and Graphs: Dynamic TensorAnalysis[C]//Proceedings of the12th ACM SIGKDD International Conference onKnowledge Discovery and Data Mining (KDD’06). Philadelphia, PA, USA: ACM,2006:374–383.
[37] Tong H, Papadimitriou S, Sun J, et al. Colibri: Fast Mining of Large Static andDynamic Graphs[C]//Proceedings of the14th ACM SIGKDD International Con-ference on Knowledge Discovery and Data Mining (KDD’08). Las Vegas, Nevada,USA: ACM,2008:686–694.
[38] Sun J, Faloutsos C, Papadimitriou S, et al. GraphScope: Parameter Free Miningof Large Time Evolving Graphs[C]//Proceedings of the13th ACM SIGKDD Inter-national Conference on Knowledge Discovery and Data Mining (KDD’07). SanJose, California, USA: ACM,2007:687–696.
[39] Shoubridge P, Kraetzl M, Wallis W D, et al. Detection of Abnormal Change ina Time Series of Graphs[J]. Journal of Interconnection Networks,2002,3(1):85–101.
[40] Schweller R T, Gupta A, Parsons E, et al. Reversible Sketches for Efficient andAccurate Change Detection over Network Data Streams[C]//Internet MeasurementConference. Taormina, Sicily, Italy: ACM,2004:207–212.
[41] Bunke H, Dickinson P J, Kraetzl M, et al. A Graph Theoretic Approach to Enter-prise Network Dynamics[M]. Boston: Birkha¨user,2007:67–81.
[42] Liu Z, Yu J X, Ke Y, et al. Spotting Significant Changing Subgraphs in EvolvingGraphs[C]//Proceedings of the8th IEEE International Conference on Data Mining(ICDM’08). Pisa, Italy: IEEE Computer Society,2008:917–922.
[43]邹兆年,高宏,李建中,等.演变图上的连接子图演变模式挖掘[J].软件学报,2010,21(5):1007–1019.
[44]张鹏程,李必信,李雯睿.时间属性序列图的语法和语义[J].软件学报,2010,21(11):2752–2767.
[45] Feigenbaum J, Kannan S, McGregor A, et al. Graph Distances in the Data StreamModel[J]. SIAM Journal on Computing,2008,38(5):1709–1727.
[46] Diehl S, Gorg C. Graphs, They Are Changing[J]. Lecture Notes in ComputerScience,2002,2528(1):23–31.
[47] Wang C, Chen L. Continuous Subgraph Pattern Search over Graph Stream-s[C]//Proceedings of the25th IEEE International Conference on Data Engineering(ICDE’09). Los Alamitos, CA, USA: IEEE Computer Society,2009:393–404.
[48] Aggarwal C C, Zhao Y, Yu P S. Outlier Detection in Graph Stream-s.[C]//Proceedings of the27th IEEE International Conference on Data Engineering(ICDE’11). Hannover, Germany: IEEE Computer Society,2011:399–409.
[49] Orda A, Rom R. Shortest Path and Minimum Delay Algorithms in Networks withTime Dependent Edge Length[J]. Journal of the ACM,37(3):607–625.
[50] Sung K, Bell M G H, Seong M, et al. Shortest Paths in a Network with Time Depen-dent Flow Speeds[J]. European Journal of Operational Research,2000,121(1):32–39.
[51] Kanoulas E, Du Y, Xia T, et al. Finding Fastest Paths on a Road Network withSpeed Patterns[C]//Proceedings of the22nd International Conference on Data En-gineering (ICDE’06). Atlanta, Georgia, USA: IEEE Computer Society,2006:1–10.
[52] Gonzalez H, Han J, Li X, et al. Adaptive Fastest Path Computation on a RoadNetwork: a Traffic Mining Approach[C]//Proceedings of the33rd InternationalConference on Very Large Data Bases (VLDB’07). Vienna, Austria: VLDB En-dowment,2007:794–805.
[53] Ding B, Yu J X, Qin L. Finding Time Dependent Shortest Paths over Large Graph-s[C]//Proceedings of the11th International Conference on Extending DatabaseTechnology: Advances in Database Technology (EDBT’08). Nantes, France:ACM,2008:205–216.
[54] George B, Shekhar S. Time Aggregated Graphs for Modeling Spatio-TemporalNetworks[C]//Proceedings of the3rd International Conference on Advancesin Conceptual Modeling for Geographic Information Systems (CoMoGIS’06).Berlin, Heidelberg: Springer Verlag,2006:85–99.
[55] Chabini I. Discrete Dynamic Shortest Path Problems in Transportation Applica-tions: Complexity and Algorithms with Optimal Run Time[J]. Transportation Re-search Records,1998,1645(1):170–175.
[56] Dehne F, Omran M T, Sack J R. Shortest Paths in Time Dependent FIFO NetworksUsing Edge Load Forecasts[C]//Proceedings of the2nd International Workshop onComputational Transportation Science (IWCTS’09). Seattle, Washington: ACM,2009:1–6.
[57] Pfoser D, Brakatsoulas S, Brosch P, et al. Dynamic Travel Time Provision for RoadNetworks[C]//Proceedings of the16th ACM SIGSPATIAL International Confer-ence on Advances in Geographic Information Systems (GIS’08). Irvine, Californi-a: ACM,2008:68–71.
[58] Pfoser D, Tryfona N, Voisard A. Dynamic Travel Time Maps Enabling EfficientNavigation[C]//Proceedings of the18th International Conference on Scientific andStatistical Database Management (SSDBM’06). Vienna, Austria: IEEE ComputerSociety:369–378.
[59] Dijkstra E W. A Note on Two Problems in Connexion with Graphs[J]. NumerischeMathematic,1959,1(1):269–271.
[60] Samet H, Sankaranarayanan J, Alborzi H. Scalable Network Distance Browsing inSpatial Databases[C]//Proceedings of the ACM SIGMOD International Conferenceon Management of Data (SIGMOD’08). Vancouver, Canada: ACM,2008:43–54.
[61] Xiao Y, Wu W, Pei J, et al. Efficiently Indexing Shortest Paths by Exploiting Sym-metry in Graphs[C]//Proceedings of the12th International Conference on Extend-ing Database Technology: Advances in Database Technology (EDBT’09). Saint-Petersburg, Russia: ACM,2009:493–504.
[62] Wei F. TEDI: Efficient Shortest Path Query Answering on Graphs[C]//Proceedingsof the ACM SIGMOD International Conference on Management of Data (SIG-MOD’10). Indianapolis, Indiana, USA: ACM,2010:99–110.
[63] Cheng J, Ke Y, Chu S, et al. Efficient Processing of Distance Queries in LargeGraphs: A Vertex Cover Approach[C]//Proceedings of the ACM SIGMOD Inter-national Conference on Management of Data (SIGMOD’12). Scottsdale, Arizona,USA: ACM,2012:457–468.
[64] Rice M N, Tsotras V J. Graph Indexing of Road Networks for Shortest Path Querieswith Label Restrictions[C]//Proceedings of the36th International Conference onVery Large Data Bases (VLDB’10). Singapore: VLDB Endowment,2010:69–80.
[65] Qiao M, Cheng H, Chang L, et al. Approximate Shortest Distance Computing: AQuery Dependent Local Landmark Scheme[C]//Proceedings of the22nd Interna-tional Conference on Data Engineering (ICDE’12). Washington, DC, USA: IEEEComputer Society,2012:462–473.
[66] Martins E Q V. On a Multicriteria Shortest Path Problem[J]. European Journal ofOperational Research,1984,16(2):236–245.
[67] Delling D, Wagner D. Pareto Paths with SHARC[C]//Proceedings of the8th Inter-national Symposium on Experimental Algorithms (SEA’09). Dortmund, Germany:Springer Verlag,2009:125–136.
[68] Mandow L, Perez D J. A New Approach to Multiobjective A*Search[C]//Proceedings of the19th International Joint Conference on ArtificialIntelligence (IJCAI’05). Edinburgh, Scotland: Morgan Kaufmann Publishers,2005:218–223.
[69] Chen L, Lian X. Dynamic Skyline Queries in Metric Spaces[C]//Proceedings ofthe11th International Conference on Extending Database Technology: Advancesin Database Technology (EDBT’08). Nantes, France: ACM,2008:333–343.
[70] Mouratidis K, Lin Y, Yiu M L. Preference Queries in Large Multi-cost Trans-portation Networks[C]//Proceedings of the26th International Conference on DataEngineering (ICDE’10). Long Beach, California, USA: IEEE Computer Society,2010:533–544.
[71] Wu D, Ke Y, Yu J, et al. Leadership Discovery When Data Correlatively Evolve[J].World Wide Web,2011,14(1):1–25.
[72] Cui Y, Pei J, Tang G, et al. Finding Email Correspondents in Online Social Net-works[J]. World Wide Web,2013,16(2):195–218.
[73] Yu Z, Zhou X, Zhang D, et al. Understanding Social Relationship Evolution byUsing Real World Sensing Data[J]. World Wide Web,2013,16(1):1–14.
[74] Musial K, Budka M, Juszczyszyn K. Creation and Growth of Online Social Net-work[J]. World Wide Web,2013,16(4):421–447.
[75] Musial K, Kazienko P. Social Networks on the Internet[J]. World Wide Web,2013,16(1):31–72.
[76]林闯,贾子骁,孟坤.自适应的未来网络体系架构[J].计算机学报,2012,35(6):1077–1093.
[77] Cormen T H, Leiserson C E, Rivest R L, et al. Introduction to Algorithms, SecondEdition[M]. Boston: The MIT Press and McGraw Hill,2001:643–651.
[78] Gomory R E, Hu T C. Multi-terminal Network Flows[J]. Journal of the Society ofIndustrial and Applied Mathematics,1961,9(4):551–570.
[79] Eppstein D, Galil Z, Italiano G F. Dynamic Graph Algorithms[J]. Algorithms andTheory of Computation,1(1):1–40.
[80] Bonchi F, Castillo C, Gionis A, et al. Social Network Analysis and Mining forBusiness Applications[J]. ACM Transactions on Intelligent Systems and Technol-ogy,2011,2(3):1–37.
[81] Brandes U, Erlebach T. Network Analysis Methodological Foundations[M].Berlin, Germany: Springer,2005:16–61.
[82] Newman M. An Introduction to Networks[M]. Oxford, United Kingdom: OxfordUniversity Press,2010:168–193.
[83] Freeman L C, Borgatti S P, White D R. Centrality in Valued Graphs: A Measure ofBetweenness Based on Network Flow[J]. Social Networks,1991,13(2):141–154.
[84] Alvarez J I, Gaston B M, Busch J R. Understanding Edge Connectivity in theInternet Through Core Decomposition[J]. Internet Mathematics,2011,7(1):45–66.
[85] Wasserman S, Faust K. Social Network Analysis: Methods and Applications[M].Cambridge, United Kingdom: Cambridge University Press,1994:169–177.
[86] White D R, Harary F, Sobel M, et al. The Cohesiveness of Blocks in Social Net-works: Node Connectivity and Conditional Density[J]. Sociological Methodology,2001,31(1):305–359.
[87] Flake G W, Lawrence S, Giles C L. Efficient Identification of Web Com-munities[C]//Proceedings of the6th ACM SIGKDD International Conference onKnowledge Discovery and Data Mining (KDD’00). Boston, Massachusetts, USA:ACM,2000:150–160.
[88]於志文,於志勇,周兴社.社会感知计算：概念、问题及其研究进[J].计算机学报,2012,35(1):16–26.
[89] Zhou F, Toivonen H, Mahler S. Network Simplification with Minimal Loss ofConnectivity[C]//Proceedings of the10th IEEE International Conference on DataMining (ICDM’10). Washington, DC, USA: IEEE Computer Society,2010:659–668.
[90] Toivonen H, Mahler S, Zhou F. A Framework for Path Oriented Network Simplifi-cation[C]//Proceedings of the9th International Conference on Advances in Intelli-gent Data Analysis (IDA’10). Tucson, AZ, USA: Springer Verlag,2010:220–231.
[91] Tian Y, Hankins R A, Patel J M. Efficient Aggregation for Graph Summariza-tion[C]//Proceedings of the ACM SIGMOD International Conference on Manage-ment of Data (SIGMOD’08). Vancouver, Canada: ACM,2008:567–580.
[92] Zhang N, Tian Y, Patel J M. Discovery Driven Graph Summariza-tion[C]//Proceedings of the26th International Conference on Data Engineering(ICDE’10). Long Beach, California, USA: IEEE Computer Society,2010:880–891.
[93] Tutte W T. An Introdution to Graph Theory[M]. Cambridge, United Kingdom:Cambridge University Press,2001:149–157.
[94] Gonzalez T F. Clustering to Minimize the Maximum Intercluster Distance[J]. The-oretical Computer Science,1985,38(1):293–306.
[95] Baus J, Kru¨ger A, Wahlster W. A Resource Adaptive Mobile Navigation Sys-tem[C]//Proceedings of the7th International Conference on Intelligent User Inter-faces (IUI’02). San Francisco, California, USA: ACM,2002:15–22.
[96] Terefe K. Nonlinear Transportation Problems[J]. Thesis Mathematics,2007,1(1):1–57.
[97] Hart P E, Nilsson N J, Raphael B. A Formal Basis for the Heuristic Determinationof Minimum Cost Paths[J]. IEEE Transaction on Systems Science and Cybernetics,1968,4(2):100–107.
[98] Goldberg A V, Harrelson C. Computing the Shortest Path: A*Search Meets GraphTheory[C]//Proceedings of the16th Annual ACM-SIAM Symposium on DiscreteAlgorithms (SODA’05). Vancouver, British Columbia: Society for Industrial andApplied Mathematics,2005:156–165.
[99] Goldberg A V, Kaplan H, Werneck R F. Reach for A*: Efficient Point to PointShortest Path Algorithms[C]//Proceedings of Workshop on Algorithm Engineeringand Experiments (ALENEX’06). Miami, Florida, USA: Society for Industrial andApplied Mathematics,2006:129–143.
[100] Shetty C M. A Solution to the Transportation Problem with Nonlinear Costs[J].Operation Research,1959,7(5):571–580.
[101] Ilich N, Simonovic S P. An Evolution Program for Nonlinear Transportation Prob-lems[J]. Journal of Heuristics,2001,7(2):145–168.
[102] Abourjeili A, Karypis G. Multilevel Algorithms for Partitioning Power LawGraphs[C]//Proceedings of the20th International Conference on Parallel and Dis-tributed Processing (IPDPS’06). Rhodes Island, Greece: IEEE Computer Society,2006:124–124.
[103] Dhillon I S, Guan Y, Kulis B. Weighted Graph Cuts without Eigenvectors: AMultilevel Approach[J]. IEEE Transactions on Pattern Analysis and Machine In-telligence,2007,29(11):1944–1957.
[104] Xu X, Yuruk N, Feng Z, et al. SCAN: a Structural Clustering Algorithm forNetworks[C]//Proceedings of the13th ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining (KDD’07). San Jose, California, USA:ACM,2007:824–833.
[105] Leape J. The London Congestion Charge[J]. Journal of Economic Perspectives,2006,20(4):157–176.
[106] Mahony M, Szeto W Y, Li X Q. Modeling Time Dependent Tolls under Trans-port, Land Use, and Environment Considerations[C]//Proceedings of the9th In-ternational Conference on Applications of Advanced Technology in Transporta-tion (AATT’06). Chicago, Illinois, USA: American Society of Civil Engineers,2006:852–857.
[107] Jiang L, Parekh S, Walrand J. Time Dependent Network Pricing and Band-width Trading[C]//Proceedings of Network Operations and Management Sympo-sium (NOMS’08). Salvador, Bahia, Brazil: IEEE Computer Society,2008:193–200.
[108] Cai X, Kloks T, Wong C K. Shortest Path Problems with Time Con-straints[C]//Proceedings of the21st International Symposium on MathematicalFoundations of Computer Science (MFCS’96). Cracow, Poland: Springer BerlinHeidelberg,1996:255–266.
[109] Cai X, Kloks T, Wong C. Time Varying Shortest Path Problems with Constraints[J].Networks,1997,29(3):141–150.
[110] Dean B. Algorithms for Minimum Cost Paths in Time Dependent Networks withWaiting Policies[J]. Networks,2004,44(1):41–46.