Arxiv網路科學論文摘要7篇(2018-03-05)

03-14

網路科學研究速遞更新一周年了！

網路社區結構模型的過擬合與欠擬合評估;
社會網路中的影響的高階單調性和子模性：從局部到全局;
RankDCG：秩排序評估度量;
利用聚合手機數據理解人類流動情況;
NetGAN：通過隨機遊走生成圖;
偽分形無標度網路和謝爾賓斯基圖形中的獨立數和最大獨立集的個數;
用於可靠統計抽樣的稀疏冪律網路模型;

網路社區結構模型的過擬合與欠擬合評估

原文標題： Evaluating Overfit and Underfit in Models of Network Community Structure

地址： http://arxiv.org/abs/1802.10582

作者： Amir Ghasemian, Homa Hosseinmardi, Aaron Clauset

摘要：網路上常見的數據挖掘任務是社區檢測，它根據網路連接的統計規律尋求將網路無監督地分解為結構組。儘管存在許多方法，但社區檢測的免費午餐定理意味著每種方法都會做出某種折衷，並且沒有演算法可以在所有輸入上達到最優。因此，不同的演算法會在不同的輸入上過度或不適合，發現更多，更少或者僅僅是不同的社區而不是最優的，並且使用元數據分區作為基本事實的評估方法將產生關於一般準確性的令人誤解的結論。在這裡，我們對社區檢測中過度和不足的廣泛評估，比較了16個最新社區檢測演算法在406個真實世界網路的新穎和結構多樣化語料庫上的行為。我們發現：（i）在給定相同輸入的情況下，他們發現的社區數量及其相應構成的演算法差異很大;（ii）演算法可以根據其實時輸出的相似性聚類到不同的高級組中，（iii）這些差異會導致鏈路預測和鏈路描述任務的精度變化很大。我們引入了一種新的診斷方法來評估實踐中的過度擬合和不足，並將其用於將社區檢測方法大致分為通用和專業學習演算法。在各種方法和輸入中，基於隨機塊模型和最小描述長度方法的貝葉斯技術表示最佳的一般學習方法，但在特定情況下可能會表現優異。這些結果同時引入了一種理論上有原則的方法來評估網路社區結構模型的過度和不足以及可以評估和比較新方法的現實基準。

社會網路中的影響的高階單調性和子模性：從局部到全局

原文標題： Higher order monotonicity and submodularity of influence in social networks: from local to global

地址： http://arxiv.org/abs/1803.00666

作者： Wei Chen, Qiang Li, Xiaohan Shan, Xiaoming Sun, Jialin Zhang

摘要： Kempe，Kleinberg和Tardos（KKT）提出了關於社會網路中一般門限模型的以下猜想：局部單調性和子模數性意味著全局單調性和子模數性。也就是說，如果每個節點的閾值函數是單調和子模塊，那麼擴展函數$ sigma（S）$是單調和子模塊，其中S是一個種子集合，擴展函數$ sigma（S）$表示從S開始的擴散過程終止時的活動節點的預期數量。 Mossel和Roch證明了這個猜想的正確性。在本文中，我們首先提供了概念AD-k（交替差 - k）作為單調性和子模性的推廣。具體來說，如果所有輸入上f 的所有 ell -th階差分對每個$ ell都簽有$（ - 1）^ { ell + 1} $，那麼一個函數$ f $被稱為 adk leq k $。注意AD-1對應於單調性，而AD-2對應於單調性和子模數。我們提出了KKT猜想的改進版本：在一般閾值模型中，局部AD-k意味著全局AD-k。原始的KKT猜想對應於AD-2的情況，而AD-1的情況是局部單調性的平凡意味著全球單調性。通過利用集合函數的連續擴展以及社交圖結構，當社交圖是有向無環圖（DAG）時，我們證明了我們猜想的正確性。此外，當k= infty時，我們肯定了對一般社會圖的猜想。

RankDCG：秩排序評估度量

原文標題： RankDCG: Rank-Ordering Evaluation Measure

地址： http://arxiv.org/abs/1803.00719

作者： Denys Katerenchuk, Andrew Rosenberg

摘要：排名用於廣泛的問題，最顯著的是信息檢索（搜索）。評估排名的方法有很多，比如肯德爾的 tau，平均精確度和nDCG。在處理用戶排序或推薦系統等問題時，所有這些措施都會遇到各種問題，包括無法處理相同級別的元素，不一致和模糊的下限分數以及不適當的成本函數。我們提出了一個解決這些問題的新措施rankDCG。這是流行的nDCG演算法的修改。我們為任何有效的排名演算法提供了許多標準，並顯示只有rankDCG滿足所有這些演算法。結果顯示在構建的和真實的數據集上。我們發布了一個公開的rankDCG評估軟體包。

