基于空間化PageRank算法的人口流動空間集聚性分析

鐘 斌 青，劉 湘 南

基于空間化PageRank算法的人口流動空間集聚性分析

鐘 斌 青，劉 湘 南＊

（中國地質大學（北京）信息工程學院，北京 100083）

提出了一種基于空間化PageRank算法的人口流動空間集聚性分析方法。在PageRank算法的基礎上增加空間節點間要素流量大小（F）的加權作用以及距離因子（Dst）所引起的流動成本和阻力效應，使該算法具備針對空間網絡模型的分析能力，通過對人口流動網絡模型中的節點進行集聚性排序，描述人口流動的空間特征。以華東六省一市人口流動狀況為例，PR值、區域人口總流入量（RTI）和流動人口密度區位商（MLQ）的計算結果對比表明：空間化PageRank算法可以客觀地評估空間節點吸引力，并彌補了總流入量等簡單人口學統計指標對于現象背后驅動機制表達不足的缺點。

空間化PageRank算法;人口流動;空間網絡模型;空間集聚性

0 引言

根據國家統計局發布的《2010年第六次全國人口普查主要數據公報（第1號）》，截至2010年，我國人口流動規模達2.61億人，占人口總數的19.04%，即在我國每5個人中就有1人屬于流動人口。而在未來二三十年內，根據預測，流動人口的總量仍將不斷增加。如此巨量的流動人口群體，緣于經濟增長大環境下區域間市場化改革程度、市場發育的空間不平衡性和我國二元分割的戶籍制度，而這種勞動力資源的大尺度空間流動，又會不斷地反作用于區域經濟發展及社會生活的各個層面，影響深遠。

關于人口流動空間特征描述的研究，早在1885年Ravenstein就曾繪制12幅地圖分析英國人口的各種空間流動特征［1］。近年來Rae等研究了借助于GIS的人口流動空間表達技術［2，3］，李薇等分別采用人口遷移選擇指數法、GIS空間相關性分析及綜合考慮凈遷移率和總遷移率的復合型指標進行中國人口流動的空間特征分析［4－6］。這些研究多選取傳統的人口學統計口徑，如流入人口、流出人口、凈流動人口或總流動人口等，亦有采用簡單指數的分析，如遷移率和人口遷移指數等。以上方法雖各具優勢，但對人口流動空間特征的深入挖掘及其驅動機制的分析尚有不足。特別是缺乏綜合表達人口流動在特定區域集聚特性的能力，不能客觀全面地比較人口集聚性的空間差異。

PageRank算法作為網頁排序算法，提供了一種解決此類問題獨辟蹊徑的可能思路。1998年，Google的創始人Sergey Brin和Lawren Page在斯坦福大學發明了PR算法［7］，對互聯網信息檢索產生了革命性的影響，并成為延續至今的搜索引擎核心技術。該算法在其他領域，如科技文獻質量評價［8］、生物學中蛋白質相互作用網絡的分析［9］等研究中亦有應用，但針對空間分析的研究則鮮見報道。Jiang把PR算法應用到城市空間的人口移動預測，卻未深入討論PR算法的空間化問題［10］。

PR算法的特征和關鍵優勢在于通過網頁間的“投票”機制，對網絡中海量的網頁進行排序，挖掘出最具價值的信息。這種“投票”機制同樣存在于人口流動現象中。人口學的眾多研究表明，人口流動背后的驅動機制主要是區域間的經濟發展不均衡所導致的推力與拉力作用。從另一個角度，人口是在用自己的遷移行為給區域“投票”。但網頁的排序與空間節點的排序之間存在一個巨大差異——空間性，即PR算法僅能分析網頁鏈接模型，而不具備對于空間網絡模型的分析能力。因此，本文主要探討PR算法應用于人口流動空間分析所需進行的空間化改進和擴展，并通過華東地區人口流動空間集聚性的分析，實際檢驗該算法效果。

1 PR算法及其空間化原理

1.1 PR算法原理

PR算法在網頁排序過程中通過超鏈接關系確定一個頁面的等級［11］。把從A頁面到B頁面的鏈接解釋為A頁面給B頁面投票，根據投票來源和投票目標的等級決定新的等級，簡言之，一個高等級的頁面可以提升其他低等級頁面的等級。可以假設一個由4個頁面組成的集合：A、B、C和D［12］（圖1a），如果所有的頁面都將網絡鏈接指向A，則A的PR值將是B、C及D的和。

