李坤　白茹鑫　田立勤　薛小燕　欒尚敏

摘要：隨著物聯(lián)網(wǎng)、云計(jì)算的迅猛發(fā)展，大數(shù)據(jù)吸引了越來(lái)越多的關(guān)注，正在成為信息社會(huì)的重要財(cái)富。研究社團(tuán)成員間親密程度有助于了解社團(tuán)成員的社交影響力并方便對(duì)成員的工作協(xié)同提供指導(dǎo)。為保證社團(tuán)組織結(jié)構(gòu)調(diào)整的合理性以及工作配置的均衡性，有必要研究社團(tuán)成員間的親密程度以及社團(tuán)成員的影響力。運(yùn)用Python3.6進(jìn)行數(shù)據(jù)清洗和概化。通過(guò)numpy數(shù)組對(duì)上班時(shí)間和非上班時(shí)間的通話時(shí)長(zhǎng)、通話次數(shù)構(gòu)建矩陣，獲得不同星期數(shù)、不同時(shí)間點(diǎn)、不同城市以及不同社團(tuán)成員的通話次數(shù)分布情況。提出了多指標(biāo)綜合排序模型，調(diào)用networkx確定社團(tuán)成員間親密程度，形成社團(tuán)成員影響力網(wǎng)絡(luò)。采用GN算法檢測(cè)社團(tuán)結(jié)構(gòu)，對(duì)社團(tuán)成員進(jìn)行團(tuán)體劃分，多次聚類分析法對(duì)社團(tuán)負(fù)責(zé)城市進(jìn)行區(qū)域劃分。以主叫次數(shù)最多為依據(jù)設(shè)置各區(qū)域總部城市所在地。提出了基于方位角的位置排序法，通過(guò)球面距離公式計(jì)算分區(qū)負(fù)責(zé)人乘飛機(jī)遍歷所負(fù)責(zé)城市一遍花費(fèi)的最小時(shí)間。提出以社團(tuán)成員影響力確定分管城市負(fù)責(zé)人的新政策。

關(guān)鍵詞：社團(tuán)結(jié)構(gòu)；networkx；GN算法；聚類分析；位置排序法

中圖分類號(hào)：TP399? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2023）01-0049-04

1 引言

復(fù)雜網(wǎng)絡(luò)的研究在各個(gè)領(lǐng)域受到廣泛關(guān)注，并在計(jì)算機(jī)、數(shù)學(xué)、生物學(xué)等領(lǐng)域體現(xiàn)出很大的應(yīng)用價(jià)值。復(fù)雜網(wǎng)絡(luò)研究的關(guān)鍵是通過(guò)社團(tuán)結(jié)構(gòu)了解網(wǎng)絡(luò)性質(zhì)。很多學(xué)者正在對(duì)社團(tuán)結(jié)構(gòu)的提取方法進(jìn)行研究，例如Kernighan等人[1]研究對(duì)圖的剖分問(wèn)題，Newman[2]的研究引起了社團(tuán)檢測(cè)的研究熱潮。目前已經(jīng)出現(xiàn)了很多檢測(cè)方法，這些方法從機(jī)器學(xué)習(xí)角度看都是無(wú)監(jiān)督的方法。

模塊度用于定量的衡量社團(tuán)結(jié)構(gòu)的優(yōu)劣，其值越大，對(duì)應(yīng)的社團(tuán)結(jié)構(gòu)越好。因此模塊度經(jīng)常被作為目標(biāo)函數(shù)，經(jīng)過(guò)對(duì)其進(jìn)行優(yōu)化，盡力使其取得最大值，從而從網(wǎng)絡(luò)中提取最優(yōu)的社團(tuán)結(jié)構(gòu)。Guimera等人[3]將模塊度作為目標(biāo)函數(shù)，用模擬退火算法對(duì)其進(jìn)行優(yōu)化。Newman[4]應(yīng)用譜分析法對(duì)問(wèn)題進(jìn)行求解，得到最優(yōu)的社團(tuán)結(jié)構(gòu)。Newman[5]基于擴(kuò)展的模塊度矩陣，用同樣的方法將2個(gè)子網(wǎng)絡(luò)分別遞歸地進(jìn)行分裂，得到最終的社團(tuán)結(jié)構(gòu)。

2 數(shù)據(jù)挖掘

