ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
TRẦN THỊ PHƯƠNG
KHAI PHÁ MẠNG XÃ HỘI DỰA TRÊN CÁC BẢN GHI SỰ KIỆN HOẠT ĐỘNG CỦA DOANH NGHIỆP
Ngành: Công nghệ Thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 604805
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. HÀ QUANG THỤY
Hà Nội - 2015
2
LỜI CÁM ƠN
Lời đầu tiên, tôi xin chân thành cảm ơn sự hướng dẫn và chỉ bảo tận tình của PGS.TS. Hà Quang Thụy – người đã đưa ra định hướng khoa học và luôn quan tâm, động viên, thông cảm, tạo điều kiện thuận lợi cho tôi trong suốt quá trình thực hiện luận văn.
Tôi xin cảm ơn Phòng thí nghiệm Khoa học dữ liệu và Công nghệ Tri thức (DS&KTLab)và Đề tài cấp Đại học Quốc Gia Hà Nội, mã số QG.15.22 đã định hướng cho tôi trong đề tài nghiên cứu này.
Cuối cùng, tôi xin gửi lời cảm ơn tới các bạn bè đã giúp đỡ, hỗ trợ tôi cả về
mặt tinh thần và nền tảng kiến thức để tôi có thể hoàn thành luận văn.
Hà Nội, tháng 10 năm 2015
Trần Thị Phương
3
LỜI CAM ĐOAN
Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá nhân tôi, không sao chép lại của người khác. Trong toàn bộ nội dung của luận văn, những điều đã trình bày là của cá nhân tôi hoặc được tôi tổng hợp từ nhiều nguồn tài liệu. Tất cả các nguồn tài liệu tham khảo có xuất xứ rõ ràng và được trích dẫn hợp pháp.
Tôi xin chịu toàn bộ trách nhiệm và chịu mọi hình thức kỷ luật theo quy định
cho lời cam đoan của tôi.
Hà Nội, tháng 10năm 2015
Trần Thị Phương
4
MỤC LỤC
LỜI CÁM ƠN ................................................................................................................ 2
LỜI CAM ĐOAN .......................................................................................................... 3
DANH MỤC TỪ VIẾT TẮT ........................................................................................ 6
DANH MỤC BẢNG BIỂU ........................................................................................... 7
DANH MỤC HÌNH VẼ ................................................................................................. 8
MỞ ĐẦU ......................................................................................................................... 9
Chương 1. Những khái niệm cơ bản về nhật ký sự kiện và khai phá quy trình.... 11
1.1.
Khái niệm nhật ký sự kiện ............................................................................... 11
1.2.
Khai phá quy trình ........................................................................................... 12
Chương 2. Khai phá mạng xã hội .............................................................................. 15
2.1.
Trích xuất đồ thị quan hệ xã hội từ các bản ghi sự kiện .................................. 15
2.2.
Các độ đo trong xây dựng đồ thị quan hệ xã hội ............................................. 16
2.2.1. Độ đo dựa trên quan hệ nhân quả .......................................................... 17
2.2.2. Độ đo dựa trên trường hợp chung .......................................................... 24
2.2.3. Độđo dựa trên các hoạt động chung ...................................................... 25
2.3.
Phân tích mạng xã hội ...................................................................................... 27
2.3.1. Mật độ mạng .......................................................................................... 28
2.3.2. Độ gần .................................................................................................... 28
2.3.3. Độ trung tâm .......................................................................................... 29
2.3.4. Độ trung gian ......................................................................................... 31
Chương 3. Cải thiện độ đo trong xây dựng đồ thị quan hệ xã hội .......................... 33
3.1.
Đặt vấn đề ........................................................................................................ 33
3.2.
Giải pháp .......................................................................................................... 34
3.2.1. Đánh trọng số ......................................................................................... 34
3.2.2. Áp dụng trọng số chuyển giao vào công thức độ đo ............................. 36
5
Chương 4. Cài đặt, thực nghiệm ................................................................................ 37
4.1.
Công cụ MiSoN ............................................................................................... 37
4.2.
Thiết kế và cài đặt ............................................................................................ 39
4.2.1.
Thiết kế tổng thể .................................................................................... 39
4.2.2. Cấu trúc tệp nhật ký sự kiện đầu vào ..................................................... 41
4.2.3.
Thiết kế lớp ............................................................................................ 41
4.2.4.
Luồng hoạt động .................................................................................... 43
4.3.
Kết quả thực nghiệm ........................................................................................ 44
Kết luận ........................................................................................................................ 50
6
DANH MỤC TỪ VIẾT TẮT
Từ viết tắt Từ viết đầy đủ Diễn giải
Human resource management HRM
CRM
Customer relationship management Human resource Social Network analysis Hệ thống quản lý nguồn nhân lực Hệ thống quản trị quan hệ khách hàng Bộ phận quản lý nhân sự Phân tích mạng xã hội
HR SNA
7
DANH MỤC BẢNG BIỂU
Bảng 1.1 Một ví dụ nhật ký sự kiện tổng quát .................................................... 12
Bảng 1.2 Nhật ký sự kiện tổng quát đã sắp xếp theo từng trường hợp ............... 13
Bảng 2.1. Giá trị độ đo dựa trên sự chuyển giao công việc ................................ 21
Bảng 2.2. Ma trận tần xuất thực thi hoạt động .................................................... 25
Bảng 4.1 Bảng trọng số các hoạt động ................................................................ 47
Bảng 4.2. Ma trận trọng số khi bỏ qua chuyển giao công việc nhiều lần, bỏ qua chuyển giao gián tiếp ........................................................................................... 47
Bảng 4.3. Ma trận trọng số khi bỏ qua chuyển giao công việc nhiều lần, có tính tới chuyển giao gián tiếp ..................................................................................... 47
Bảng 4.4. Ma trận trọng số khi có tính tới chuyển giao công việc nhiều lần, bỏ qua chuyển giao gián tiếp .................................................................................... 48
Bảng 4.5. Ma trận trọng số khi có tính tới chuyển giao công việc nhiều lần, bỏ qua chuyển giao gián tiếp .................................................................................... 49
8
DANH MỤC HÌNH VẼ
Hình 1.1. Sơ đồ quy trình tuyển dụng ................................................................. 11
Hình 1.2. Sơ đồ quy trình dạng lưới Petri cho nhật ký sự kiện tổng quát .......... 14
Hình 2.1. Đồ thị quan hệ xã hội trích xuất từ nhật ký sự kiện Bảng 1.1 ............ 16
Hình 2.2. Đồ thị minh họa về độ gần của nút trong đồ thị .................................. 29
Hình 2.3. Đồ thị minh họa về độ trung tâm cục bộ của nút ................................ 30
Hình 2.4. Đồ thị minh họa về độ trung gian ....................................................... 31
Hình 4.1. Kiến trúc của MiSoN .......................................................................... 38
Hình 4.2 Giao diện MiSoN hiển thị đồ thị quan hệ xã hội với dữ liệu từ Staffware log ....................................................................................................... 39
Hình 4.3. Vị trí và mối quan hệ của package SocialNetwork trong ProM ......... 40
Hình 4.4. Thiết kế lớp cài đặt độ đo chuyển giao công việc ............................... 42
Hình 4.5 Biểu đồ công tác xây dựng đồ thị quan hệ xã hội ................................ 44
Hình 4.6 Sơ đồ luồng tính toán ma trận trọng số ................................................ 44
9
MỞ ĐẦU
Cùng với sự phát triển của công nghệ thông tin, các hệ thống thông tin doanh nghiệp ngày càng được ứng dụng phổ biến, trong đó có thể kể đến những cái tên tiêu biểu: HRM – hệ thống quản lý nhân sự, CRM - quản trị quan hệ khách hàng… Các hệ thống này lưu trữ dữ liệu sự kiện hoạt động của doanh nghiệp dưới dạng các bản ghi có cấu trúc kèm theo thông tin về thời gian, chi tiết hoạt động, đối tượng tham gia…, nhờ đó chúng ta có thể hình dung được luồng công việc một cách có hệ thống. Tuy nhiên, các hệ thống nói trên mới mới chỉ dừng ở mức lưu trữ và thống kê, dữ liệu sự kiện của các doanh nghiệp vẫn chưa được sử dụng một cách hiệu quả trong việc hỗ trợ nhà quản trị đưa ra quyết định điều hành.
Việc phân tích các bản ghi sự kiện đã được thực hiện từ rất sớm với nhiều công trình nghiên cứu khác nhau. Hầu hết các đề tài nghiên cứu hiện nay đều đi theo hướng khai phá quy trình - sử dụng các bản ghi sự kiện phục vụ việc xây dựng, cải tiến và kiểm chứng mô hình quy trình. Tuy nhiên, bên cạnh các thông tin về thời gian, công việc thì nhiều hệ thống còn ghi lại cả thông tin về yếu tố con người (ví dụ người thực thi hành động, người được chuyển giao công việc…). Như vậy, các bản ghi sự kiện ngoài việc phản ánh luồng công việc còn có thể phản ánh được mối quan hệ cộng tác trong công việc giữa các cá nhân, nhóm người trong doanh nghiệp.
Môi trường doanh nghiệp cũng có thể coi là một xã hội thu nhỏ, và mối quan hệ trong công việc có thể coi là một loại quan hệ xã hội trong xã hội thu nhỏ đó. Các cá nhân, nhóm người trong doanh nghiệp cùng mối quan hệ giữa họ hình thành nên mạng xã hội. Từ các bản ghi sự kiện chúng ta có thể xây dựng nên mô hình mạng xã hội cũng như phân tích dữ liệu để cho ra những thông tin tổng hợp dưới góc nhìn thuận tiện, hữu ích, hỗ trợ cho nhà quản trị doanh nghiệp.
Luận văn của tôi dựa trên nghiên cứu của WMP Van der Aalst và Minseok Song trình bày trong [1]. Trong đó, các bản ghi sự kiện sẽ được sử dụng trong khai phá mạng xã hội (mà cụ thể hơn là khai phá mối quan hệ giữa các cá nhân/nhóm người) nhằm phục vụ cho việc quản trị nhân sự trong doanh nghiệp.
Nội dung đề tài tôi sẽ trình bày bao gồm các phần như sau:
Chương 1: Trình bày những khái niệm cơ bản về nhật ký sự kiện, khai phá quy trình và những kiến thức khác liên quan đến đề tài.
10
Chương 2: Trình bày về khai phá mạng xã hội bao gồm những khái niệm cơ bản, các độ đo trong trích xuất đồ thị quan hệ xã hội và phân tích mạng xã hội.
Chương 3: Cải thiện độ đo trong trích xuất đồ thị quan hệ xã hội.
Chương 4: Cài đặt và thực nghiệm.
Hà Nội, ngày18 tháng10 năm 2015
Trần Thị Phương
11 Chương 1. Những khái niệm cơ bản về nhật ký sự kiện và
khai phá quy trình
Trong luận văn này, tôi sử dụng các bản ghi sự kiện lấy được từ các hệ thống thông tin doanh nghiệp, kết hợp với phân tích quy trình như đầu vào đã biết cho khai phá mạng xã hội. Vì vậy, trước khi trình bày về khai phá mạng xã hội cũng như việc ứng dụng khai phá mạng xã hội trong môi trường doanh nghiệp, tôi xin trình bày một vài khái niệm và lý thuyết liên quan bao gồm: khái niệm nhật ký sự kiện (event log) và khai phá quy trình(process mining).
1.1. Khái niệm nhật kýsự kiện
Giả sử rằng các hệ thống thông tin doanh nghiệp lưu trữ lịch sử hoạt động của doanh nghiệp trong nhật ký sự kiện (event log)dưới dạng các bản ghi có cấu trúc gọi là sự kiện (event). Các sự kiện ghi trong nhật ký sự kiện thỏa mãn những tính chất sau[2]:
- Mỗi sự kiện tương ứng với một trường hợp (case), một thể hiện quy trình
hoạt động.
- Mỗi sự kiện tương ứng với một hoạt động(activity), một bước nào đó
trong một thể hiện quy trình hoạt động.
- Mỗi sự kiện tương ứng có một người thực thi (performer hoặc resource).
- Trong cùng một trường hợp, các sự kiện được ghi lại theo đúng trình tự
thực hiện về thời gian.
Để hiểu rõ hơn về các khái niệm trường hợp, hoạt động,người thực thi, ta xét ví dụ sau về một quy trình tuyển dụng như Hình 1.1.
Hình 1.1. Sơ đồ quy trình tuyển dụng
Quy trình tuyển dụng bao gồm các bước
Bước 1: Trưởng phòng nhân sự lên kế hoạch tuyển dụng.
Bước 2: Bộ phận nhân sự (HumanResource -HR) đăng tin tuyển dụng.
12
Bước 3: Ứng viên nộp hồ sơ ứng dụng.
Bước 4: HR liên hệ với ứng viên để sắp xếp lịch phỏng vấn.
Bước 5: Trưởng bộ phận/HR v.v. phỏng vấn ứng viên.
Bước 6: Trưởng bộ phận/HR v.v. đánh giá kết quả phỏng vấn và lựa chọn
ứng viên phù hợp.
Bước 7: HR thông báo kết quả tuyển dụng cho ứng viên.
Trong ví dụ này, mỗi lần tuyển dụng tương ứng là một trường hợp. Các bước trong quy trình tuyển dụng (1, 2,..., 6, 7) là các hoạt động. Trưởng phòng nhân sự, HR, ứng viên, trưởng bộ phận… là những người thực thi.
1.2. Khai phá quy trình
Sử dụng đầu vào là nhật ký sự kiện, mục tiêu của khai phá quy trình (Process mining)là trích xuất thông tin về các quy trình [3], qua đó phát hiện, xây dựng và cải tiến quy trình để nâng cao hiệu suất làm việc của doanh nghiệp. Trong phát hiện quy trình, yếu tố con người được bỏ qua, và chúng ta chỉ quan tâm đến thứ tự thực hiện của các hoạt động trong các trường hợp.
Để minh họa cho khái niệm khai pháquy trình, xét ví dụ với một nhật ký sự kiệntổng quát như trongBảng 1.1.
Bảng 1.1 Một ví dụ nhật ký sự kiện tổng quát
Trường hợp 1 2 3 3 1 1 2 4 2 2 5 4 1 3 3 Hoạt động A A A B B C C A B D A C D C D Người thực thi An An Mai Chi Duy An Duy Mai An Minh Mai Chi Minh Mai Minh
13
4 5 5 4 B E D D Mai Nga Nga Minh
Sắp xếp lại theo từng trường hợp, chúng ta có Bảng 1.2.
Bảng 1.2 Nhật ký sự kiện tổng quát đã sắp xếp theo từng trường hợp
Trường hợp 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 Hoạt động A B C D A C B D A B C D A C B D A E D Người thực thi An Duy An Minh An Duy An Minh Mai Chi Mai Minh Mai Chi Mai Minh Mai Nga Nga
Quan sát ví dụ trên ta thấy:
- Mỗi trường hợp đều bắt đầu với hoạt động A và kết thúc bằng hoạt động
D.
- Giữa A và D có thể là E hoặc B và C. - B và C không có thứ tự thực hiện cố định.
1 https://en.wikipedia.org/wiki/Alpha_algorithm 2 https://en.wikipedia.org/wiki/Petri_net
Áp dụng thuật toán alpha1, chúng ta có thể biểu diễn mô hình thể hiện mối quan hệ về mặt thứ tự thực hiện giữa các hoạt động dưới dạng lưới Petri2 như trong Hình 1.2:
14
Hình 1.2. Sơ đồ quy trình dạng lưới Petri cho nhật ký sự kiện tổng quát
Trong luận văn này, tôi tập trung vào khía cạnh xã hội (tức mối quan hệ giữa các cá nhân) của nhật ký sự kiện. Vì vậy, các khái niệm cụ thể trong khai phá quy trình, thuật toán và ký pháp biểu diễntôi sẽ không trình bày chi tiết.
15
Chương 2. Khai phá mạng xã hội
Khác với khai phá quy trình, khai phá mạng xã hội nhằm tới mục tiêu hỗ trợ nhà quản trị đưa ra các quyết định về mặt nhân sự trong doanh nghiệp.Do đó, thay vì tập trung vào thứ tự thực hiện của các hoạt động, khai phá mạng xã hội khai thác mối quan hệ giữa các cá nhân, nhóm người tham gia vào quy trình trích xuất được từ nhật ký sự kiện.
Quá trình khai phá mạng xã hội trải qua hai bước. Đầu tiên, đồ thị quan hệ xã hội (sociogram) giữa các cá nhân tham gia vào quy trình hoạt động của doanh nghiệp được trích xuất từ nhật ký sự kiện. Sau đó,đồ thị quan hệ xã hội được sử dụng làm đầu vào cho phân tích mạng xã hội, tổng hợp dữ liệu và biểu diễn dưới các góc độ, khía cạnh khác nhau, thuận tiện hơn cho việc ra quyết định.
2.1. Trích xuất đồ thị quan hệ xã hội từ các bản ghi sự kiện
Từ góc nhìn toán học, đồ thị quan hệ xã hội là đồ thị G(P, R) trong đó[1]
P:tập các nút của đồ thị, tương ứng tập những người thực thi các hoạt
động trong các bản ghi sự kiện.
R ⊆ P × P là tập các mối quan hệ giữa những người thực thi.
Tùy thuộc vào yêu cầu phân tích mà đồ thị có thể có hướng hoặc vô hướng, có trọng số hoặc không có trọng số. Nếu đồ thị G có trọng số, G có một hàm W dùng để gán giá trị cho các phần tử của R. Tập P có thể được xác định trực tiếp từ các bản ghi sự kiện. Tuy nhiên, R và W thì có nhiều tiêu chí khác nhau để xác định. Ví dụ, ta có thể coi giữa những người trong cùng một phòng ban trên cây cơ cấu tổ chức là có mối liên hệ với nhau. Trong cùng phòng ban đó, những người làm việc cùng một nhóm nhỏ sẽ có mối liên hệ mạnh hơn so với những người cùng phòng ban nhưng khác nhóm. Những người có cùng vai trò trong công việc hay có sự chuyển giao công việc cho nhau cũng được coi là có mối liên hệ với nhau(ta gọi đó là mối quan hệ chuyển giao công việc – Transfer of work)
Theo ngôn ngữ của khai phá quy trình, giả sử trong cùng một trường hợp C, nếu hoạt động A2 được thực hiện ngay sau hoạt động A1 thì mối quan giữa người thực thi A1 và A2 được gọi là quan hệ chuyển giao công việc. Nhìn chung, mối quan hệ chuyển giao công việc phản ánh khá chính xác mối quan hệ trong thực tế hoạt động của doanh nghiệp.
16
Quay lại với ví dụ nhật ký sự kiện trong Bảng 1.1, ta có nhận xét như sau:
- Chi và Duy có thể thực hiện các hoạt động như nhau (B và C)
- Duy thì luôn làm việc với An (trường hợp 1 và 2), còn Chi thì lại luôn làm
việc với Mai (trường hợp 3 và 4).
Như vậy, mặc dù có thể Chi và Duy có cùng vai trò nhưng Chi không làm việc với An và Duy không làm việc với Mai. Lập luận tương tự, dựa trên mối quan hệ chuyển giao công việc, từ nhật ký sự kiệnBảng 1.1, ta có thể trích xuất ra đồ thị quan hệ xã hội như Hình 2.1.
Hình 2.1. Đồ thị quan hệ xã hội trích xuất từ nhật ký sự kiện Bảng 1.1
Trong đồ thị trên Hình 2.1, giữa An và Duy, Mai và Chi có sự chuyển giao công việc qua lại. Tuy nhiên giữa Mai và Minh chỉ có sự chuyển giao công việc từ Mai sang Minh mà không có chiều ngược lại. Tương tự với mối quan hệ giữa An và Minh, Mai và Nga. Đồ thị trên là đồ thị không có trọng số, tuy nhiên, để phục vụ cho việc phân tích mạng xã hội, trọng số có thể được thêm vào đồ thị. Trọng số được đánh căn cứ vào tần suất chuyển giao công việc, ví dụ, cung từ An tới Duy có trọng số là 2.
2.2. Các độ đo trong xây dựng đồ thị quan hệ xã hội
Để xây dựng được đồ thị quan hệ xã hội, chúng ta định nghĩa ra các độ đo khác nhau nhằm đánh trọng số cho các cung thể hiện mối quan hệgiữa những người thực thi. Gọi trọng số trên cung nối giữa người thực thi i và j là Wi,j. Nếu Wi,j>= τ nào đó (τ là giá trị ngưỡng) thì ta thêm cung ịj vào tập R. Bằng cách đó, chúng ta có được đồ thị G (P, R, W) có thể dùng làm đầu vào cho các công cụ phân tích mạng xã hội. Trong luận văn này, tôi chỉ trình bày ba loại độ đo có thể được trích xuất từ nhật ký sự kiện [1][2]:
(1) Độ đo dựa trên quan hệ nhân quả
17
(2) Độ đo dựa trên những trường hợp chung
(3) Độ đo dựa trên các hoạt động chung
Để thuận tiện, tôi xin định nghĩa lại dưới dạng toán học khái niệm nhật ký sự kiện và các ký pháp tôi sẽ sử dụng trong phần này[1][2].
Định nghĩa 2.1(Nhật ký sự kiện):Gọi A là một tập các hoạt động, P là tập ntác nhân (cá nhân, nhóm người tham gia vào quy trình).E = A×P là tập hợp các sự kiện có thể xảy ra. Khi đó:
- Mỗi sự kiện được định nghĩa dưới dạng một cặp giá trị (a, p) thể hiện hoạt
động a được thực hiện bởi p.
- C = E* là tập các chuỗi sự kiện có thể (mỗi chuỗi sự kiện tương ứng với
một trường hợp).
- B(C) là tập các túi từ trên C.
- L ⊆ B(C) là một nhật ký sự kiện và là tập con của C.
Với sự kiện e(a, p) ta định nghĩa hai phép toán
- 𝜋a (e) = a
- 𝜋p(e) = p
2.2.1. Độ đo dựa trên quan hệ nhân quả
Độ đo dựa trên quan hệ nhân quả phản ánh cách luồng công việc di chuyển giữa các cá nhân trong từng trường hợp. Tính nhân quả thể hiện trong hai loại mối quan hệ mà chúng ta sẽ sử dụng làm độ đo trong phần này: quan hệ chuyển giao công việc (Handover of work) và quan hệ thầu phụ (Sub-contracting).
Quan hệ chuyển giao công việc: Trong cùng một trường hợp, nếu có một hoạt động thực hiện bởi j được thực hiện ngay sau hoạt động thực hiện bởi i thì ta nói ở đây có sự chuyển giao công việc từ i sang j. Khi đánh giá quan hệ chuyển giao công việc ta có thể kết hợp với khai phá quy trình để xác định có thật sự có mối quan hệ nhân quả trong việc chuyển giao hay không. Ngoài ra, khi sử dụng làm độ đo, khái niệm chuyển giao công việc cũng cần thay đổi để có thể phân cấp được độ mạnh yếu của mối quan hệ giữa những người thực thi. Ngoài việc dựa vào sự chuyển giao trực tiếp, chuyển giao gián tiếp cũng có thể được tính tớithông qua việc sử dụng hệ số nhân quả β[1]. Ví dụ nếu có 3 hoạt động xen
18
giữa hoạt động thực hiện bởi i và hoạt động thực hiện bởi j thì hệ số nhân quả là β3.
Quan hệ thầu phụ: Nếu giữa hai hoạt động được thực hiện bởiicó hoạt động được thực hiện bởi j thì ta có nói có mối quan hệ thầu phụ giữa i và j[1].
a. Độ đo dựa trên mối quan hệ nhân quả trong chuyển giao công việc
Ý tưởng cơ bản của độ đo này là những người thực thi có mối liên hệ với nhau nếu giữa họ có sự chuyển giao công việc cho nhau. Khi đánh giá theo độ đo này, có 3 yếu tố cần cân nhắc[1]:
- Ta chỉ quan tâm đến chuyển giao công việc trực tiếp hay tính tới cả chuyển
giao công việc gián tiếp.
- Nếu trong cùng một trường hợp, hai người thực thi chuyển giao công việc cho
nhau nhiều lần thì tính thành một lần hay nhiều lần.
- Chỉ xét tới chuyển giao công việc khi có mối quan hệ nhân quả hay cả khi chuyển giao công việc theo thứ tự bất kỳ (ví dụ trong Hình 1.2, ta thấy A và B không có quan hệ nhân quả vì sau A không nhất thiết phải là B mà còn có thể là C hoặc E)
Căn cứ theo những tiêu chí trên, chúng ta có thể có 8 (23) biến thể khác nhau của độ đo này.
Công thức độ đo và các toán tử sử dụng trong độ đo được định nghĩa như sau:
Định nghĩa 2.2 (⊳, ⊵):Gọi L là một nhật ký sự kiện. Ký hiệu → biểu diễn mối quan hệ nhân quả trích xuất được từ L. Với a1, a2∈ A, p1, p2∈ P, c = (c0, c1,…) ∈ L và n ∈ N ta có[1]
1 Nếu
0 trong trường hợp khác
1 Nếu 0 trong trường hợp khác
19
là một hàm trả về giá trị 1 nếu tồn tại ít nhất một trường hợp trong
và đó có cả p1 và p2 cùng tham gia, và khoảng cách giữa 2 hoạt động mà
thực hiện là n. Nếu n = 1 thì sự chuyển giao công việc là trực tiếp, ngược
lại, nếu n > 1 là chuyển giao gián tiếp.
trả ra số lần của trong cùng trường hợp c, hay nói cách
khác, có tính đến việc trong cùng một trường hợp có thể có nhiều
lần chuyển giao công việc giữa những người thực thi.
và cũng tương tự như và , chỉ khác
ở chỗ là ở đây ta có tính tới cả trường hợp chuyển giao công việc ngẫu nhiên chứ không nhất thiết phải có mối quan hệ nhân quả.
Ví dụ với nhật ký sự kiện Bảng 1.1, xét trường hợp 1, thứ tự thực hiện của các hoạt động là: A (An), B (Duy), C (An), D (Minh). Ta có
Duy An = 1
Duy Minh = 0
Duy An = 0 vì mặc dù Duy thực hiện B ngay sau A thực hiện bởi An thực
hiện A nhưng giữa A và B không có mối quan hệ nhân quả bởi sau A không nhất thiết là B mà có thể là C.
Duy Minh = 1 do B và C có mối quan hệ nhân quả (sau B nhất định phải
có D)
Sử dụng định nghĩa ở trên, ta có 8 công thức về mối quan hệ chuyển giao công việc như sau:
Định nghĩa 2.3 (Độ đo dựa trên sự chuyển giao công việc): Gọi L là một nhật ký sự kiện, p1, p2∈ P và giá trị hệ số β (0 < β < 1) ta có [1]
20
là tỉ lệ giữa số lần chuyển giao công việc trực tiếp từ đến và
tổng số lần chuyển giao công việc của nhật ký sự kiện. cũng vậy
nhưng đã được bỏ qua những lần chuyển giao công việc trùng nhau trong cùng một trường hợp. Ví dụ trong Bảng 1.1 ta có:
An Duy = 2/14
An Duy = 2/5.
và xử lý cả việc chuyển giao công việc không trực tiếp
vào độ đo bằng cách bổ sung thêm hệ số giảm β. Nếu trong cùng một trường hợp, giữa hai người thực thi có n sự kiện thì hệ số giảm sẽ là βn.
quan tâm đến tất cả các lần chuyển giao công việc trong nhật ký sự
kiện
bỏ qua những lần những lần chuyển giao công việc trong cùng một
trường hợp.
Nếu áp dụng công thức trên cho nhật ký sự kiện trong Bảng 1.1, ta có kết quả như trong Bảng 2.1.
21
Bảng2.1. Giá trị độ đo dựa trên sự chuyển giao công việc
An Duy An An An Minh β
0.1 0.3116 (1/3.21) 0.0312 (0.1/3.21) 0.0031 (0.01/3.21)
0.5 0.2352 (1/4.25) 0.1176 (0.5/4.25) 0.0588 (0.25/4.25)
0.9 0.1783 (1/5.61) 0.1604 (0.9/5.61) 0.1444 (0.81/5.61)
Ta thấy Nếu β = 1 thì khả năng phân loại độ mạnh yếu của mối quan hệ giảm đi đáng kể bởi khoảng cách giữa các cá nhân được san bằng, chỉ cần có chuyển giao công việc, bất kể là có bao nhiêu sự kiện xen giữa đều coi như nhau. Điều này là không chính xác khi đánh giá mối quan hệ xã hội trong thực tế. Khi β càng tăng thì độ chênh lệch giữa các giá trị càng giảm [1].
Bốn công thức còn lại cũng tương tự như bốncông thức trên, chỉ khác là chúng chỉ tính tới quan hệ nhân quả giữa các hoạt động.
Ta có thể gộp 8 công thức trên thành 4 công thức như sau:
Định nghĩa 2.4 (Công thức chung cho độ đo dựa trên sự chuyển giao công việc): Gọi L là một nhật ký sự kiện, p1, p2∈ P và giá trị hệ số β (0 < β < 1), k ∈ N ta có [1]
Trong các công thức gộp này, chúng ta thêm vào một hệ số nữa là độ sâu tính toán k (calculation depth factor). Khi tính toán độ đo, k thể hiện giá trị lớn nhất của số sự kiện xen giữa hai hoạt động thực hiện bởi 2 người thực thi. Ví dụ với k
22
= 3 thì ta chỉ tính tới những lần chuyển giao trực tiếp hoặc chuyển giao gián tiếp chỉ cách nhau 1 hoặc 2 sự kiện. Ta thấy:
Với k = 1, β= 1 thì ta có công thức
Với k > max(|c|) ta có công thức
Do các nhật ký sự kiện thường có kích thước lớn nên việc tính tới tất cả các trường hợp chuyển giao công việc dẫn đến phân tích chậm và không hiệu quả. Vì vậy chọn giá trị k phù hợp là rất quan trọng trong khai phá mạng xã hội.
a. Độđo dựa trên quan hệ thầu phụcông việc
Quan hệ thầu phụ công việc cũng dựa trên sự nối tiếp công việc giữa những người thực thi. Với mối quan hệ thầu phụ, cũng giống như chuyển giao công việc, tacũng có thể điều chỉnh để cho ra các công thức độ đo khác nhau. Sự nối tiếp công việc là trực tiếp tức là chỉ có 1 hoạt động ở giữa 2 hoạt động thực hiện bởi một người thực thi khác. Khi có nhiều hoạt động xen giữa thì đó là thầu phụ gián tiếp. Hệ số giảm β cũng được đưa vào công thức cho trường hợp thầu phụ gián tiếp. Ví dụ, giả sử có 4 hoạt động, trong đó hoạt động đầu và cuối được thực hiện bởi cùng người thực thi i, hoạt động thứ 2 và 3 được thực hiện theo thứ tự bởi người thực thi j, k.Khi đó, chúng ta có thể trích xuất hai mối quan hệ từ i tới j và k.
Định nghĩa 2.5 Gọi L là một nhật ký sự kiện. Ký hiệu → biểu diễn mối
quan hệ nhân quả trích xuất được từ L. Với a1, a2∈ A, p1, p2∈ P, c = (c0, c1,…) ∈ L, |c| > 2, n ∈ N và n > 1 ta có[1]
1nếu 0 trong trường hợp khác
1 Nếu
0 trong trường hợp khác
23
trả ra giá trị 1 nếu giữa haihoạt độngcó khoảng cách n được thực
hiện bởi p1 có hoạt động thực hiện bởi p2. Công thức này đã bỏ qua cả yếu tố ràng buộc nhân quả và bỏ qua việc chuyển giao công việc nhiều lần trong
cùng một trường hợp. Ví dụ trong Bảng 1.1, trường hợp 1 thì An Duy = 1
trả ra số lần trong trường hợp c, hay nói cách khác, ở đây
ta tính tới cả việc chuyển giao công việc nhiều lần trong cùng một trường hợp.
và cũng tương tự như trên, nhưng ở đây ta chỉ tính tới
những trường hợp mà giữa các hoạt động thực sự có quan hệ nhân quả thay vì thực thi ngẫu nhiên.
Sử dụng những ký pháp được xác định tại định nghĩa 2.5 ta có các công thức cho độ đo mức độ trung gian (in-between metric) dựa trên mối quan hệ thầu phụnhư sau:
Định nghĩa 2.6 (Độ trung gian): Gọi L là một nhật ký sự kiện. p1, p2∈ P, c = (c0, c1,…) ∈ L, |c| > 2 và giá trị hệ số β (0 < β < 1) [1]
Tuy nhiên, cũng như mối quan hệ chuyển giao công việc, ta cũng có thể gộp 8 công thức trên thành 4 công thức cho độ trung gian bằng cách đưa thêm vào hệ
24
số độ sâu tính toán k.
Định nghĩa 2.7 (Độ trung gian - công thứctổng quát): Gọi L là một nhật ký sự kiện. p1, p2∈ P, giá trị hệ số β (0 < β < 1) và k ∈ N (k > 1)[1]
Khi tính toán theo độ đo, k là khoảng cách tối đa mà hai hoạt động được thực thi bởi một người thực thi khác. Ví dụ nếu k = 3, chúng ta chỉ tính tới những trường hợp một hoặc hai hoạt động được thực thi ở giữa hai hoạt động được thực thi bởi
một người thực thi khác. Nếu β = 1 và k = 2 thì và nếu
k>max(|c|) thì .
2.2.2. Độ đo dựa trên trường hợp chung
Với độ đo này, chúng ta bỏ qua mối quan hệ nhân quả giữa các hoạt động mà đơn giản tính tần suất haingười thực thi thực hiện các hoạt động trong cùng một trường hợp. Và ta gọi những trường hợp mà cả hai cùng tham gia đó là trường hợp chung (join case). Độ đo cộng tác dựa tính toán độ mạnh mối quan hệ trong đồ thị quan hệ xã hội dựa trên trường hợp chung được định nghĩa như sau:
Định nghĩa 2.8 (Độ đo cộng tác): Gọi L là một nhật ký sự kiện. p1, p2∈ P, c=(c0, c1,…) ∈ L ta có[2]
(c, p1) nếu 𝑔𝑐∈𝐿
p1⋈Lp2=p1 ⋈c p2 / 𝑔𝑐∈𝐿
p1⋈cp2 = 1 nếu ∃0<= i,j< |c|; i #j𝜋p(ci) = p1∧ 𝜋p(cj) = p2; ngược lại p1⋈cp2 = 0
g(c, p1) = 1 nếu ∃0<= i < |c|𝜋p(ci) = p1; ngược lại g(c, p1) = 0
(c, p1) ≠ 0; ngược lại p1⋈Lp2 = 0
Chú ý, trong định nghĩa này chúng ta chia số trường hợp chung cho số trường hợp có p1 tham gia khi xét mối quan hệ giữa p1 và p2. Mối quan hệ này không
25
phải đối xứng. Ví dụ: p1 tham gia 3 trường hợp, p2 tham gia 6 trường hợp, p1 và p2 có 3 trường hợp chung. Như vậy, p1 luôn làm việc với p2 nhưng p2 thì không. Do đó, p1⋈L p2phải khác p2⋈L p1.Áp dụng công thức vào nhật ký sự kiện Bảng 2.1, ta có An⋈LMinh = 2/2 và Minh⋈LAn = 2/4.
2.2.3. Độđo dựa trên các hoạt động chung
Để tính toán độ đo này, trước tiên chúng ta cần thống kê tần suất các cá nhân tham gia vào từng hoạt động[1].
Định nghĩa 2.9(△):Gọi L là một nhật ký sự kiện. p1∈ P, a1∈ A, c = (c0, c1,…) ∈ L ta có [2]:
1 Nếu 0 trong trường hợp khác
Toán tử △giúp xác định ma trận tần suất thực thi của các hoạt động. Ma trận có hàng P và cột A. Áp dụng định nghĩa 2.9 cho nhật ký sự kiện Bảng 1.1 ta có ma trận tần suất như Bảng 2.2.
Bảng2.2. Ma trận tần xuất thực thi hoạt động
Người thực thi A 2 3 0 0 0 0 An Mai Duy Chi Minh Nga B 1 1 1 1 0 0 C 1 1 1 1 0 0 D 0 0 0 0 4 1 E 0 0 0 0 0 1
3
4
https://en.wikipedia.org/wiki/Minkowski_distance https://en.wikipedia.org/wiki/Hamming_distance
Sau khi có ma trận tần suất, chúng ta có thể tính khoảng cách của những người thực thi bằng cách so sánh các vector tần suất của những người thực thi. Các loại khoảng cách khác nhau có thể được áp dụng tuỳ vào mục đích của độ đo. Khoảng cách Minkowski3được áp dụng khi ta có tính tới tần suất tuyệt đối của các cá nhân, hay khoảng cách Hamming4 khi ta không quan tâm giá trị tuyệt đối của tần suất mà chỉ quan tâm 2 giá trị 1/0 tương ứng cá nhân có/không thực thi
26 hoạt động. Một loại độ đo khác là hệ số tương quan Pearson5 dùng để tìm mối quan hệ giữa các trường hợp[1].
Ta có công thức độ đo tương ứng với các loại khoảng cách giữa những người thực thi như sau đây.
Định nghĩa 2.10 (
): Gọi L là một nhật ký sự kiện và △L là ma trận tần suất thực thi hoạt động của những người thực thi. Với p1, p2∈ P, n ∈ 1, 2, 3, … [1]
Với 0, 𝑥 > 0 𝑦 > 0 (𝑥 = 𝑦 = 0) 1, trườnghợpkhác
Với
Trong đó:
là công thức độ đo sử dụng khoảng cách Minkowski
o Khi tham số n = 1 thì ta được công thức của khoảng cách
Manhattan.
o Khi n = 2 thì khoảng cách là khoảng cách Euclidean6.
là độ đo sử dụng khoảng cách Hamming không chứa tham số nhưng
có thể được mở rộng khi áp dụng một số giá trị ngưỡng.
là độ đo với hệ số tương quan Pearson cho giá trị kết quả dao động
5
6
trong khoảng -1 đến +1. Giá trị khoảng cách giữa những người thực thi càng nhỏ thì hệ số tương quan càng tiến gần tới 1 và càng lớn thì càng tiến
https://en.wikipedia.org/wiki/Pearson_product-moment_correlation_coefficient https://en.wikipedia.org/wiki/Euclidean_distance
27
dần tới -1.
Trong ví dụ Bảng 2.2,bằng cái nhìn trực quan, ta có thể khoảng cách giữa Mai và Chi (với 2 hoạt động chung) nhỏ hơn giữa Chi và Nga (không có hoạt động chung nào). Áp dụng các công thức tính khoảng cách trên, ta có
Khoảng cách Minkowski giữa Mai và Chi là 3 và giữa Chi và Nga là 4. Tuy nhiên, nếu Mai thực hiện hoạt động B và C ba lần thì khoảng cách giữa Mai và Chi là 7, tức là so với Mai thì Nga có quan hệ gần gũi hơn với Chi.
Khoảng cách Hamming cho ra Chi gần với Mai hơn so với gần với Nga
bởi khoảng cách Mai-Chi = 1/5, Chi-Nga = 4/5.
Khoảng cách tính theo hệ số tương quan Pearson thì Mai-Chi = 0.2182 và
Chi-Nga = -0.6667.
Như vậy trong trường hợp này, công thức với khoảng cách Hamming và hệ số tương quan Pearson cho ra cùng một nhận định chính xác hơn so với khoảng cách Minkowski.
2.3. Phân tích mạng xã hội
Phân tích mạng xã hội (Social Network Analysis: SNA) là chiến lược nghiên cứu cấu trúc xã hội thông qua lý thuyết mạng và đồ thị[5]. Cách tiếp cận của SNA là coi mạng xã hội như một đồ thị với các nút (thể hiện cho các tác tử, cá nhân trong mạng) và các cạnh thể hiện mối quan hệ giữa những nút mạng, để từ đó tổng hợp dữ liệu và biểu diễn dưới nhiều khía cạnh, góc nhìn khác nhau. Ví dụ, cùng là dữ liệu về hoạt động của một cá nhân trên mạng xã hội facebook, chúng ta có thể đưa ra đồ thị thể hiện mối quan hệ bạn bè trong mạng với nút trung tâm là cá nhân đó, hay đồ thị thể hiện mối quan tâm của cá nhân đó với các loại sản phẩm hàng hóa thông qua dữ liệu tương tác của cá nhân với các mẫu quảng cáo trên facebook…
Đầu vào cho phân tích mạng xã hội là đồ thị quan hệ xã hội. Từ góc nhìn toán học thì đồ thị quan hệ xã hội là đồ thị G(P, R) trong đó P là tập các cá nhân tham gia vào quy trình (người thực thi) và R ⊆ P × P là tập các mối quan hệ giữa các những cá nhân đó. Nếu G vô hướng thì R có tính đối xứng. Nếu đồ thị G có trọng số, G có một hàm W dùng để gán giá trị cho các phần tử của R. Các độ đo dùng cho việc xây dựng đồ thị tôi đã trình bày ở các phần trước. Như đã trình bày ở trên, mục tiêu của phân tích mạng xã hội là đưa ra dữ liệu tổng hợp dưới
28
các khía cạnh, góc nhìn khác nhau nhằm đánh giá tính chất của mạng hoặc của các nút trong mạng. Chính vì vậy, chúng ta cũng cần tới những độ đo để đánh giá. Trong phần này, tôi xin trình bày một số độ đo quan trọng dùng trong phân tích mạng xã hội là mật độ mạng (network density), độ gần (closeness), độ trung tâm (centrality) và độ trung gian(betweenness).
2.3.1. Mật độmạng
Khi phân tích đồ thị quan hệ xã hội một cách tổng thể, một trong những độ đo quan trọng mà chúng ta cần nhắc tới là mật độ mạng (network density). Mật độmạng là tỉ lệ tương đối của số phần tử thực tế trong R (số cung/cạnh của đồ thị) với số phần tử tối đa có thể có của R [7][8]. Nếu đồ thị là đồ thị có hướng n nút, số kết nối tối đa có thể có là n2. Giá trị của mật độ là một số d thuộc [0,1]. Giá trị càng gần 1 thì mạng càng được coi là dày đặc.
Ví dụ với đồ thị trên Hình 2.1, có 6 nút mạng và 8 liên kết giữa các nút, do đó mật độ d = 8/(6*6) = 0.22.
2.3.2. Độ gần
Thay vì đánh giá tổng thể mạng, độ gần (closeness) dùng để đánh giá các nút trong mạng. Giá trị độ gần của một nút phản ánh mức độ gần gũi của nút đó với các nút khác trong mạng. Nút có độ gần càng cao thì càng có nhiều liên kết (trực tiếp và gián tiếp) tới cácnút khác, và trọng số của các liên kết càng cao (với đồ thị có trọng số)[6][7].
Độ gần gũi dựa trên khái niệm đường trắc địa (geodesic path)và khoảng cách trắc địa(geodesic distance) trong đồ thị. Đường trắc địa từ nút i đến nút j là đường đi ngắn nhất để có thể đi từ nút i đến nút j. Với đồ thị không trọng số, đường trắc địachính là đường đi cần ít cung nối nhất. Với đồ thị có trọng số, đườngtrắc địa là đường đi có tổng trọng số các cung/cạnh là nhỏ nhất. Khoảng cách trắc địa chính là độ dài (tổng số cạnh hoặc tổng trọng số) của đường trắc địa[4].
Định nghĩa 2.11 (Độ gần): Cho đồ thị n đỉnh. Gọi Cc(i) là độ gần của nút thứ i, Di,j là khoảng cáchtrắc địa giữa nút i và nút j[7]. Ta có
Do khoảng cách trắc địa không có tính đối xứng trong đồ thị có hướng nên độ
29
gần cũng không có tính đối xứng.
Hình 2.2. Đồ thị minh họa về độ gần của nút trong đồ thị
Xét ví dụ mạng trong Hình 2.2, ta thấy:
Mai là tâm cụm các nút: Giang, Bình, Chi, Dũng, Duy, Minhvà Mai. Như vậyMai có thể tiếp cận các nút này dễ dàng với khoảng cách ngắn. Do đó, Mai có độ gần tương đối cao.
Tương tự An là tâm cụm các nútChi, Sang, Nga, An nên có độ gần tương
đối cao.
Chi có độ gần lớn nhất bởi ngoài việc kết nối trực tiếp với các nút thì những nút trong cụm mạng của mình (An, Mai, Dũng, Bình) thì nó còn kết nối với tâm của các cụm nút mạng khác (Mai, An).
2.3.3. Độ trung tâm
Khái niệm độ trung tâm bao gồm 2 mức: địa phương (local centrality) và toàn cục (global centrality)[8].
a. Độ trung tâm cục bộ
Khi xét độ trung tâm cục bộ của một nút, ta chỉ tính tới các liên kết trực tiếp đến nút đó. Nút càng có nhiều liên kết trực tiếp thì càng có độ trung tâmcục bộcao. Nếu ta loại bỏ tất cả các nút và các cung không liên kết trực tiếp với nút đang xét, ta thu được một mạng thu nhỏ với nút đang xét làm trung tâm. Khi đó, độ trung tâm cục bộ của nút trung tâm mang cùng ý nghĩa với mật độ mạng của mạng nhỏ vừa thu được[8].
30
Hình 2.3. Đồ thị minh họa về độ trung tâm cục bộ của nút
Với mạng ở Hình 2.3, ta có nhận xét
Chi có độ trung tâm cục bộ tương đối cao vì nó liên kết trực tiếp với 4 nút
khác (Bình, Mai, Dũng, An)
Mai có độ trung tâm cao nhất vì nó liên kết trực tiếp với 6 nút khác. Tuy nhiên ta cũng thấy rằng tuy có độ trung tâm cục bộ cao nhưng Mai không có độ gần không cao bằng Chi bởi nếu muốn tiếp cận các nút thuộc cụm khác,Mai bắt buộc phải đi qua Chi.
b. Độ trung tâm toàn cục
Khác với độ trung tâm cục bộ, độ trung tâm toàn cục tính tới cả các liên kết gián tiếp trong mạng và được tính toán thông qua khoảng cách giữa các nút trong mạng. Khoảng cách được nhắc tới ở đây là khoảng cáchtrắc địa đã được trình bày trong độ gần[7][9]. Ý tưởng chủ đạo ở đây là: nếu một nút có càng nhiềuđường trắc địa chạy qua thì nút càng có độ trung tâm cao. Một ví dụ thực tế của nút có độ trung tâm toàn cục cao là tâm mạng nhện. Xét trên khía cạnh xã hội học thì cá nhân tương ứng với nút ở đây có mối quan hệ mật thiết và rộng với các nút khác trong mạng. Do cùng dựa trên khoảng cách trắc địa nên đôi khi độ trung tâm toàn cục còn được gọi là độ gần trung tâm (closeness centrality).
Có nhiều công thức khác nhau, dựa trên tiêu chí khác nhau để đánh giá độ trung tâm toàn cục của một nút. Chỉ số trung tâm Bavelas-Leavitt dựa trên khoảng cáchtrắc địalà một trong số đó.
Định nghĩa 2.12 (Chỉ số Bavelas-Leavitt):Gọi i là một là một nút trong đồ thị
31 và Dj,k là khoảng cách trắc địa từ nút j tới nút k. Gọi BL(i) là chỉ số trung tâm Bavelas-Leavitt của nút i, ta có
j,i + Di,k)
j,k) / ( 𝐷𝑗 ,𝑘
BL(i) = ( 𝐷𝑗 ,𝑘
Ở đây ta thấy rằng giá trị chỉ số đã được chia cho tổng khoảng cách trắc địa từ và tới nút đang xét. Ta có thể chuẩn hoá độ đo này bằng cách đem chia độ trung tâm cho kích thước mạng. Tuy nhiên, ta cũng thấy rằng cả độ trung tâmcục bộ và toàn cục đều phụ thuộc nhưng không tuyến tính vào kích thước của mạng, vì vậy, chúng ta không thể so sánh độ trung tâm giữa các nút thuộc các mạng có kích thước quá khác nhau[8].
2.3.4. Độ trung gian
Độ trung gian thể hiện mức độ thuận lợi về vị trí của nút trong việc tạo kết nối tới các cặp hoặc các nhóm nút khác ở trong mạng. Nếu một nút nằm trên đường nối giữa 2 nút khác, hoặc nằm trên đường kết nối giữa hai cụm nút thì nút đang xét vai đóng trò điểm trung gian kết nối hai nút, hai cụm nút với nhau [10]. Một nút có vai trò cao trong việc kết nối các nút khác thì ta gọi nút đó có độ trung gian cao. Như vậy, nút càng có độ trung gian cao thì:
Nútnằm ở vị trí quan trọng trong mạng
Tác động đến nút có ảnh hưởng lớn đến tổng thể mạng
Hình 2.4.Đồ thị minh họa về độ trung gian
Nhận xét một cách trực quan ví dụ với mạng trong Hình 2.4, ta có:
32
Các nút như Sang, Nga có độ trung tâm bằng 0 vì nó không nằm trên đường nối giữa hai nút nào khác. Việc loại bỏ những nút này chỉ ảnh hưởng tới bản thân nút đó mà thôi.
Mai và An có độ trung tâm tương đối cao vì nó nằm trên đường kết nối giữa nhiều nút khác (ví dụ Mai nối giữa Duy và Bình, Dũng và Giang…) tạo thành 2 cụm nút mà chúng nằm ở tâm (vai trò trung gian)
Chi có độ trung tâm cao nhất vì Chi đóng vai trò trung gian kết nối hai cụm nút có tâm là Mai và An và những tác động đến Chi sẽ ảnh hưởng lớn đến cấu trúc mạng. Ví dụ, nếu loại bỏ Chi thì hai cụm mạng hoàn toàn mất kết nối tới nhau.
Công thức của độ trung tâmđược định nghĩa như sau:
Định nghĩa 2.13 (Độ trung gian): Cho đồ thị mạng với n nút. Gọi Cb(ni) là độ đo trung tâm của nút i, gkt(nj) là số đường trắc địa nối giữa nút k và nút t có chứa nút j ở giữa. Ta có
Cb(ni) =
𝑥𝑥 𝑛 −2 (𝑛 −1) 2
33 Chương 3. Cải thiện độ đo trong xây dựng đồ thị quan hệ
xã hội
3.1. Đặt vấn đề
Trong những phần trước, tôi đã trình bày các độ đo trong xây dựng đồ thị quan hệ xã hội.Trong các độ đo đó, ta thấy rằng các hoạt độngđược đánh giá ngang hàng với nhau, không phụ thuộc vào tính chất hay bất kỳ thuộc tính nào khác của hoạt động cũng như của sự kiện. Điều này không sát với thực tế hoạt động của doanh nghiệp. Các hoạt động khác nhau cóthời gian thực hiện, mức độ quan trọng cũng như mức độ trao đổi cần thiết để thực thi khác nhau, do đó trên thực tế, mối quan hệ giữa các cá nhân phát sinh từ hoạt động cũng có độ mạnh yếu khác nhau, chịu ảnh hưởng bởi tính chất của các hoạt động. Quay lại với ví dụ về quy trình tuyển dụng với các hoạt động:
1. Trưởng phòng nhân sự lên kế hoạch tuyển dụng
2. HR đăng tin tuyển dụng
3. Ứng viên nộp hồ sơ tuyển dụng
4. HR liên hệ với ứng viên để sắp xếp lịch phỏng vấn
5. Trưởng bộ phận/HR… phỏng vấn ứng viên
6. Trưởng bộ phận/HR… đánh giá kết quả phỏng vấn và lựa chọn ứng viên phù hợp
7. HR thông báo kết quả tuyển dụng cho ứng viên
Như trong ví dụ trên ta có nhận xét mang tính tương đối như sau:
- Hoạt động 1 quan trọng hơn hoạt động 2
- Hoạt động 1 có thời gian thực thi dài hơn hoạt động 2
- Hoạt động 5 và 6 có thể do hai cá nhân/nhóm người khác nhau thực hiện
- Khi thực hiện hoạt động 6 (đánh giá kết quả phỏng vấn và lựa chọn ứng viên), người đánh giá cần phải trao đổi nhiều với người đã thực hiện phỏng vấn.
- HR khi thực hiện hoạt động 2 (đăng tin tuyển dụng) không cần phải trao đổi
nhiều với người lên kế hoạch tuyển dụng.
34
Như vậy, trên thực tế, mối quan hệ giữa người phỏng vấn và người lựa chọn ứng viên mạnh hơn mối quan hệ giữa người lên kế hoạch tuyển dụng và người đăng tin tuyển dụng. Tuy nhiên, khi xây dựng đồ thị quan hệ xã hội theo các độ đo đã trình bày ở trên (giả sử chúng ta dùng độ đo dựa trên sự chuyển giao công việc) thì hai mối quan hệ này có độ mạnh ngang nhau.
Từ ví dụ trên cho thấy việc đánh giá đồng nhất, ngang hàng các hoạt động trong khai phá mạng xã hội từ dữ liệu doanh nghiệp chưa thực sự phù hợp với thực tế hoạt động của doanh nghiệp.
Chính vì vậy, dựa trên các độ đo có sẵn, trong đề tài của mình tôi xin được đề xuất giải pháp cải thiện các độ đo trong xây dựng đồ thị quan hệ xã hội. Trong giới hạn đề tài của mình, tôi chỉ tập trung khắc phục nhược điểm trên độ đo dựa trên sự chuyển giao công việc.
3.2. Giải pháp
Như đã trình bày vấn đề ở phần trên, vấn đề cơ bản với độ đo dựa trên mối quan hệ chuyển giao công việc hiện tại là đang đánh giá đồng nhất, ngang hàng các hoạt động trong quy trình. Do đó, để tăng tính chính xác khi xây dựng đồ thị quan hệ xã hội, có hai vấn đề cần phải được giải quyết:
Đánh lại trọng số cho các hoạt động trong quy trình
Đưa trọng số vào công thức độ đo
3.2.1. Đánh trọng số
Với mỗi loại độ đo khác nhau, tiêu chí và cách đánh trọng số cho các hoạt động cũng khác nhau. Tuy nhiên, có một giải pháp chung nhất cho việc đánh trọng số các hoạt động là đánh trọng số thủ công. Như đã trình bày về khái niệm hoạt động: hoạt động là một bước cụ thể trong quy trình hoạt động của doanh nghiệp. Như vậy, từ nhật ký sự kiện cùng khai phá quy trình, chúng ta hoàn toàn có thể trích xuất được danh sách các hoạt động để đánh trọng số làm đầu vào cho khai phá mạng xã hội. Với cách làm này nhà quản trị hoàn toàn có thể chủ động trong việc đánh giá trọng số theo sự đánh giá cảm tính của bản thân. Tuy vậy, khi các nhật ký sự kiện lớn, quy trình phức tạp và nhiều hoạt động thì việc đánh trọng số thủ công tương đối khó khăn và khó đảm bảo hiệu quả.
Với độ đo dựa trên sự chuyển giao công việc, bản chất mối quan hệ xuất phát từ việc các cá nhân phải trao đổi thông tin với nhau trong quá trình chuyển giao và
35
trong lúc thực thi công việc được chuyển giao. Tôi xin trình bày hướng tiếp cận của mình trong việc đánh trọng số hoạt động áp dụng cho độ đo dựa trên sự chuyển giao công việc. Cách đánh trọng số tôi sẽ trình bày dựa trên nhận xét cơ bản như sau:
- Khi một hoạt động càng cần nhiều thời gian để thực thi thì khả năng cao khi
chuyển giao càng cần nhiều sự trao đổi.
- Cùng một loại hoạt động nhưng giữa những lần chuyển giao khác nhau, thời
gian thực thi và nhu cầu trao đổi có thể khác nhau.
Từ những nhận xét trên, tôi xin đưa ra công thức đánh trọng số cho các hoạt động như Định nghĩa 3.1như sau đây.
Định nghĩa 3.1: Gọi L là một nhật ký sự kiện với a ∈ A, p1, p2∈ P, c = (c0, c1,…) ∈ L và n ∈ N
Gọi Wt(i,j) là trọng số chuyển giao của hoạt động Ci khi chuyển giao từ hoạt động Ci sang hoạt động Cj trong trường hợp c. T(ci) là thời gian thực thi hoạt động ci. Ta có
𝑗 −𝑖
𝑛ế𝑢 𝑗 > 𝑖 Wt(ci, cj) =
0 𝑛ế𝑢 𝑗 ≤ 𝑖
Nếu
0 trong trường hợp khác
1 Nếu
0 trong trường hợp khác
Ở đây, trọng số của một hoạt động trong mối quan hệ chuyển giao công việc sang một hoạt động khác được tính dựa trên khoảng cách thời gian giữa hoạt động đó và hoạt động nối tiếp để chuyển giao. Có một số điểm cần lưu ý trong công thức trên:
36
- Công thức trên đã tính tới việc trường hợp chuyển giao công việc gián tiếp, do đó, khi tính toán thời gian ta phải chia cho khoảng cách giữa các hoạt động (j - i)
- Do công thức áp dụng cho mối quan hệ chuyển giao công việc nên j > i
3.2.2. Áp dụng trọng số chuyển giao vào công thức độ đo
Khi các hoạt động đã được gán các trọng số khác nhau, giá trị trọng số đó cần phải được đưa vào trong độ đo để có được công thức độ đo trong khai phá mạng xã hội phản ánh đúng thực tiễn hơn
Định nghĩa 3.2: ( Gọi L là một nhật ký sự kiện. Ký hiệu → biểu diễn mối quan hệ nhân quả trích xuất được từ L. Với p1, p2P, c = (c0, c1,…)L và nN ta có
Nếu
0 trong trường hợp khác
Nếu
0 trong trường hợp khác
Trong những công thức trên, thay vì đánh trọng số là 1 cho mỗi lần chuyển giao công việc, chúng ta đánh trọng số theo hoạt động của công việc chuyển giao Wt. Bằng cách đó, mối quan hệ chuyển giao các công việc (tương ứng các hoạt động khác nhau) sẽ có sự biến thiên tùy theo tính chất của hoạt động (mà cụ thể ở đây là thời gian cần để thực thi hoạt động).
37
Chương 4. Cài đặt, thực nghiệm
Như đã trình bày trong phần mở đầu, đề tài nghiên cứu của tôi dựa trên nghiên cứu phân tích mạng xã hội của các tác giả WMP Van der Aalst và Minseok Song [1]. Các tác giả đã phát triển và giới thiệu công cụ MiSoN7 dùng trong khai phá mạng xã hội. Đây cũng là nền tảng để tôi cài đặt giải pháp cho bài toán đặt ra trong đề tài của mình.Trong phần này, tôi xin trình bày sơ lược về cấu trúc của công cụ MiSoN và thiết kế, cài đặt, cũng như kết quả thực nghiệm của tôi theo giải pháp đã trình bày ở chương 3.
4.1. Công cụ MiSoN
MinSoN (Mining Social Network) là công cụ được phát triển bởi nhóm tác giả WMP Van der Aalst và Minseok Song dùng cho mục đích khai phá mạng xã hội giữa các cá nhân trên cơ sở dữ liệu từ các hệ thống thông tin doanh nghiệp bao gồm các hệ thống quản lý luồng công việc như Staffware, InConcert, MQSeries, ERP , CRM. Từ các bản ghi sự kiện thu được từ các hệ thống nói trên, MiSoN xây dựng lên đồ thị quan hệ xã hội. Đồ thị thu được có thể được sử dụng làm đầu vào cho phân tích mạng xã hội. Các mối liên kết quan hệ được trích xuất có thể được xuất ra dưới dạng ma trận và sử dụng trong hầu hết các công cụ SNA.Với các công cụ đó, chúng ta có thể áp dụng nhiều kỹ thuật, các độ đo khác nhau (ví dụ như các độ đo trình bày trong phần 2.2) để tìm ra các mẫu tương tác giữa các cá nhân, đánh giá vai trò của các cá nhân trong doanh nghiệp[1].
7
http://www.processmining.org/discontinued/mison
MiSoN được phát triển trên nền tảng Java, có sử dụng các thư viện xử lý dữ liệu XML như JAXB và JDOM, cung cấp giao diện đồ hoạthân thiện, dễ sử dụng [2]. Hình 4.1 mô tả kiến trúc của MiSoN.
38
Hình 4.1. Kiến trúc của MiSoN
Dữ liệu định dạng XML bao gồm các thông tin về quy trình, trường hợp, hoạt động, thời gian của sự kiện cũng như người thực thi. Dữ liệu XML này có thể được xuất ra từ các hệ thống thông tin doanh nghiệp[1].
MinSON cung cấp chức năng tính toán theo các độ đo khác nhau đã đề cập đến trong phần 2.3. Hình 4.2 là ảnh chụp MinSoN hiển thị kết quả của độ đo chuyển giao công việc khi áp dụng trên nhật ký sự kiện Bảng 1.1.
39
Hình 4.2 Giao diện MiSoN hiển thị đồ thị quan hệ xã hội với dữ liệu từ Staffware log
4.2. Thiết kế và cài đặt
Gần đây, MiSoN đã được tích hợp thành module SocialNetwork trong ProM framework8. Dựa trên cấu trúc thiết kế hiện tại của ProM cũng như MiSoN, trong phần này tôi xin trình bày chi tiết thiết kế và cài đặt của giải pháp tôi đã đưa ra ở phần 3.2
4.2.1. Thiết kế tổng thể
8
http://processmining.org/
Vị trí và mối quan hệ giữapackage SocialNetwork và các package liên quan khác được thể hiện như Hình 4.3.
40
Hình 4.3.Vị trí và mối quan hệ của package SocialNetwork trong ProM
Trong đó:
- Framework: cung cấp khung giao diện cho các package tương ứng với các
plugin (SocialNetwork là một trong số đó) hoạt động.
- Log: cung cấp tính năng nhập khẩu tệp làm đầu vào cho các plugin nói chung,
SocialNetwork nói riêng hoạt động (Tệp nhật ký sự kiện).
- SocialNetwork: cung cấp tính năng khai phá mạng xã hội, bao gồm trích xuất
đồ thị quan hệ xã hội, phân tích mạng xã hội.
- Các hệ thống thông tin quản lý cung cấp tệp nhật ký sự kiện làm đầu vào cho
khai phá mạng xã hội.
- Các công cụ phân tích mạng xã hội: đồ thị quan hệ xã hội có thể được xuất
khẩu thành tệp làm đầu vào cho các công cụ phân tích mạng xã hội khác.
- Mining: chứa các lớp phục vụ cho xây dựng đồ thị quan hệ xã hội.
- Analysis: chứa các lớp phục vụ cho phân tích mạng xã hội
41
4.2.2. Cấu trúc tệp nhật ký sự kiện đầu vào
Tệp nhập khẩu đầu vào cho khai phá mạng xã hội có định dạng xml, tuân theo cấu trúc như sau
Tag
WorkflowLog
Source
Process
ProcessInstance AuditTrailEntry
WorkflowModelElement
EventType
Originator
Timestamp Mô tả Tương ứng với một nhật ký sự kiện. Mỗi tệp nhật ký sự kiện chứa một tag WorkflowLog Thuộc tính của WorkflowLog, mô tả nguồn gốc của tệp nhật ký sự kiện. Như trong ví dụ ở trên, tệp nhật ký sự kiện được lấy từ hệ thống staffware Thuộc tính của WorkflowLog, chứa danh sách các trường hợp trong nhật ký sự kiện Tương ứng với một trường hợp Tương ứng với một sự kiện Thuộc tính của AuditTrailEntry, tương ứng tên của sự kiện, tên của hoạt động Thuộc tính của AuditTrailEntry, tương ứng loại sự kiện Thuộc tính của AuditTrailEntry, tương ứng người thực hoạt động trong sự kiện Thuộc tính của AuditTrailEntry, tương ứng thời điểm hoạt động được thực thi
4.2.3. Thiết kế lớp
Do phạm vi đề tài của tôi chỉ tập trung cải thiện độ đo dựa trên mối quan hệ chuyển giao công việc nên trong phần thiết kế chi tiết, những lớp và package chỉ
42
liên quan đến khai phá mạng xã hội nói chung, không liên quan trực tiếp đến độ đo này tôi xin không trình bày cụ thể.
Sơ đồ thiết kế lớp cài đặt cho độ đo chuyển giao công việc được trình bày như trong hình 4.4.
Hình 4.4.Thiết kế lớp cài đặt độ đo chuyển giao công việc
Trong đó, quan trọng nhất là các lớp thực hiện tính toán các độ đo dựa trên mối quan hệ chuyển giao công việc
Lớp Mô tả
BasicOperation
Cài đặt những tính toán chung cho tất cả các loại độ đo trong xây dựng đồ quan hệ xã hội.
HandoverCCCDCM Cài đặt tính toán cho độ đo chuyển giao công việc trong
đó:
- Chỉ tính tới chuyển giao có mối quan hệ nhân quả - Chỉ tính tới chuyển giao trực tiếp - Có tính tới chuyển giao nhiều lần trong cùng một
trường hợp
43
HandoverICIDCM
Cài đặt tính toán cho độ đo chuyển giao công việc trong đó
- Tính tới cả chuyển giao không có tính nhân quả - Tính tới cả chuyển giao gián tiếp - Có tính tới chuyển giao nhiều lần trong cùng một
trường hợp
HandoverICIDIM
Cài đặt tính toán cho độ đo chuyển giao công việc trong đó:
- Tính tới cả chuyển giao không có tính nhân quả - Tính tới cả chuyển giao gián tiếp - Không tính tới chuyển giao nhiều lần trong cùng một
trường hợp
HandoverICCDIM
Cài đặt tính toán cho độ đo chuyển giao công việc trong đó:
- Tính tới cả chuyển giao không có tính nhân quả - Chỉ tính tớichuyển giao trực tiếp - Không tính tới chuyển giao nhiều lần trong cùng một
trường hợp
4.2.4. Luồng hoạt động
Sơ đồ luồng hoạt động của chương trình như Hình 4.5 và Hình 4.6
44
Hình 4.5 Biểu đồ công tác xây dựng đồ thị quan hệ xã hội
Hình 4.6 Sơ đồ luồng tính toán ma trận trọng số
4.3. Kết quả thực nghiệm
Tôithử nghiệm cài đặt với một tệp nhật ký sự kiện đơn giản để thấy được sự khác nhau sau khi thêm trọng số hoạt động vào trong độ đo.
Tệp nhật ký sự kiện đầu vào như sau:
45
Register
complete
Duy
2003-11-25T09:00:00+01:00
Send
complete
Giang
2003-11-25T09:01:00+01:00
Evaluate
complete
Mai
2003-11-25T09:02:00+01:00
Send
complete
Giang
2003-11-25T09:03:00+01:00
Receive
complete
Duy
2003-11-25T09:03:30+01:00
Evaluate
complete
Mai
2003-11-25T09:04:00+01:00
complete
Minh
2003-11-25T09:06:00+01:00
46
47
Register Evaluate
Send Receive Process_complain Check_processing Archieve
Bảng 4.1 Bảng trọng số các hoạt động
0.5 0.75 0.375 0.25 1.0 1.0 0.25
Với bảng trọng số trên, ta có ma trận trọng số mối quan hệ giữa các cá nhân như sau
a. Trường hợp bỏ qua việc chuyển giao công việc nhiều lần, bỏ qua chuyển
giao gián tiếp
Giang Duy Minh Mai
Giang Duy Minh Mai
Giang
0
1.5
Giang
0
0.5625
0.5625
0
1.5
0
0
1.5
Duy
1.5
0
0
0.375
Duy
0.75
0
0
1.5
Minh
0
0
0
1.5
Minh
0
0
0
0
Mai
1.5
1.5
0
Mai
1.5
1.125
0
Bảng 4.2. Ma trận trọng số khi bỏ qua chuyển giao công việc nhiều lần, bỏ qua chuyển giao gián tiếp
(a) Không có trọng số hoạt động (b) Có trọng số hoạt động
Quan sát trên bảng (a) ta thấy mối quan hệ Duy-Giang và Duy-Mai có trọng số ngang nhau (1.5). Tuy nhiên, khi đánh trọng số cho hoạt động, mối quan hệ Duy-Giangchịu ảnh hưởng của trọng số hoạt động Register (0.5), mối quan hệ DuyMai chịu ảnh hưởng trọng số hoạt động Receive(0.25) nên trọng số của mối quan hệ Duy-Giang là 0.75, của Duy-Mai là 0.375.
b. Trường hợp bỏ qua chuyển giao công việc nhiều lần trong cùng một
trường hợp, có tính tới chuyển giao gián tiếp
Với hệ sốβ = 0.5 và độ sâu tính toán k = 5 ta có ma trận trọng số như Bảng 4.3 (a) và (b)
Bảng 4.3. Ma trận trọng số khi bỏ qua chuyển giao công việc nhiều lần, có tính tới chuyển giao gián tiếp
Giang Duy Minh Mai
Giang 0.290323 0.645161 0.16129 0.83871
Duy 0.709677 0.064516 0.258065 0.935484
48
0 0.258065 0 0.516129 Minh
0.645161 0.258065 0.580645 0.419355 Mai
(a) Không có trọng số hoạt động
Giang Duy Minh Mai
Giang 0.108871 0.241935 0.060484 0.314516
0.33871 0.032258 0.064516 0.306452 Duy
0.258065 0 0 0.516129 Minh
0.612903 0.193548 0.435484 0.314516 Mai
(b) Có trọng số hoạt động
c. Trường hợp khi có tính tới chuyển giao nhiều lần trong cùng một trường
hợp, bỏ qua chuyển giao gián tiếp
Bảng 4.4. Ma trận trọng số khi có tính tới chuyển giao công việc nhiều lần, bỏ qua chuyển giao gián tiếp
Giang Duy Minh Mai
0 0.125 0 0.125 Giang
0.125 0 0.125 0 Duy
0 0 0 0.125 Minh
0.25 0 0.125 0 Mai
(a) Không có trọng số hoạt động
Giang Duy Minh Mai
0 0.046875 0.046875 0 Giang
0.0625 0 0.03125 0 Duy
0 0 0 0.125 Minh
0.21875 0 0.09375 0 Mai
(b) Có trọng số hoạt động
d. Trường hợp khi có tính tới chuyển giao nhiều lần trong cùng một trường
hợp, bỏ qua chuyển giao gián tiếp
49
Với hệ số β = 0.5 và độ sâu tính toán k = 5 ta có ma trận trọng số như Bảng 4.5 (a) và (b)
Bảng 4.5. Ma trận trọng số khi có tính tới chuyển giao công việc nhiều lần, bỏ qua chuyển giao gián tiếp
Giang Duy Minh Mai
Giang 0.040541 0.09009 0.022523 0.126126
Duy 0.099099 0.099099 0.036036 0.130631
Minh 0.036036 0 0 0.072072
Mai 0.162162 0.036036 0.081081 0.058559
(a) Không có trọng số hoạt động
Giang Duy Minh Mai
Giang 0.040541 0.040541 0.022523 0.081081
Duy 0.063063 0.009009 0.036036 0.076577
Minh 0.036036 0 0 0.072072
Mai 0.036036 0.063063 0.058559
(b) Có trọng số hoạt động
Kết quả thực nghiệm cho thấy sau khi đánh trọng số cho các hoạt động trong quy trình, độ mạnh yếu trong mối mối quan hệ trong đồ thị thu được đã có sự tính chất của hoạt động. phân cấp rõ ràng, chịu ảnh hưởng theo
50
Kết luận
Luận văn được phát triển dựa trên đề tài nghiên cứu của các tác giả WMP Van der Aalst và Minseok Song [1] về việc áp dụng khai phá mạng xã hội trong môi trường doanh nghiệp với dữ liệu là nhật ký sự kiện ghi cung cấp bởi các hệ thống thông tin doanh nghiệp. Thông qua việc tìm hiểu, phân tích các độ đo trong xây dựng đồ thị quan hệ xã hội, luận văn đã chỉ ra điểm yếu trong các độ đo xây dựng đồ thị quan hệ xã hội hiện tại cũng như đề xuất phương hướng cải tiến, khắc phục điểm yếu đó trên độ đo dựa trên mối quan hệ chuyển giao công việc.
Giải pháp được trình bày trong luận văn là đánh trọng số cho các hoạt động trong quy trình dựa trên yếu tố thời gian thực thi của hoạt động. Nhận xét cơ bản định hướng cho giải pháp cho bài toán cải thiện độ đo: thông thường, hoạt động càng cần nhiều thời gian thực thi thì càng cần có nhiều trao đổi và mối quan hệ giữa các cá nhân tham gia càng mạnh. Các thuật toán cải thiện độ đo đã được cài đặt và tiến hành thực nghiệm với một bộ dữ liệu đơn giản như một minh họa cho giải pháp đã được đưa ra.
Hướng nghiên cứu tiếp theo của luận văn là nghiên cứu đưa ra giải pháp cho các độ đo khác trong xây dựng đồ thị quan hệ xã hội (độ đo dựa trên quan hệ thầu phụ, độ đo dựa trên trường hợp chung, độ đo dựa trên các hoạt động chung). Đồng thời,giải pháp hiện tại cũng cần được áp dụng trên dữ liệu của các doanh nghiệp khác nhau để có thể kiểm chứng tính hiệu của giải pháp cũng như có phương hướng điều chỉnh cho phù hợp với thực tiễn hoạt động của các doanh nghiệp.
51
TÀI LIỆU THAM KHẢO
1. Wil M. P. van der Aalst, Hajo A. Reijers, Minseok Song. Discovering Social Networks from Event Logs. Computer Supported Cooperative Work 14(6), 2005.
2. Wil M. P. van der Aalst, Minseok Song. Mining Social Networks: Uncovering Interaction Patterns in Business Processes. Business Process MMaigement 2004, 2004.
3. Wil van der Aalst. Process mining: Discovery, Conformance, enhancement
of business processes, 2011.
4.K Chandra Sekharaiah, MAM Khan. Towards Metrics for Social Computing. World Congress on Science, Engineering, Technology, Dubai, UAE, January, 20-30, 2009.
5. Evelien Otte, Ronald Rousseau. Social network Mailysis: a powerful strategy, also for the information sciences. J. Information Science 28(6): 441-453, 2002.
6.Kazuya Okamoto, Wei Chen, Xiang-Yang Li.Ranking of Closeness Centrality
for Large-Scale Social Networks.
7.Guandong Xu, Yanchun Zhang, Lin Li. Web Mining and Social Networking:
Techniques and Applications (1st edition). Springer US, 2011.
8. Neveen Ghali, Mrutyunjaya Panda, Aboul Ella Hassanien, Vaclav Snasel, Ajith Abraham (eds.). Computational Social Networks: Mining and Visualization. Springer-London, 2012.
9.Sibel Adal, Xiaohui Lu, Malik Magdon-Ismail. Local, community and global
centrality methods for analyzing networks.
10.Freeman, Linton. A set of measures of centrality based on betweenness,
1977.