圖1 PR算法中的網頁節點結構Fig.1 The structure of the Web pages in the PR algorithm

繼續假設B也與C有鏈接，并且D也有鏈接到包括A的3個頁面（圖1b）。一個頁面不能投票2次，所以B給每個頁面半票。以同樣的邏輯，D投出的票只有1/3算到了A的PR值上。

最后，所有的這些PR值被換算為一個百分比再乘以一個系數q。由于沒有頁面的PR值會是0，所以算法給每個頁面一個最小初始化值1－q。

所以一個頁面的PR值是由其他頁面的PR值計算得到的。算法不斷地重復計算每個頁面的PR值，如果在初始時給每個頁面分配一個隨機的PR值（非0），則經過不斷地重復計算，這些頁面的PR值會趨于正常和穩定，數學上可證明其收斂。

1.2 PR算法空間化

PR算法所針對的網頁鏈接模型（圖2）與人口流動的空間網絡模型（圖3）存在共性而又有細節上的差異。空間中各區域節點類同于網絡中的網頁，而從某個空間節點向另一個空間節點的人口流動又與網頁間的超鏈接類似。因而，可以套用PR算法分析空間節點間人口流動的集聚特性，即把區域節點間人口流動視為對節點的“投票”，觀察節點得分的多寡，分析空間節點在整個節點集合中對流動要素吸引力的強弱。但空間網絡模型相對網頁鏈接模型更為復雜，在把PR算法應用到空間網絡模型分析前，需克服原算法不具備空間性的缺陷，對其加入空間影響因子（如流量、距離等），使其空間化［13］。

空間化關鍵因子：1）流量。網頁鏈接模型中的超鏈接沒有流量概念，是純粹的布爾量，有鏈接為1，無鏈接則為0。但人口流動空間模型中，兩個空間節點間的人口流動具有量的大小，即從A地到B地具體有多少人進行了空間遷移。在算法“投票”過程中須考慮這一量值。具體的解決思路類似于普通PR算法中根據鏈接出度均分上一次計算的PR值。在此則根據流出節點的人口數按比例配給相應的PR值。2）距離。網頁鏈接模型存在于虛擬的互聯網中，不存在距離問題，但在人口流動環境下，距離直接構成對于流動最主要的成本和阻力。已有研究表明，人口在流動過程中由于經濟成本和思想觀念等原因，更趨于選擇較近的目的地進行空間遷移［14］。因此，在PR算法“投票”過程中，距離與“投票分值”呈正相關，即流動距離越大，其“投票分值”越高。

同樣假設4個空間節點A、B、C和D，以此為例對空間化改進后的PR算法進行逐步說明（圖4），算法中的各變量說明見表1。

圖4 空間化PageRank算法運算流程Fig.4 The process of spatialized PageRank algorithm

表1 算法變量說明Table 1 The algorithm variables

（1）初始化所有空間節點PR值，此處每個空間節點的PR值被初始化為1/4（圖2a）。

（2）目標節點的小分計算。以人口流出節點PR值為基礎，以該節點的流出人口總數均分其PR值，得到該節點每個流動單位實際持有的“投票能力”;然后，視流動到目標節點的流量FB-A為“流動單位

1

個數”計算投票;經由距離因子DstBk-A加權得到“投票分值”，同理計算SB-A、SC-A、SD-A（圖2b）。

（3）目標節點的總分計算。空間節點A的總得分S（A）即節點SB-A、SC-A和SD-A對其“投票”的總和。回調第2步，同理可得SB、SC、SD（圖2c）。

（4）對得分進行歸一化處理。計算單個節點得分占全部節點總分的比值，得到該節點的新PR值，此處理保證了在計算過程中，空間節點PR值介于0～1區間內，且所有節點PR值的和為1（圖2d）。

（5）進行邏輯判斷，該組PR值是否已達到穩定水平。如判斷為是，則得到結果;反之則以該組PR值為基礎繼續從步驟1開始循環，直至達到穩定條件為止。

2 華東地區人口流動空間集聚性分析