主要是運(yùn)用Python3.6，導(dǎo)入pandas、numpy以及matplotlib三個(gè)庫(kù)，挖掘數(shù)據(jù)信息。數(shù)據(jù)概化是一項(xiàng)前期基礎(chǔ)工作，即將已有數(shù)據(jù)轉(zhuǎn)換成適合進(jìn)行數(shù)據(jù)挖掘的形式。為了更便于進(jìn)行數(shù)據(jù)挖掘工作，對(duì)于數(shù)據(jù)中的“起始時(shí)間”列，采用時(shí)間序列確定星期數(shù)，并將通話時(shí)間點(diǎn)精確到小時(shí)。以10：08：51為例，經(jīng)過(guò)數(shù)據(jù)轉(zhuǎn)換精確到時(shí)，即10時(shí)。

建立during_onwork，times_onwork，during_offwork，times_offwork四個(gè)dataframe對(duì)象，分別表示上班時(shí)間的通話時(shí)長(zhǎng)、通話次數(shù)，下班時(shí)間的通話時(shí)長(zhǎng)、通話次數(shù)。通過(guò)numpy數(shù)組構(gòu)建矩陣，統(tǒng)計(jì)任意兩人在上班、非上班時(shí)間的通話時(shí)長(zhǎng)和通話次數(shù)，并將數(shù)據(jù)寫入Excel文件。通過(guò)數(shù)據(jù)挖掘，得到了不同星期數(shù)、不同時(shí)間點(diǎn)、不同城市以及不同社團(tuán)成員的通話次數(shù)分布統(tǒng)計(jì)圖，分別如圖1（a） ～（d） 所示。

由圖1（a） 可知，社團(tuán)成員在周四通話最頻繁，周四、周五和周六三天的通話次數(shù)接近，周日通話次數(shù)最少。由圖1（b） 可知，社團(tuán)成員通話總次數(shù)在一日內(nèi)出現(xiàn)4個(gè)活躍時(shí)間段，分別為8～10時(shí)，11～12時(shí)，13～16時(shí)，19～21時(shí)，其中13～16時(shí)為一天中的通話峰值段。圖1（c） 展示了通話次數(shù)排名前10的城市，影響力由大到小依次為白城、天水、大理、拉薩、徐州、錫林浩特、岳陽(yáng)、大連、天津以及蚌埠。圖1（d） 顯示了上班和非上班時(shí)間通話次數(shù)排名前10的社團(tuán)成員，其中蔡月通話次數(shù)居首位。

3 數(shù)學(xué)模型建立

提出了多指標(biāo)綜合排序模型。根據(jù)挖掘出的任意兩人上班、非上班時(shí)間通話次數(shù)和通話時(shí)長(zhǎng)信息，分別獲得每個(gè)個(gè)體上班、非上班時(shí)間的通話總次數(shù)和總時(shí)長(zhǎng)四項(xiàng)指標(biāo)。初始化變量，分別對(duì)各指標(biāo)進(jìn)行排序，如圖2所示，得到社團(tuán)成員各指標(biāo)排名，求和獲得綜合名次，綜合名次的數(shù)值越小，影響力越大。調(diào)用networkx，繪制社團(tuán)成員影響力網(wǎng)絡(luò)圖，如圖3所示，圖中粉紅色表示影響力前10名的社團(tuán)成員。

社交網(wǎng)絡(luò)能夠描述現(xiàn)實(shí)社會(huì)中人與人之間的社會(huì)關(guān)系，其中社團(tuán)結(jié)構(gòu)是表征社交網(wǎng)絡(luò)結(jié)構(gòu)特征的因素之一。采用了檢測(cè)社團(tuán)結(jié)構(gòu)的經(jīng)典算法——Girvan-Newman（GN）算法，其基本流程是首先計(jì)算網(wǎng)格中所有邊介數(shù)，即計(jì)算經(jīng)過(guò)網(wǎng)絡(luò)中每一條邊的最短路徑數(shù)目，其次需要找到邊介數(shù)最大的邊，從網(wǎng)絡(luò)中剔除，最后重新計(jì)算網(wǎng)絡(luò)中剩余邊的邊介數(shù)。重復(fù)上述兩個(gè)步驟，直至網(wǎng)絡(luò)中任一頂點(diǎn)作為一個(gè)退化的社區(qū)為止[6]。為把社團(tuán)成員分為2個(gè)或3個(gè)小團(tuán)體，調(diào)用GN算法，得到計(jì)算結(jié)果。部分程序如下：

from networkx.algorithms.community.centrality import girvan_newman

comp = girvan_newman（G）

comunities = tuple（c for c in next（comp））

comunities

print（comunities[0]）

print（comunities[1]）

comunity_list1 = []

comunity_list2 = []

names = adjacency_bool.index

for i in comunities[0]：

comunity_list1.append（names[i]）

for j in comunities[1]：

comunity_list2.append（names[j]）

print（comunity_list1）

print（comunity_list2）