利用聚合手機數據理解人類流動情況

原文標題： Understanding Human Mobility Flows from Aggregated Mobile Phone Data

地址： http://arxiv.org/abs/1803.00814

作者： Caterina Balzotti, Andrea Bragagnini, Maya Briani, Emiliano Cristiani

摘要：在本文中，我們處理人口密集地區旅行流量和人群模式的研究。有關人員移動的信息是從粗粒度聚合蜂窩網路數據中提取的，而無需單獨跟蹤移動設備。行動電話數據由義大利電信公司TIM提供，並由不同時刻某一地區人員的密度分布（即空間分布）組成。通過計算兩個連續密度剖面之間的Wasserstein距離的合適近似值，我們能夠提取人們所遵循的主要方向，即了解人們在空間和時間中的分布情況。提出的技術的主要應用是監測通勤者的日常流量，組織大型活動以及更一般的交通管理和控制。

NetGAN：通過隨機遊走生成圖

原文標題： NetGAN: Generating Graphs via Random Walks

地址： http://arxiv.org/abs/1803.00816

作者： Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, Stephan Günnemann

摘要：我們建議NetGAN--圖的第一個隱式生成模型，能夠模擬真實世界的網路。我們將圖生成問題稱為學習輸入圖上偏向隨機遊動的分布。所提出的模型基於隨機神經網路，其生成離散輸出樣本並且使用Wasserstein GAN目標進行訓練。 NetGAN能夠生成展示眾所周知的網路模式的圖表，而無需在模型定義中明確指定它們。與此同時，我們的模型展現出強大的泛化特性，正如其競爭性鏈路預測表現所強調的那樣，儘管沒有專門針對此任務進行培訓。作為結合這兩種理想特性的第一種方法，NetGAN開啟了令人興奮的進一步研究途徑。

偽分形無標度網路和謝爾賓斯基圖形中的獨立數和最大獨立集的個數

原文標題： Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpi
ski gasket

地址： http://arxiv.org/abs/1803.00829

作者： Liren Shan, Huan Li, Zhongzhi Zhang

摘要：作為理論計算機科學的基礎課題，最大獨立集（MIS）問題不僅具有純粹的理論興趣，而且在各個領域也有廣泛的應用。但是，對於確定MIS大小的一般圖是NP難度的，並且精確計算所有MIS的數量更加困難。因此尋找可以準確解決MIS問題的特殊圖表是非常有意義的。在本文中，我們解決偽分形無標度網格和Sierpi nski墊片中具有相同頂點和邊數量的MIS問題。對於這兩個圖，我們都確定了所有可能的MIS的獨立數量和數量。偽分形無標尺網片的獨立編號是Sierpi nski墊片的兩倍。此外，偽分形無標度網具有獨特的MIS，而Sierpinski墊中MIS的數量隨著頂點的數量呈指數增長。

用於可靠統計抽樣的稀疏冪律網路模型

原文標題： Sparse power-law network model for reliable statistical sampling

地址： http://arxiv.org/abs/1803.00976

作者： A. Kartun-Giles, D. Krioukov, J.P. Gleeson, Y. Moreno, G. Bianconi

摘要：投影網路模型是一種能夠基於網路數據的子樣本進行預測的模型，如果考慮更大的樣本，則預測保持不變。可交換模型是不依賴於節點採樣順序的模型。儘管在網路科學中廣泛使用的各種各樣的非平衡（增長）和平衡（靜態）稀疏複雜網路模型，但如何將稀疏性（恆定平均度）與期望的統計性質的可預測性和可交換性協調起來，科學問題。在這裡我們提出一個隱含變數的網路過程，它是投射的，可以產生稀疏的冪律網路。儘管模型不可交換，但它可以與可交換的不相關網路密切相關，如其資訊理論特徵和網路熵所表明的那樣。這裡提出的網路過程作為空模型的使用在這裡對真實數據進行了測試，表明該模型為統計網路建模提供了一個有前途的途徑。

聲明：Arxiv文章摘要版權歸論文原作者所有，由本人進行翻譯整理，未經同意請勿隨意轉載。本系列在微信公眾號「網路科學研究速遞」（微信號netsci）和個人博客 https://www.complexly.me （提供RSS訂閱）進行同步更新。

網路社區結構模型的過擬合與欠擬合評估;
社會網路中的影響的高階單調性和子模性：從局部到全局;
RankDCG：秩排序評估度量;
利用聚合手機數據理解人類流動情況;
NetGAN：通過隨機遊走生成圖;
偽分形無標度網路和謝爾賓斯基圖形中的獨立數和最大獨立集的個數;
用於可靠統計抽樣的稀疏冪律網路模型;