以華東地區六省一市（山東、江蘇、安徽、浙江、江西、福建和上海）為樣本，應用空間化PR算法分析這7個空間節點間的人口流動數據，并與傳統統計方法中普遍應用的兩個集聚性分析指數（區域人口總流入量和流動人口密度區位商）進行對比分析。

2.1 數據獲取

人口流動數據源于《第五次全國人口普查數據（2000年）》，各空間節點間距離數據取自鐵道部公布的六省會城市與上海市之間的鐵路旅程，各省市面積數據源于《2000年中國統計年鑒》。表2和表3分別為整理后的空間節點間人口流動數據和空間節點間距離數據。

表2 空間節點間人口流動量Table 2 Migration between the spatial nodes 人

表3 空間節點間距離Table 3 Distance between the spatial nodes km

2.2 數據計算

PR算法的實現選擇Microsoft Visual Studio 2005下的C＃開發環境。建立二維數組變量，存儲人口流量和空間距離原始數據，之后應用多層循環迭代方法，對數據進行空間化PR算法的運算處理。計算結果如表4所示，從第10次迭代運算開始，整個PR數組 開 始分 別 收 斂 于0.1031、0.2421、0.0517、0.1723、0.0516、0.1097和0.2694，且其總和為1。

表4 空間化PageRank算法的計算結果Table 4 The results of spatialized PageRank algorithm

作為對比指數，各空間節點流動人口總流入值根據表2按列求和得到，公式如下：

另一對比指數密度區位商計算公式如下：

式中：Qi為區域的密度區位商指數，Pi為區域的流動人口數，P為所有參與計算區域的流動人口數總和，ai為區域的面積，A為所有參與計算區域的總面積。

總流入與密度區位商的計算結果如表5所示。

2.3 結果分析

3種指數在空間上基本反映出了大體一致的客觀事實，但在細節上又存在差異。圖5作為3種指數的空間映射比較了這些差異，圖5a中連線的長短、粗細分別代表空間化PR算法所考慮的距離與流量因素，圖5c中深色填充表示區位商所計算的面積因素。

表5 區域總流入與密度區位商Table 5 RTI and MLQ results

圖5 PR、總流入與密度區位商的空間映射Fig.5 Space mapping of PR，RTI and MLQ

PR值與總流入值的比較（圖6）：二者的空間分布極其近似，都是以東部的上海市為中心向西深入內陸呈階梯狀遞減：上海為第一級階梯，江蘇和浙江次之，山東和福建構成第三級，安徽和江西為最后一級。這一結果符合勞動力資源對于經濟環境的選擇規律［15］，同時也證明了PR值作為空間集聚性分析指數的有效性。從圖5無法直接分辨PR值與總流入值的差別，但實際在同級階梯內部排名上卻存在差異。江蘇和浙江同為第二級階梯，在PR值方面，前者比后者要高，但其總流入值大小卻相反。同樣的情況還存在于山東和福建。這主要是由于PR值的計算不單純考慮人口流動量的大小，同時考慮了人口流動時距離成本和節點權重因子的緣故。

PR值與密度區位商的比較（圖7）：上海相對于其他空間節點具有絕對的高密度區位商值。因為密度區位商在計算時考慮區域面積因子，放大了最具空間集聚性的空間節點。圖7給出了PR值與其折線對比，密度區位商具有與PR值大體一致的空間節點相對趨勢，但明顯壓制了低值區域，凸顯高值。

此處空間化PR算法并未考慮區域面積，因此與密度區位商結果形成了較大的出入。區域面積抽象到PR算法的模型中，可被視為空間節點的容量，亦是一種空間網絡模型中的影響因子，即在節點容量較小的情況下，若流動要素依然表現出較大的進入量，則該空間節點的吸引力和集聚性應該被判斷為更高。

圖6 PR值與總流入值對比Fig.6 Difference between PR and RTI

圖7 PR值與密度區位商對比Fig.7 Difference between PR and MLQ

3 結論

針對人口流動的空間特征描述問題，本文基于計算機網絡搜索領域的PR算法，進行空間化改進，加入距離與流量因子，使該算法適應于空間網絡模型分析。華東地區人口流動空間集聚性分析結果表明：1）同為描述集聚性的指數，空間化PR值相對于區域總流入值，可以額外體現人口流動時的距離成本和流出地本身的權重等因素;2）由于符合客觀現象背后的復雜驅動機理與事實，該指數能更客觀地評估空間節點對于流要素的吸引力;3）與密度區位商的差異指出了另一空間化影響因子，即空間節點容量特征，可作為進一步研究的方向，同時證明了PR算法擁有豐富的空間化擴展性能。