計(jì)算結(jié)果表明，社團(tuán)成員被分為2個(gè)小團(tuán)體，畢婕靖、孟芳、凌慧雯、柯雅蕓、李熹俊、劉松荷、孫錦、林禮琴、高淼、駱?gòu)?、劉菁蕓、康蕓晴、陳斕和鐘倩為一個(gè)團(tuán)體，其余人為另一個(gè)團(tuán)體。

針對(duì)社團(tuán)調(diào)整組織架構(gòu)，主要通過(guò)采用多次聚類分析將社團(tuán)負(fù)責(zé)的139個(gè)城市分為3大區(qū)域。具體實(shí)現(xiàn)路徑為：首先分別提取出主叫地點(diǎn)“東經(jīng)”“北緯”信息和各主叫地點(diǎn)的主叫次數(shù)，整合信息到一個(gè)工作表，并進(jìn)行有無(wú)缺失值檢查，如果有缺失值，需進(jìn)行數(shù)據(jù)清洗。確定沒(méi)有缺失值后進(jìn)行第一次聚類分析，計(jì)算結(jié)果如圖4（a） 所示。

觀察圖4（a） 發(fā)現(xiàn)，區(qū)域分布點(diǎn)極不均勻，但存在明顯的分界線。為了保證區(qū)域分布的均衡性，對(duì)點(diǎn)密集區(qū)域進(jìn)行第二次聚類分析，計(jì)算結(jié)果如圖4（b） 所示。如圖4（c） 所示，經(jīng)過(guò)兩次聚類分析獲得了3大區(qū)域，分區(qū)1為含個(gè)舊的城市。最后，以主叫次數(shù)最多為依據(jù)設(shè)置了3大區(qū)域的總部城市所在地，分別為天水、白城和徐州。

根據(jù)任務(wù)均衡性和成員間的親密程度把該社團(tuán)的所有成員配置到 3 個(gè)分區(qū)中，分別提名各分區(qū)的負(fù)責(zé)人各一名。構(gòu)建36×139矩陣，獲得36名社團(tuán)成員個(gè)體分別在139個(gè)城市的通話次數(shù)。程序如下：

import pandas as pd

import numpy as np

import networkx as nx

from sklearn.cluster import KMeans

from matplotlib import pyplot as plt

plt.rcParams['font.sans-serif']=['STSong']

df = pd.read_excel（"附件.xlsx"）

counts_onwork = pd.read_excel（"上班時(shí)間通話次數(shù).xlsx"， index_col=0）

citys = pd.read_excel（'附件.xlsx'， sheet_name="Sheet2"， index_col=0）

locations = np.array（citys）

member_place = np.zeros（（36， 139）， dtype=int）

member_place = pd.DataFrame（member_place， index=counts_onwork.index， columns=citys.index）

for i in range（df.shape[0]）：

row = df.loc[i， "主叫"]

col = df.loc[i， "主叫地點(diǎn)"]

member_place.loc[row， col] += 1

利用Excel分別統(tǒng)計(jì)各社團(tuán)成員在3大分區(qū)的通話次數(shù)，篩選出各分區(qū)通話次數(shù)最多的成員作為分區(qū)負(fù)責(zé)人。潘立作為分區(qū)1（含個(gè)舊）負(fù)責(zé)人，蔡月和張培蕓作為另兩個(gè)分區(qū)負(fù)責(zé)人。

計(jì)算各分區(qū)負(fù)責(zé)人乘飛機(jī)遍歷所負(fù)責(zé)城市一遍花費(fèi)的最小時(shí)間，提出了基于方位角的位置排序法，如圖5所示。找到分區(qū)中經(jīng)度最小的城市，計(jì)算其他城市相對(duì)于該城市的北偏東方位角，對(duì)分區(qū)中所有點(diǎn)依據(jù)此方位角進(jìn)行排序，按順序?qū)υ摲謪^(qū)所有城市進(jìn)行遍歷，形成一條閉合回路。

依據(jù)球面距離公式計(jì)算，得到分區(qū)1的路線為 ['喀什'， '塔城'， '阿勒泰'， '阿克蘇'， '烏魯木齊'， '哈密'， '玉門'， '敦煌'， '張掖'， '銀川'， '青銅峽'， '德令哈'， '西寧'， '蘭州'， '格爾木'， '寶雞'， '天水'， '漢中'， '綿陽(yáng)'， '成都'， '重慶'， '宜賓'， '遵義'， '貴陽(yáng)'， '都勻'， '西昌'， '六盤水'， '攀枝花'， '昆明'， '憑祥'， '大理'， '個(gè)舊'， '和田'， '拉薩'， '畹町'， '日喀則']，用時(shí)為26.1小時(shí)。

分區(qū)2的路線為['呼和浩特'， '哈爾濱'， '鞍山'， '青島'， '二連浩特'， '同江'， '牡丹江'， '濟(jì)南'， '大連'， '長(zhǎng)春'， '雞西'， '天津'， '秦皇島'， '保定'， '濰坊'， '大同'， '四平'， '煙臺(tái)'， '石家莊'， '張家口'， '錦州'， '圖們'， '通化'， '營(yíng)口'， '錫林浩特'， '榮成'， '佳木斯'， '沈陽(yáng)'， '滿洲里'， '包頭'， '唐山'， '丹東'， '北京'， '承德'， '白城'， '海拉爾']，用時(shí)32.7小時(shí)。

分區(qū)3的路線為['南京'， '南寧'， '汕頭'， '武漢'， '上海'， '十堰'， '徐州'， '岳陽(yáng)'， '太原'， '榆林'， '沙市'， '寧波'， '無(wú)錫'， '九江'， '延安'， '合肥'， '南陽(yáng)'， '開封'， '揚(yáng)州'， '安慶'， '椒江'， '廈門'， '柳州'， '杭州'， '桂林'， '景德鎮(zhèn)'， '臨汾'， '宜昌'， '廣州'， '信陽(yáng)'， '南昌'， '三明'， '北海'， '安陽(yáng)'， '懷化'， '常德']，用時(shí)34.1小時(shí)。

針對(duì)新政策信息在該社團(tuán)網(wǎng)絡(luò)中的傳播機(jī)制，以建立的社團(tuán)成員影響力排名的數(shù)學(xué)模型為基礎(chǔ)，確定社團(tuán)成員的影響力，計(jì)算結(jié)果為：['蔡月'， '張培蕓'， '潘立'， '畢婕靖'， '張荊'， '曾帥'， '陳斕'， '孫翼茜'， '梁茵'， '鐘倩'， '易貞'， '劉松荷'， '李熹俊'， '吳宇曉'， '吳霄'， '高淼'， '柯雅蕓'， '彭荃'， '潘瀾巧'， '康蕓晴'， '謝斑尚'， '文芝'， '張庭琪'， '童豫'， '林禮琴'， '王蘊(yùn)姣'， '陸盈'， '涂蘊(yùn)知'， '孫怡毓'， '孫錦'， '孟芳'， '凌慧雯'， '劉菁蕓'， '廖顏翠'， '柳謂'， '駱?gòu)?]。以除去總部負(fù)責(zé)人以外的社團(tuán)成員的影響力順序通過(guò)任務(wù)均衡性和成員間的親密程度的解決思路確定分管城市的負(fù)責(zé)人。

4 結(jié)束語(yǔ)

本文通過(guò)建立數(shù)學(xué)模型研究成員的影響力和親密程度，為將來(lái)社團(tuán)的工作安排提供依據(jù)，通過(guò)對(duì)信息的挖掘，建立數(shù)學(xué)模型對(duì)社團(tuán)成員影響力進(jìn)行排名并將成員劃分為小團(tuán)隊(duì)。將社團(tuán)調(diào)整組織架構(gòu)，把負(fù)責(zé)的城市分為大區(qū)域并設(shè)置該分區(qū)的總部城市所在地。根據(jù)任務(wù)均衡性和成員間的親密程度把該社團(tuán)的所有成員配置到分區(qū)中，分別提名各分區(qū)的負(fù)責(zé)人各一名。計(jì)算各分區(qū)負(fù)責(zé)人乘飛機(jī)遍歷所負(fù)責(zé)城市一遍花費(fèi)的最小時(shí)間。研究新政策信息在該社團(tuán)網(wǎng)絡(luò)中的傳播機(jī)制，在新政策正式公布后，能使得新政策得到全面貫徹和執(zhí)行。

參考文獻(xiàn)

[1] Kernighan B W， Clauset A， Leicht E.Mixture models and exploratory analysis in networks[J].Proc Natl Ac ad Sci，2014，15（23）：64-68.

[2] Newman M E J，Girvan M，Leicht E.The structure and function of complex networks[J].SIAM Review，2013，45（2）：167-256.

[3] Guimera D A，Newman M E J，Derenyi.Detection community struction in netuorks[J].European Systems，2015，38（2）：321-330.

[4] Newman M E J.Structure and tie strengths in mobile communication networks[J].Proceedings of the National Academy of Sciences，2012，104（18）：32-73.

[5] Newman M E J.The large-scale organization of metabol-ic net-works[J].Nature，2016，407（6804）：651-654.

[6] 馬靜.基于社交網(wǎng)絡(luò)的社團(tuán)劃分算法研究[D].濟(jì)南：山東師范大學(xué)，2011.

【通聯(lián)編輯：謝媛媛】