空間化PR算法為人口流動空間集聚性分析提供了一種極具創新性的解決思路。而對于類似的空間網絡流動要素分析問題，如交通路網、商貿物流、通信網絡、移動終端位置軌跡等研究對象，在抽象出對應的空間網絡模型，并對PR算法施加針對性的空間化微調和擴展后，即可分析描述其空間特征并進行空間數據挖掘。因此，該技術具有較強的泛用性并值得深入研究。

［1］RAVENSTEIN E G.The laws of migration［J］.The Statistical Society of London，1885，48（2）：167－235.

［2］RAE A.From spatial interaction data to spatial interaction information？Geovisualisation and spatial structures of migration from the 2001 UK census［J］.Computer，Environment and Urban Systems，2009，33：161－178.

［3］PHAN D，XIAO L，YEH R，et al.Flow map layout［A］.Info Vis 2005，the Eleventh Annual IEEE Symposium on Information Visualization，2005.23－25.

［4］李薇.我國人口省際遷移空間模式分析［J］.人口研究，2008，32（4）：86－96.

［5］朱傳耿，顧朝林，馬榮華，等.中國流動人口的影響要素與空間分布［J］.地理學報，2001，56（5）：549－560.

［6］劉盛和，鄧羽，胡章.中國流動人口地域類型的劃分方法及空間分布特征［J］.地理學報，2010，65（10）：1187－1197.

［7］PAGE L，BRIN S.The anatomy of a lagre-scale hypertextual Web search engine［A］.Proceeding of the 7th International Conference on World Wide Web（WWW）［C］.1998.107－117.

［8］BOLLEN J，RODRIGUEZ M A，VAN DE SOMPEL H.Journal status［J］.Scientometrics，2006，69（3）：1030.

［9］IVAN G，GROLMUSZ V.When the Web meets the cell：Using personalized PageRank for analyzing protein interaction networks［J］.Bioinformatics，2011，27（3）：405－407.

［10］JIANG B.Ranking spaces for predicting human movement in an urban environment［J］.International Journal of Geographical Information Science，2009，23（7）：823－837.

［11］曹軍.Google的PageRank技術剖析［J］.情報雜志，2002（10）：15－18.

［12］黃德才，戚華春.PageRank算法研究［J］.計算機工程，2006，32（4）：145－146.

［13］XING W，GHORBANI A.Weighted PageRank algorithm［A］.Second Annual Conference on Communication Networks and Services Research（CNSR′04），2004.305－314.

［14］蔡昉，王德文.作為市場化的人口流動——第五次全國人口普查數據分析［J］.中國人口科學，2003（5）：11－19.

［15］嚴善平.中國省際人口流動的機制研究［J］.中國人口科學，2007（1）：71－77.

A Spatialized PageRank Algorithm for Migration Spatial Agglomeration Analysis

ZHONG Bin－qing，LIU Xiang－nan
（CollegeofInformationEngineering，ChinaUniversityofGeosciences（Beijing），Beijing100083，China）

In this paper，a spatialized algorithm based on PageRank for analyzing the migration spatial agglomeration is proposed.This algorithm considers the flow amount factor and the distance factor additionally.After being enhanced，it has the capacity to analyze a spatial network model，and then give a new solution to migration agglomeration analysis.By analyzing the migration condition of East China，thePR，Region Total Inflow（RTI）and Migration Location Quotient（MLQ）results shows that：the spatialized PageRank algorithm can objectively evaluate the node attractive force，and explain the driving mechanism behind the migration phenomenon which the traditional statistic index can′t.

spatialized PageRank algorithm;migration;spatial network model;spatial agglomeration

K901.3

A

1672－0504（2011）05－0082－05

2011－05- 20;

2011－07－16

國家高技術研究發展計劃（863）項目（2007AA12Z174）

鐘斌青（1987－），男，碩士，主要研究方向為空間信息分析與挖掘。＊通訊作者E－mail：liuxn＠163.com